I had this as an interview question through phone through an online text editor.
The input is a linked list and in addition to a next pointer there is a random pointer that can point to any node in the list. Create a deep copy of the linked list and return the head of the new copy.
This my code below, which does the above Can some one review the code provide some feed back. Also is 28 mins too much for this code for a phone interview? I took my time but still made a few mistakes which has been fixed here already.
public class Node {
public int val;
public Node next;
public Node random;
public Node(int val) {
this.val = val;
next = null;
random = null;
}
}
class CopyUtil {
Node deepCopy(Node head) {
if (head == null) return head;
Dictionary < Node, Node > nodePool = new Dictionary < Node, Node > ();
Node current = head;
Node newHead = new Node(head.val);
nodePool.Add(current, newHead);
newHead.random = getNode(nodePool, head.random);
Node returnHead = newHead;
while (current.next != null) {
newHead.next = getNode(nodePool, current.next);
newHead.next.random = getNode(nodePool, current.next.random);
current = current.next;
newHead = newHead.next;
}
return returnHead;
}
Node getNode(Dictionary < Node, Node > nodePool, Node current) {
Node ret = null;
if (current==null) return ret;
if (nodePool.ContainsKey(current))
ret = nodePool[current];
else {
ret = new Node(current.val);
nodePool.Add(current, ret);
}
return ret;
}
}
Mistakes:
- 1) Had a return type for constructor.
- 2) Had private (unspecified protection levels) Node values.
- 3) I was working with
newHead.random
instead ofnewHead.next.random
inside loop. - 4) Missed
new
keyword in one of initialization of Dictionary. - 5) Missed
null
check when I moved to code to a util function.
Tips:
- 1) The editor was in plain text and 1/2/4 were stupid and silly mistakes which should have been caught if I patiently reviewed the code.
- 2) Practice on a plain notepad editor.
- 3) Have a headphone. Its important to collect your thoughts without worrying about dropping your phone.
- 4) Silly mistakes creeped in when I moved some code lines into a function and was doing some copy/paste. Be careful when you refactor your code during interviews.
- 5) Think your are submitting your code to codereview in stackexchange. lol.