It is Wednesday evening and the high for the day was about 72F in Apple Valley, MN. The good thing is that most of the day was sunny and as far as I can tell there was no rain. The Minnesota State Fair is going on but my wife and I seldom attend the event.
I received the Azure Kinect DK arrived this afternoon. The box was delivered by FedEx to our next door neighbor. He was home because some workers were replacing his gutters. When he read the label he stopped by and delivered the package. He mentioned that it was interesting that the delivery person did not check the address which was perfectly readable on the box label.
I opened the package and the box. I will set it up this coming Saturday and will immediately start experimenting with it. Want to try it in standalone mode. Hopefully I will have available a computer that meets requirements; otherwise will have to purchase a new DELL. Once that is done will connect to Azure and experiment with the numerous tools available for Machine Learning.
Now let’s dive into the subject of this post. I tried from chapter 2 question 2.1 in the Cracking the Coding Interview book. I am not looking at the solution until after this post is published. If I find issues with the code, I will update the post tomorrow.
The question is straight forward. Given a singly linked list remove duplicates. Given that the first thought would be to use an additional data structure, the second part of the question is to remove duplicates without using additional data structures. Please note that the nodes in the linked list are not in order. Removing duplicates in an order list requires a different approach.
We will use the Java programming language for this question.
In the drawing we have a singly linked queue whose head points to a node with value 1. We have to remove the third node which also has a value of 1. When all is said and done the sample queue will only have nodes with values 1, 2, and 3.
Decided to use a hash map to determine which values are duplicated. As we traverse the queue, we check if the value is already in the hash map or not. If it is, we need to remove it from the queue.
The deleteDups() method implements the algorithm. We first declare p and q which will be used to traverse and delete duplicates from the queue. We instantiate a HashMap data structure which will be used to detect duplicates in the queue.
We enter a loop which will be used to traverse the linked list once. This makes this algorithm O(n) complex.
We check if the value of the current node is not in the hash map. If not, we insert a key value pair with the value of the node and we default the key to 1. This is done because we have no use at the time for the value. We then update the q and p variables.
If the value of the node is a duplicate, we skip the current node.
I just noticed that the last bracket was missed in the picture.
// **** create an empty single link queue ****
slq = new SingleLink();
// **** add elements to the queue ****
slq.appendToTail(1);
slq.appendToTail(2);
slq.appendToTail(1);
slq.appendToTail(3);
slq.appendToTail(1);
// **** display the queue ****
System.out.println("main <<< slq: " + slq.toString());
// **** delete duplicates from the queue ****
slq.deleteDups();
// **** display the queue ****
System.out.println("main <<< slq: " + slq.toString());
System.out.println();
These lines of code belong to the scaffolding that I made to test the methods. I could have copied files or I could just use the same scaffolding and implement a set of methods to solve several questions. I went with the latter approach.
The Java code instantiates a singly linked queue with nodes with values 1, 2, 1, 3, and 1. To make sure all is well we display the queue. We then delete duplicates. In our case the last two 1s should be deleted from the queue. To check that all went well we display the contents of the queue.
// **** delete duplicate values (use additional data structure) ****
public void deleteDups() {
SNode<Integer> p = this.head;
SNode<Integer> q = null;
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
// **** traverse the queue deleting duplicates ****
while (p != null) {
// **** check if not duplicate ****
if (!hm.containsKey(p.data)) {
hm.put(p.data, 1);
q = p;
// p = p.next;
}
// **** remove node from queue ****
else {
q.next = p.next;
// p = p.next;
}
// **** ****
p = p.next;
}
}
The actual code in the Eclipse IDE is quite similar to what we had on the whiteboard. The only optimization was to replace the two assignments of p with a single one. The logic is the same.
The idea is to delete duplicate values from the queue without the use of an external data structure (i.e., HashMap).
We will use three variables and implement two loops to traverse the linked list removing duplicate nodes. This approach uses an outer loop to traverse the queue and a second inner loop that traverses the queue one element less at a time. This produces a O(n^2) algorithm. The p and q variables are used by the inner loop to traverse and delete duplicates.
The deleteDups2() method sets the variable r to the head of the queue.
Two loops are implemented. The outer one moves the r variable one node per pass. The inner loop traverse the remaining queue segment deleting duplicates with respect to the value of node r.
After the second loop completes, the value or r is adjusted to point to the next node in the queue.
Note that when I used the whiteboard, I passed the head of the queue to the deleteDups2() method. Given the way the code is implemented in other methods in the file, the argument head will not be passed as an argument in the actual Java code written in the Eclipse IDE.
// **** create an empty single link queue ****
slq = new SingleLink();
// **** add elements to the queue ****
slq.appendToTail(1);
slq.appendToTail(2);
slq.appendToTail(1);
slq.appendToTail(3);
slq.appendToTail(1);
// **** display the queue ****
System.out.println("main <<< slq: " + slq.toString());
// **** delete duplicates from the queue ****
slq.deleteDups2();
// **** display the queue ****
System.out.println("main <<< slq: " + slq.toString());
The test scaffolding is quite similar to the one used by the first method.
// **** delete duplicate values (no additional data structures) ****
public void deleteDups2() {
// **** ****
SNode<Integer> r = this.head;
// **** empty queue ****
if (r == null)
return;
// **** outer loop ****
while (r.next != null) {
// **** ****
SNode<Integer> q = r;
SNode<Integer> p = r.next;
// **** inner loop ****
while (p != null) {
if (r.data == p.data) {
q.next = p.next;
// p = p.next;
} else {
q = p;
// p = p.next;
}
// ****
p = p.next;
}
// **** ****
r = r.next;
}
}
Note that the head argument is not required as mentioned previously. The r variable is initialized to point to the head of the queue.
We check if the queue is empty and return. We could have also checked if the queue has a single element but I did not include such check in the actual code.
The outer loop traverses the queue from head to one less than the last node. There is no need to check the last node against itself.
The inner loop traverses the rest of the queue comparing the values of the nodes against the current r node. If a duplicate is encountered it is deleted using the p and q variables.
The code optimizes the assignment of the p variable which was not done on the whiteboard.
/*
* Single linked list node.
*/
public class SNode<T> {
SNode<T> next;
T data;
// **** constructor ****
public SNode(T data) {
this.data = data;
}
}
For completeness the SNode class is shown.
main <<< slq: 1 -> 2 -> 1 -> 3 -> 1 main <<< slq: 1 -> 2 -> 3 main <<< slq: 1 -> 2 -> 1 -> 3 -> 1 main <<< slq: 1 -> 2 -> 3
The run of both methods is captured from the console of the Eclipse IDE. As we can see both method remove all the duplicates.
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