Facebook Interview Question for Android Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

class node
{
public:
	int val;
	node* next;
	node* random;
	
	node( int k ): val(k), next(nullptr), random(nullptr)
	{}
};


node* deepCopy( node* head )
{
	if( head == nullptr ) return nullptr;
	
	node* curr = head;
	node* origNext = nullptr;
	
	// [1] create new nodes link them with current list
	// After this step, we will have 2 lists combined into 1
	while( curr )
	{
		origNext = curr->next;
		curr->next = new node( curr->val );
		curr->next->next = origNext;
		curr = origNext;
	}
	
	// [2] Go over the entire list again and adjust random ptr
	// If original list has x nodes, then new list has 2x nodes
	curr = head;
	while( curr )
	{
		// current's next is copy of current
		// only do this if random is valid
		if( curr->random )
		{
			curr->next->random = curr->random->next;
		}
		curr = curr->next->next;		
	}
	
	// [3] Go over the list again and de-link the new list
	
	node* dummy = new node(-1);
	curr = head;
	node* newCurr = dummy;
	while( curr )
	{
		origNext = curr->next->next;
		newCurr->next = curr->next;
		curr->next = origNext;
		newCurr = newCurr->next;
		curr = curr->next;
	}
	
	return dummy->next;
	
}

- mr.robot.fun.society November 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Ashar November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Ashar November 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
};

- Chris November 04, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More