Today is Thursday, one more day to go. The nice thing is that this coming weekend is Labor Day.
As I mentioned in a previous post, I received my Azure Kinect DK camera. I checked the hardware requirements and tried matching to my machines at home. I decided to get a Windows base pedestal instead of a Linux server. The hardware requirements for the computer follow:
System Requirements: Windows® 10 PC or Ubuntu 18.04 LTS with 7th Generation Intel® CoreTM i3 Processor (Dual Core 2.4 GHz with HD620 GPU or faster), USB 3.0 Port, 4 GB RAM. Not available on Windows 10 in S mode. Skeletal/body tracking and other experiences may require more advanced PC hardware.
Decided on the following hardware from Dell Computers:
Precision 3630 Tower
Dell 43 Ultra HD 4K Multi Client Monitor – P4317Q
The estimated delivery date: Sep. 6 – 10, 2019. With any luck I should receive the order during the weekend. If that is not the case I will hate to wait until the following weekend.
This morning I was talking with a coworker about linked lists and the idea of having a sorted linked list came up. There is nothing new about the problem but since we are approaching the end of the week and I am fried, decided to make this post.
We still use a singly linked queue with the only difference being that the values are in sorted order.
Given that the code is quite simple and short I took a single picture of the diagram and the Java code.
The idea is to traverse the queue from the head using the p variable. If the next node holds the same value we just drop the next node by pointing to the next-next node. Given that we are using Java we do not have to free the memory used by the duplicate node. If using C / C++ we would have to free the node.
If the next node is not a duplicate we just move on to the next node.
// **** create an empty single link queue ****
slq = new SingleLink();
// **** add elements to the queue ****
slq.appendToTail(1);
slq.appendToTail(1);
slq.appendToTail(2);
slq.appendToTail(3);
slq.appendToTail(3);
// **** display the queue ****
System.out.println("main <<< slq: " + slq.toString());
// **** delete duplicates from the queue ****
slq.removeSortedDups();
// **** display the queue ****
System.out.println("main <<< slq: " + slq.toString());
System.out.println();
The test code is familiar. We instantiate and populate the queue. We remove duplicates and we display the queue to verify that all went well.
// **** remove duplicate nodes from a sorted linked list ****
public void removeSortedDups() {
// **** start at the head of the queue ****
SNode<Integer> p = this.head;
// **** traverse the sorted queue ****
while ((p != null) && (p.next != null)) {
if (p.data == p.next.data)
p.next = p.next.next;
else
p = p.next;
}
}
The method starts by setting p to the head. Note that in the code that I wrote in the whiteboard I left the space, but did not write the initialization of p. I woke up today around 04:00 AM and was generating this post around 05:00 PM. It has been a long day. Note that I did mention the initialization while discussing the approach. I would assume the interviewer would hint me of the missing initialization in the code.
The loop which traversed the queue in O(n) checks for duplicates. If the next node is a duplicate we skip it; otherwise we just move to the next node.
main <<< slq: 1 -> 1 -> 2 -> 3 -> 3 main <<< slq: 1 -> 2 -> 3
As we can verify the queue holds duplicates and the values are in ascending order.
The second line shows the queue in which all duplicate nodes have been removed.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa