Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
The problem is how to fill in the random links on the 2nd pass. On the original list, the random pointer will point to a member of the list, but how to determine which member it is?
One way is to keep a map of original node pointers to Int, where Int is the position of the node in the list.
Scan through the original list once building an array of new nodes, and a map of old nodes to position.
Then fix up the random pointers in the new linked list using the map to look up the position, and the array to find the right new node.
You can then delete the array and the map. You have complexity of 2n, but of course you have used extra space.
Duplicates of what? It is a linked list. I would assume that there could be duplicate values within the list.
Using a hash map can solve this. They key will be the address of the given node external link and its value will be the address of the newly made node of the duplicate list.
Here is a solution for it in javascript (node.js)
It marks the original objects with their index, then builds an array to represent the new linked lists (thus making it indexable). Then it fixes up the random links. The it deletes the tag it put on the original object. Thus it does it in 2 passes and uses an array plus a tag temporarily.
In Java, you would use a dictionary of objects rather than marking the original nodes of the list. I'm not sure how to create a map where objects are the keys in javascript.
var n = {data: 25, next: {data: 57, next: {data:2, next: {data:6, next:null
};
n.random = n.next.next;
n.next.random = n;
n.next.next.random = n.next.next;
n.next.next.next.random = n.next;
function show(n) {
do {
console.log('data: ' + n.data + ', random: ' + n.random.data);
n = n.next;
} while(n);
}
function copy(n) {
var newNodes = [];
var p = n;
var i = 0;
while(p) {
newNodes.push({data: p.data});
p.index = i++;
p = p.next;
}
p = n;
i = 0;
while(p) {
newNodes[i].next = newNodes[i+1];
newNodes[i].random = newNodes[p.random.index];
++i;
p = p.next;
}
p = n;
while(p) {
delete p.index;
p = p.next;
}
return newNodes[0];
}
console.log('original: ');
show(n);
console.log('copy: ');
show(copy(n));
We need to store pointers of the node in original list in a heap (along with its order of appearance).
Now simply create nodes (no links) for all the elements of first list and store them in another heap (with same order of oppearance)
Traverse each node of first list and look up for index of the node-addresses it is linked to. Do similar linking for second set of nodes.
The solution proposed works pretty well...
After create a replica with regular next links
insert then given linked list into the new replica in a way that node1 of original comes before the node1 of replica.
Let me name node1 of original as node1_orig and
node1 of replica as node1_rep.
node1_rep->rand = node1_orig->rand->next;
After which we can remove the alternating original node to get the replica with with random pointers.
yes we can do it...
In first parse make the clone of the original linklist. Along with this we need to create 2 tables..
1 -- Address of original node , Coresponding Clone node..
2 -- Original node , random node pointer
In the 2nd parse first check the first node is which random node from table 2, find the corresponding node in clone linklist from table 1. link the result to corresponding node in clone link list.
//given start of linked list : start;
*pointer start,start',nextNode,nextNode';
// each node conatin one pointer 'next' and another 'rand' with obvious purposes.
//Part 1 : create clone linked list where rand pointer of each clone is pointing to element pointed by original element of that clone,
// and rand pointer of each original node pointing to its cloned node.
nextNode = start;
start'=null;
while(nextNode!=null){
if(start'==null){
start' = createClone(nextNode);
nextNode'=start';
}
else{
nextNode'->next=createClone(nextNode); //createClone creates a memory for similar node pointer having value as
//argument node and next pointer pointing to null;
nextNode'=nextNode'->next;
}
nextNode'->rand=nextNode->rand;
nextNode->rand=nextNode';
nextNode=nextNode->next;
}
//Part 2 : Point next pointer of each clone to the rand element of respective original nodes
// and rand pointer of each clone to point to cloned rand node
nextNode=start;
nextNode'=start';
while(nextNode!=null){
*pointer temp = nextNode'->next;
nextNode'->next=nextNode'->rand;
nextNode'->rand=nextNode'->rand->rand;
nextNode=nextNode->next;
nextNode'=temp;
}
//Part 3 : Point each original node 'rand' pointer to original rand node,
// and clone node's next pointer to next cloned node.
nextNode=start;
nextNode'=start';
while(nextNode!=null){
nextNode->rand=nextNode'->next;
nextNode'->next=nextNode->next->rand; //null check the value and assign null if nexttNode->next is null;
nextNode=nextNode->next;
nextNode'=nextNode'->next;
}
So, finally
start : pointer to original linked list and
start' : pointer to cloned linked list.
One way is we can visualize the structure as a graph.
1. Do regular BFS on source graph
2. In addition to that every time you de-queue, for each in source set, if not visited , in the clone set create a new node and assign a pointer to the new node. If visited the just assign a new pointer.
yes we can do it...
In first parse make the clone of the original linklist. Along with this we need to create 2 tables..
1 -- Address of original node , Corresponding Clone node..
2 -- Original node , random node pointer
In the 2nd parse first check the first node is which random node from table 2, find the corresponding node in clone linklist from table 1. link the result to corresponding node in clone link list.
yes we can do it...
In first parse make the clone of the original linklist. Along with this we need to create 2 tables..
1 -- Address of original node , Corresponding Clone node..
2 -- Original node , random node pointer
In the 2nd parse first check the first node is which random node from table 2, find the corresponding node in clone linklist from table 1. link the result to corresponding node in clone link list.
yes we can do it...
In first parse make the clone of the original linklist. Along with this we need to create 2 tables..
1 -- Address of original node , Corresponding Clone node..
2 -- Original node , random node pointer
In the 2nd parse first check the first node is which random node from table 2, find the corresponding node in clone linklist from table 1. link the result to corresponding node in clone link list.
In Java
public class ArrayCloner {
public class Node {
int value;
Node next;
Node random;
//getters, setters & contructors
}
private Map<Node,Node> nodeMap = new HashMap<Node,Node>();
public Node cloneArray(Node head) {
if(head == null) {
return null;
}
Node newHead = new Node();
Node currentNewNode = newHead;
Node currentNode = head;
while(currentNode != null) {
currentNewNode.value = currentNode.value;
nodeMap.put(currentNode,currentNewNode);
if(currentNode.next != null) {
currentNewNode.next = new Node();
}
currentNewNode = currentNewNode.next();
currentNode = currentNode.next();
}
currentNewNode = newHead;
currentNode = head;
while(currentNode != null) {
currentNewNode.random = nodeMap.get(currentNode.random);
currentNewNode = currentNewNode.next();
currentNode = currentNode.next();
}
return newHead;
}
}
This is my solution
#include <stdio.h>
#include <stdlib.h>
typedef struct __LinkedListNode__ {
int data;
struct __LinkedListNode__* next;
struct __LinkedListNode__* link;
} LinkedListNode;
LinkedListNode* clone_list(LinkedListNode* head) {
LinkedListNode* trav = head;
LinkedListNode* clone = NULL;
LinkedListNode* cloneHead = NULL;
if (head == NULL)
return NULL;
while (trav) {
clone = malloc(sizeof(LinkedListNode));
clone->data = trav->data;
clone->next = trav->next;
trav->next = clone;
trav = clone->next;
}
trav = head;
cloneHead = trav->next;
while (trav) {
trav->next->link = trav->link->next;
trav = trav->next->next;
}
trav = head;
while (trav) {
clone = trav->next;
trav->next = clone->next;
trav = clone->next;
if (clone->next)
clone->next = clone->next->next;
}
return cloneHead;
}
void destroy(LinkedListNode* head) {
LinkedListNode* node;
while (head) {
node = head;
head = head->next;
free(head);
}
}
void print_list(LinkedListNode* head) {
while (head) {
if(head->link)
printf("data:%d ldata:%d\n",head->data, head->link->data);
else
printf("data:%d ldata:NULL\n",head->data);
head = head->next;
}
}
int main() {
LinkedListNode *node1, *node2, *node3, *node4, *clone;
node1 = malloc(sizeof(LinkedListNode));
node1->data = 1;
node2 = malloc(sizeof(LinkedListNode));
node2->data = 2;
node3 = malloc(sizeof(LinkedListNode));
node3->data = 3;
node4 = malloc(sizeof(LinkedListNode));
node4->data = 4;
node1->next = node2;
node1->link = node3;
node2->next = node3;
node2->link = node4;
node3->next = node4;
node3->link = node2;
node4->next = NULL;
node4->link = node4;
clone = clone_list(node1);
printf("Original\n");
print_list(node1);
printf("\nClone\n");
print_list(clone);
printf("\n");
destroy(node1);
destroy(clone);
return 0;
}
// creating a clone of the nodes of the list
// the next pointers of the original list will
// be pointing to the corresponding node in the copy list
// the next pointers of the copy list will be
// pointing to the next node of the corresponding node
// in the original list
p = head
while (p != null) {
q = clone(p)
q.next = p.next
p.next = q
p = q.next
// random pointer of q points to nowhere at this point
}
// copying random pointers to the copy list
p = head
while (p != null) {
q = p.random.next
p.next.random = q
p = p.next.next
}
// fixing the next pointers in the two lists
p = head
copyhead = p.next
while (p != null) {
q = p.next
p.next = q.next
q.next = p.next.next
p = p.next
}
return copyhead
Cant you do it in O(2n) by traversing it twice?
- King@Work February 05, 2012Once for making it and the other traverse for cloning the external links.