## 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)
{}
};

{
if( head == nullptr ) return nullptr;

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

}``````

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

{
{
return null;
}
//Create copies of all nodes and insert them interleaved in the existing link list
while(temp!=null)
{
Node clonedNode= new Node(temp.data,null,null);
clonedNode.next=temp.next;
temp.next=clonednode;
}
// Set the random pointer
while(temp!=null)
{
copiedNode=temp.next;
copiedNode.Random=temp.Random.next;
temp=temp.next.next;
}

while(temp!=null)
{
Node clonedNode= temp.next;
Node originalNextNode= clonedNode.next;
if(originalNextNode=!=null)
clonedNode.next=originalNextNode.next;
temp.next=originalNextNode;
temp=originalNextNode;
}

}

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

{
return null;
//Create copies of all nodes and insert them interleaved in the existing link list
while(temp!=null)
{
Node clonedNode= new Node(temp.data,null,null);
clonedNode.next=temp.next;
temp.next=clonednode;
}
// Set the random pointer
while(temp!=null)
{
copiedNode=temp.next;
copiedNode.Random=temp.Random.next;
temp=temp.next.next;
}

while(temp!=null)
{
Node clonedNode= temp.next;
Node originalNextNode= clonedNode.next;
if(originalNextNode=!=null)
clonedNode.next=originalNextNode.next;
temp.next=originalNextNode;
temp=originalNextNode;
}

}

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

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.

### 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.