CareerCup

isnt the first one a subset sum variation with constraint of size = 3? Its not the first 3 indices rite? its just the 3 indices whose sum is k?

for the copy of linked list...will this work?

node* copy (node* head)
{
if (!head)
return NULL;

if (map.contains(head))
return map.get(head);

node* newCopy = new node;
newCopy->d = head->d;

map.put(head,newCopy);
newCopy->next = copy(head->next);
newCopy->random = copy(head->random);

}

missed the return newCopy at the bottom of the func...

can u plz tell what will map.contains,map.head do ??

the above solution is WRONG
it creates extra nodes from random pointer

(1) make the list as circular list; O(n)
(1) store the positions in an array of the random nodes; O(n^2)
(1) create list without using random pointer for now; O(n)
(2) check the array and store the random pointers in new list; O(n^2)

Why can't we have two iterations of the original list?

1) Go through the next pointers of the original list, first creating nodes and updating the next pointers.

2) Since each node will have only one random link and also we have allocated memory for all the nodes, update the random links for the output node.

O(n) time, O(n) space.

by creating an array of pointers which points to newly allocated nodes in the new list, we can copy any random pointer relationship in O(1) time, which is O(n) for copying all of them.

@Anonymous

Can you explain your approach? How can you identify which random pointer is going to which node?

dd