Facebook Interview Question
Country: United States
Interview Type: Phone Interview
Let' s assume
public class Node {
private Node next;
private Node random;
private String data;
// getters and setters omitted for the sake of brevity
}
Deep copy would look like
private Node deepCopy(Node original) {
// We use the following map to associate newly created instances
// of Node with the instances of Node in the original list
Map<Node, Node> map = new HashMap<Node, Node>();
// We scan the original list and for each Node x we create a new
// Node y whose data is a copy of x's data, then we store the
// couple (x,y) in map using x as a key. Note that during this
// scan we set y.next and y.random to null: we'll fix them in
// the next scan
Node x = original;
while (x != null) {
Node y = new Node();
y.setData(new String(x.getData()));
y.setNext(null);
y.setRandom(null);
map.put(x, y);
x = x.getNext();
}
// Now for each Node x in the original list we have a copy y
// stored in our map. We scan again the original list and
// we set the pointers buildings the new list
x = original;
while (x != null) {
// we get the node y corresponding to x from the map
Node y = map.get(x);
// let x' = x.next; y' = map.get(x') is the new node
// corresponding to x'; so we can set y.next = y'
y.setNext(map.get(x.getNext()));
// let x'' = x.random; y'' = map.get(x'') is the new
// node corresponding to x''; so we can set y.random = y''
y.setRandom(map.get(x.getRandom()));
x = x.getNext();
}
// finally we return the head of the new list, that is the Node y
// in the map corresponding to the Node original
return map.get(original);
}
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
struct Node *random;
} Node_t;
void copy_list(Node_t *src, Node_t *dst);
void print_list(Node_t *list);
int get_index(Node_t *list, Node_t *n);
int main(int argc, char **argv)
{
Node_t src;
src.next = (Node_t *)malloc(sizeof(Node_t));
src.next->next = (Node_t *)malloc(sizeof(Node_t));
src.next->next->next = NULL;
src.random = src.next->next;
src.next->random = src.next;
src.next->next->random = &src;
src.data = 1;
src.next->data = 2;
src.next->next->data = 3;
printf("SRC:\n");
print_list(&src);
Node_t dst;
copy_list(&src, &dst);
printf("DST:\n");
print_list(&dst);
dst.random->data = 7;
printf("SRC:\n");
print_list(&src);
printf("DST:\n");
print_list(&dst);
/* should cleanup all dynamically allocated memory here */
return 0;
}
void copy_list(Node_t *src, Node_t *dst)
{
if (dst == NULL) return;
/* copy data and next pointers before copying random pointer */
Node_t *tmpdst = dst;
Node_t *curnode = src;
while (curnode != NULL)
{
tmpdst->data = curnode->data;
if (curnode->next != NULL)
tmpdst->next = (Node_t *)malloc(sizeof(Node_t));
else
tmpdst->next = NULL;
curnode = curnode->next;
tmpdst = tmpdst->next;
}
/* setup random pointers */
tmpdst = dst;
curnode = src;
while (curnode != NULL)
{
if (curnode->random != NULL)
{
int idx = get_index(src, curnode->random);
Node_t *tmpdst2 = dst;
while (idx > 0)
{
tmpdst2 = tmpdst2->next;
--idx;
}
tmpdst->random = tmpdst2;
}
else
{
tmpdst->random = NULL;
}
tmpdst = tmpdst->next;
curnode = curnode->next;
}
}
void print_list(Node_t *list)
{
/* print data from next */
Node_t *curnode = list;
while (curnode != NULL)
{
printf("%d -> ", curnode->data);
curnode = curnode->next;
}
printf("NULL\n");
/* print data from random */
curnode = list;
while (curnode != NULL)
{
printf("%d : ", curnode->data);
if (curnode->random == NULL)
printf("NULL");
else
printf("%d", curnode->random->data);
printf("\n");
curnode = curnode->next;
}
}
int get_index(Node_t *list, Node_t *n)
{
int idx = 0;
Node_t *curnode = list;
while (curnode != NULL)
{
if (curnode == n)
return idx;
++idx;
curnode = curnode->next;
}
return -1;
}
Outputs:
SRC:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
DST:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
SRC:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
DST:
1 -> 2 -> 7 -> NULL
1 : 7
2 : 2
7 : 1
The above solution is O(N^2).
One should ask, do we allow to add a field say Node* workingPtr to the Node. If yes, there is an O(N) solution.
Right, it is O(N^2). The get_index function takes O(N) and is called N times. We could store the source list's random addresses in a hash table (address as key and index as value), and then look them up in the get_index function. That would take O(N) for creating the hash table, and O(1) for the lookup.
map< Node*,Node*> mmap;
Node *copyRandomList(Node *head) {
if(head == NULL) return head;
if(mmap.find(head) != mmap.end()){
return mmap[head];
}
Node* node = new Node(head->label);
mmap[head] = node;
node->next = copyRandomList(head->next);
node->random = copyRandomList(head->random);
return node;
}
Let' s assume
public class Node {
private Node next;
private Node random;
private String data;
// getters and setters omitted for the sake of brevity
}
Deep copy would look like
private Node deepCopy(Node original) {
// We use the following map to associate newly created instances
// of Node with the instances of Node in the original list
Map<Node, Node> map = new HashMap<Node, Node>();
// We scan the original list and for each Node x we create a new
// Node y whose data is a copy of x's data, then we store the
// couple (x,y) in map using x as a key. Note that during this
// scan we set y.next and y.random to null: we'll fix them in
// the next scan
Node x = original;
while (x != null) {
Node y = new Node();
y.setData(new String(x.getData()));
y.setNext(null);
y.setRandom(null);
map.put(x, y);
x = x.getNext();
}
// Now for each Node x in the original list we have a copy y
// stored in our map. We scan again the original list and
// we set the pointers buildings the new list
x = original;
while (x != null) {
// we get the node y corresponding to x from the map
Node y = map.get(x);
// let x' = x.next; y' = map.get(x') is the new node
// corresponding to x'; so we can set y.next = y'
y.setNext(map.get(x.getNext()));
// let x'' = x.random; y'' = map.get(x'') is the new
// node corresponding to x''; so we can set y.random = y''
y.setRandom(map.get(x.getRandom()));
x = x.getNext();
}
// finally we return the head of the new list, that is the Node y
// in the map corresponding to the Node original
return map.get(original);
}
This is not my code...I took it from
stackoverflow . com / questions / 5509825 / duplicate-a-linkedlist-with-a-pointer-to-a-random-node-apart-from-the-next-node
struct node {
node *n, *r;
int data;
};
node *copy(node *src) {
if(!src)
return nullptr;
node *dst = new node({nullptr, src->r, src->data});
src->r = dst;
node *prev = dst;
for(node *p = src->n; p; p = p->n) {
node *q = new node({nullptr, p->r, p->data});
p->r = q;
prev->n = q;
prev = q;
}
vector<node*> saved;
for(node *p = dst; p; p = p->n) {
saved.push_back(p->r);
p->r = p->r->r;
}
int i = 0;
for(node *p = src; p; p = p->n, i++)
p->r = saved[i];
return dst;
}
O(n) time, O(n) space, no maps.
Classic question. Solution and analysis can be googled with 'leetcode-copy-list-with-random-pointer' keyword.
A solution excerpted from the page above using HashMap.
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
RandomListNode newHead = new RandomListNode(head.label);
RandomListNode p = head;
RandomListNode q = newHead;
map.put(head, newHead);
p = p.next;
while (p != null) {
RandomListNode temp = new RandomListNode(p.label);
map.put(p, temp);
q.next = temp;
q = temp;
p = p.next;
}
p = head;
q = newHead;
while (p != null) {
if (p.random != null)
q.random = map.get(p.random);
else
q.random = null;
p = p.next;
q = q.next;
}
return newHead;
}
O(N) solution using a hash map
#include <iostream>
#include <cassert>
#include <functional>
#include <unordered_map>
using namespace std;
struct node {
int v;
node* n;
node* r;
node(int v, node* n = nullptr, node* r = nullptr) : v(v), n(n), r(r) {}
};
auto clone_random_list = [](const node* list) {
unordered_map<const node*,node*> cloned;
function<node*(const node*)> clone_list = [&](const node* n) {
return n ? cloned[n] = new node(n->v, clone_list(n->n)) : nullptr;
};
auto ret = clone_list(list);
function<void(const node*)> set_rand = [&](const node* n) {
n ? cloned[n]->r = cloned[n->r], set_rand(n->n), 0 : 0;
};
set_rand(list);
return ret;
};
auto is_same_list = [](const node* a, const node* b) {
function<bool(const node*, const node*)> impl = [&](const node* a, const node* b) {
return a && b ? a->v == b->v && a->r->v == b->r->v && impl(a->n, b->n) :
!a && !b ? true : false;
};
return impl(a,b);
};
ostream& operator<<(ostream& os, const node* list) {
while (list) {
os << list->v << "->" << list->r->v << " ";
list = list->n;
}
return os;
}
int main() {
auto n3 = new node(3);
auto n2 = new node(2, n3);
auto n1 = new node(1, n2, n3);
n2->r = n1;
n3->r = n2;
cout << n1 << endl;
auto c = clone_random_list(n1);
cout << c << endl;
assert(is_same_list(n1, c));
return 0;
}
O(N) time solution with O(1) space.
Say the original list is n1->n2->..., and the result list' is n1'->n2'->....
First, create list' and set:
n1'.next = n1.next;
n1.next = n1';
for all nodes in list'.
Second, iterate on list and set:
n1'.random = n1.random.next;
n1.next = n1'.next; //restore n1.next
n1'.next = n1.next.next; //adjust n1'.next
for all nodes in list'.
Here is the code:
RandomListNode *copyRandomList(RandomListNode *head) {
if(!head)
return NULL;
RandomListNode * cur = head;
while(cur){
RandomListNode * n = new RandomListNode(cur->label);
n->next = cur->next;
cur->next = n;
cur = n->next;
}
cur = head;
RandomListNode * ret = cur->next;
while(cur){
RandomListNode * cp = cur->next;
assert(cp);
if(cur->random)
cp->random = cur->random->next;
cur->next = cp->next;
if(cp->next)
cp->next = cp->next->next;
cur = cur->next;
}
return ret;
}
#include <map>
#include <string>
using namespace std;
struct Node
{
string data;
Node *next;
Node *random;
};
Node *copyLinkedList(Node *head)
{
map<Node *, Node *> m;
Node *it;
Node *_head = NULL;
Node *prev = NULL;
for (it = head; it; it = it->next)
{
Node *n = new Node();
n->data = string(it->data);
n->next = NULL;
n->random = NULL;
m[it] = n;
}
for (it = head; it; it = it->next)
{
Node *orig = m[it];
orig->next = m[it->next];
orig->random = m[it->random];
}
return m[head];
}
Here is C++ version of algorithm running in O(N) with space complexity of O(N)
#include <map>
#include <vector>
using namespace std;
struct node {
int data;
node *next;
node *random;
node(int d):data(d), next(0), random(0){}
};
node * copy_list(node * r)
{
map<node*, int> nmap;
map<node*, int>::iterator found;
vector<node*> copy;
int pos = 0;
node *cur = r;
while (cur)
{
nmap[cur] = pos++;
copy.push_back(new node(cur->data));
cur = cur->next;
}
cur = r;
for (int i = 0; i < copy.size(); i++)
{
if ((found = nmap.find(cur->random))!= nmap.end())
{
copy[i]->random = copy[found->second];
}
copy[i]->next = (i <copy.size()-1)? copy[i+1]: 0;
cur= cur->next;
}
return copy[0];
}
#include <iostream>
#include <map>
typedef struct Node
{
int data;
struct Node *next;
struct Node *random;
} Node_t;
void copy_list(Node_t *src, Node_t *dst);
void print_list(Node_t *list);
using namespace std;
int main(int argc, char **argv)
{
// Create List
Node_t src;
src.next = new Node_t;
src.next->next = new Node_t;
src.next->next->next = NULL;
src.random = src.next->next;
src.next->random = src.next;
src.next->next->random = &src;
src.data = 1;
src.next->data = 2;
src.next->next->data = 3;
// Print List
cout << "SRC:" << endl;
print_list(&src);
// Copy and Print List
Node_t dst;
copy_list(&src, &dst);
cout << "DST:" << endl;
print_list(&dst);
return 0;
}
void copy_list(Node_t *src, Node_t *dst)
{
if (dst == NULL) return;
map <Node_t*, Node_t*> nodemap;
nodemap.insert ( std::pair<Node_t*, Node_t*>(src, dst));
dst->data = src->data;
while (src != NULL) {
if (src->next != NULL) {
Node_t *tmp = NULL;
if (nodemap.find(src->next) != nodemap.end()) {
tmp = nodemap[src->next];
} else {
tmp = new Node_t;
tmp->data = src->next->data;
nodemap.insert ( std::pair<Node_t*, Node_t*>(src->next, tmp));
}
dst->next = tmp;
} else {
dst->next = NULL;
}
if (src->random != NULL) {
Node_t *tmp = NULL;
if (nodemap.find(src->random) != nodemap.end()) {
tmp = nodemap[src->random];
} else {
tmp = new Node_t;
tmp->data = src->random->data;
nodemap.insert ( std::pair<Node_t*, Node_t*>(src->random, tmp));
}
dst->random = tmp;
} else {
dst->random = NULL;
}
src = src->next;
dst = dst->next;
}
}
void print_list(Node_t *list)
{
/* print data from next */
Node_t *curnode = list;
while (curnode != NULL) {
cout << curnode->data << " -> ";
curnode = curnode->next;
}
cout << "NULL" << endl;
/* print data from random */
curnode = list;
while (curnode != NULL) {
cout << curnode->data << " : ";
if (curnode->random == NULL) {
cout << "NULL";
} else {
cout << curnode->random->data;
}
cout << endl;
curnode = curnode->next;
}
}
1. Insert new nodes between old ones
- Oleksy November 12, 20141->1'->2->2'->3->3'
2. For every inserted node set random is next node to random
1' -> random = 1->random->next
3. Decouple List