One of my friends attended Google interview few days back, and he got this question as one of the questions. I have chosen to discuss the solution for that question in this post. I have written a dedicated post only because if you know a better solution, you can discuss it here so that many others (including myself) can learn.
Question:
There is a lined list whose node has 3 components. The trivial ones are the data and the next pointer. Apart from these two fields, the 3rd field is interesting. It is another pointer called rand which points to a random node in the list. The random node can come before/after the current node in the list, or can also be NULL. Given such a list, how will you make a copy of it? (Before jumping to see my solution, please take a couple of minutes and come up with your own solution first.)
Question:
There is a lined list whose node has 3 components. The trivial ones are the data and the next pointer. Apart from these two fields, the 3rd field is interesting. It is another pointer called rand which points to a random node in the list. The random node can come before/after the current node in the list, or can also be NULL. Given such a list, how will you make a copy of it? (Before jumping to see my solution, please take a couple of minutes and come up with your own solution first.)
struct node {
int data;
struct node *next;
struct node *rand;
}My Answer:
If it is just a matter of data and next fields, the solution becomes very trivial. The only challenge is the rand pointer. One crude way of doing this is to ignore the rand pointer initially and create the copy of the list. To fix the rand pointer, for each node in the given list, find out the order of the node (nth node) to which rand pointer points to. Once the n value is known, use it in the fresh list that you have created. This will take O(n^2) time and is more of a brute force type.
Here is a better solution. Assume that the list given to you is A1->A2->A3->A4 (ignoring the rand pointer).
Create a copy of the same list B1->B2->B3->B4 (Note that A1=B1, A2=B2, A3=B3, A4=B4).
Now, form a list like this A1->B1->A2->B2->A3->B3->A4->B4 (You could have created this as the first step itself, instead of creating a list with only B's).
Now assume that the rand pointers of B's are copied from A's directly. Then, if A1.rand=A3, then B1.rand=A3. Now, if you go to each odd node (i.e. nodes that are newly created), and move the rand pointer just 1 step forward, all your rand pointers will get fixed correctly.
Now the only remaining task is to break down the list once again to two lists which should be very trivial.
Any other answer?
Guys, I have shared one solution that I know of. Is there any better way of doing this?
Machi super da i broke my head for long time but could only arrive at brute force solution. Ur's is Nice :)
ReplyDeleteThere is another variant of the question that one of my friend got:
ReplyDeleteDo this whole thing in O(n) by only a single pass through the first as well as new list.
Answer: In this case, we have to use a hash table. For every node in the first list we create a has table entry mapping between the address of the first list node to the address of the corresponding second list node.
Now while traversing the original list, whichever node we come to we check whether there is a hashtable entry for the values of both the next as well as the random pointer. If any of those entries are not there, we create a new node for that, add a hashtable entry for that and update the pointers for the corresponding node in the second list accordingly. We keep traversing the original list using next pointers till we reach the end.