Microsoft Interview Question Software Engineer / Developers
Team: Bing
Country: United States
Interview Type: In-Person
Duplicate it the way you'd duplicate any (not necessarily acyclic) directed graph: Perform a depth-first traversal, keeping a memo of partially completed copies to handle cycles.
def deep_copy(root):
memo = { None : None }
def copy(node):
if node not in memo:
clone = Node()
memo[node] = clone
clone.left = copy(node.left)
clone.right = copy(node.right)
return memo[node]
return copy(root)
Eugene: He says the left pointers are arbitrary, so you cannot assume the linked structure is, say, acyclic. But like most questions on this site, the question is vague and poorly specified, so answering it requires guesswork, and it's possible the question as originally asked was more specific.
Even if the structure has cycles, there are ways to copy it that only involves O(1) memory in addition to the memory for the new structure. The algorithm has been discussed in earlier duplicates of this question. The basic approach is that you interleave the new linked list with the old: oldNode0 -> newNode0 -> oldNode1 -> newNode1 -> ... -> oldNodeN -> newNodeN, and then you perform something like:
Node* current = list->head;
while (current != null)
{
// current->next is the copy of current
// current->random->next is the copy of current's randm node
// the copy's random will be the random's copy
current->next->random = current->random->next;
current = current->next->next;
}
Then de-interleave, and voila!
Yes, if you're allowed to temporarily modify the existing data structure (which I assumed was illegal), then all kinds of things are possible. The interleaving is definitely a nice and simple way of doing it!
1. Do a shallow copy, and maintain the new node address and data value pair in a hash table.
2. Now traverse the new list, using the hash table as reference and update the random pointer.
Complexity O(n+n)
My solution to the problem is similar to MaxBrenner, but I made the new node and the corresponding source node address in the map, and use it as a reference and update the previous pointer.
typedef Node<int> IntNode;
void duplicate_linkList(IntNode *pSourceList,IntNode* &pTargeList)
{
if(pSourceList == NULL)
return ;
map<IntNode*,IntNode*> Map;
pTargeList = new IntNode(pSourceList->data);
Map.insert(std::map<IntNode*,IntNode*>::value_type(NULL,NULL));
Map.insert(std::map<IntNode*,IntNode*>::value_type(pSourceList,pTargeList));
IntNode *soureItr = pSourceList->next;
IntNode *tarItr = pTargeList;
while(soureItr != NULL)
{
IntNode *next = new IntNode(soureItr->data);
tarItr->next= next;
Map.insert(std::map<IntNode*,IntNode*>::value_type(soureItr,tarItr));
tarItr = next;
}
tarItr->next = NULL;
soureItr = pSourceList;
tarItr = pTargeList;
while(soureItr != NULL)
{
IntNode *t = (Map.find(soureItr->pre))->second;
tarItr->pre = t;
tarItr = tarItr->next;
soureItr = soureItr->next;
}
}
we can use 2 hash
hash1 stores each node of list1 as <node, its position in list>
hash2 stores each node on new list created as <position in new list, node of new list>
in first for loop we create all new nodes with next pointers(right pointers)
in second for loop we assign the prev pointers(random pointer)
Space complexity: O(2n) = O(n)
time complexity: O(2n) = O(n)
let me know if this is correct?
public LinkedList<Integer> createCopy(LinkedList<Integer> list1)
{
HashMap<Node<Integer>, Integer> hash1 = new HashMap<Node<Integer>, Integer>();
HashMap<Integer, Node<Integer>> hash2 = new HashMap<Integer, Node<Integer>>();
LinkedList<Integer> list2 = new LinkedList<Integer>();
int position = 0;
for(Node<Integer> current1 = list1.head; current1!=null; current1 = current1.next, position++)
{
Node<Integer> newNode = list2.insert(current1.value);
hash1.put(current1, position);
hash2.put(position, newNode);
}
for(Node<Integer> current1 = list1.head, current2 = list2.head;
current1!=null;
current1 = current1.next, current2 = current2.next)
{
int pos = current1.prev == null? -1 : hash1.get(current1.prev);
current2.prev = pos == -1? null : hash2.get(pos);
}
return list2;
}
A O(n) solution:
- g233007 February 15, 20121st pass: Copy the DLL like this: every copied node is placed as the next of original node.
Example: 1->2->3->4 =======> 1->1'->2->2'->3->3'->4->4'
2st pass: Copy the random pointer, making the random pointer of copied node point to the next node of random pointer of original node.
Example:
originalNode->right->left=orignalNode->left->right;
originallNode=originalNode->right->right;
3rd pass: Divide the DLL into two DLL.
Time: O(3n)=O(n)