Facebook Interview Question
Android EngineersCountry: United States
Interview Type: Phone Interview
Node DeepCopy(Node head)
{
Node head2= null;
if(head==null)
{
return null;
}
//Create copies of all nodes and insert them interleaved in the existing link list
Node temp= head;
while(temp!=null)
{
Node clonedNode= new Node(temp.data,null,null);
clonedNode.next=temp.next;
temp.next=clonednode;
}
// Set the random pointer
temp=head;
while(temp!=null)
{
copiedNode=temp.next;
copiedNode.Random=temp.Random.next;
temp=temp.next.next;
}
// Delink the two links
temp=head;
head2=head.next;
while(temp!=null)
{
Node clonedNode= temp.next;
Node originalNextNode= clonedNode.next;
if(originalNextNode=!=null)
clonedNode.next=originalNextNode.next;
temp.next=originalNextNode;
temp=originalNextNode;
}
return head2;
}
Node DeepCopy(Node head)
{
if(head==null)
return null;
Node head2= null;
//Create copies of all nodes and insert them interleaved in the existing link list
Node temp= head;
while(temp!=null)
{
Node clonedNode= new Node(temp.data,null,null);
clonedNode.next=temp.next;
temp.next=clonednode;
}
// Set the random pointer
temp=head;
while(temp!=null)
{
copiedNode=temp.next;
copiedNode.Random=temp.Random.next;
temp=temp.next.next;
}
// Delink the two links
temp=head;
head2=head.next;
while(temp!=null)
{
Node clonedNode= temp.next;
Node originalNextNode= clonedNode.next;
if(originalNextNode=!=null)
clonedNode.next=originalNextNode.next;
temp.next=originalNextNode;
temp=originalNextNode;
}
return head2;
}
it's a common problem when serializing/de-serializing, just on the deep-copy example.
There are multiple pointers to the same Node, so I need to only create the Node once. I don't know which is first, so I need a kind of a factory method that creates it if it's not already created or returns the pointer to the already created. Object Identification in this example is it's pointer value.
Memory cleanup is not done hear, code will leak of course.
#include <unordered_map>
using namespace std;
class Node
{
char value_;
Node* next_;
Node* random_;
public:
Node(char value) : value_{ value }, next_{ nullptr }, random_{ nullptr } {}
Node* deepCopy() const {
unordered_map<Node*, Node*> refs; // hashtable, orig-ptr -> copy-ptr
Node* current = this->next_;
Node* thisCpy = getOrCreate(refs, current);
Node* currentCpy = thisCpy;
while (current != nullptr) {
currentCpy->random_ = getOrCreate(refs, current->random_);
currentCpy->next_ = getOrCreate(refs, current->next_);
current = current->next_;
currentCpy = currentCpy->next_;
}
return thisCpy;
}
private:
static Node* getOrCreate(unordered_map<Node*, Node*>& refs, const Node* orig) {
if (orig == nullptr) return nullptr;
auto it = refs.find(orig);
if (it == refs.end()) {
Node* copy = new Node{orig->value_};
refs[orig] = copy;
return copy;
}
return it->second;
}
};
Different from ChrisK's solution.
+ Insert a new node at alternate locationin the original list that we are trying to copy.
exapmle, original list 1->2->3. Make it 1->1->2->2->3->3
+ Go over the list again to adjust random pointers at even location nodes.
+ go over the list again to separate odd/even location list.
+ return pointer to even location list.
Advantage here is we dont need o(n) space for lookup table. But at the same time, we are modifying the original list, so in real world this entire operation has to be atomic.
In ChrisK's solution we are not modifying the original list.
- mr.robot.fun.society November 04, 2017