## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

I like the solution
1) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node
2) Now copy the arbitrary link in this fashion

original->next->arbitrary = original->arbitrary->next; /*TRAVERSE
TWO NODES*/
This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary.
3) Now restore the original and copy linked lists in this fashion in a single loop.

original->next = original->next->next;
copy->next = copy->next->next;
4) Make sure that last element of original->next is NULL.

Time Complexity: O(n)
Auxiliary Space: O(1)

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

The approach is Good

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

Nice approach.

An O(N) time and O(N) auxillary space solution, would be to::

1) Scan the original list and create the copy list, one node at a time, populating ONLY the "next" pointers in each node. Also, while scanning the original list create a map between the addresses of corresponding nodes in original and copied list.

2) Now, scan the original list once again and for each "arbitrary" pointer in each node of the original list, get the corresponding value from the map, and copy that value in "arbitrary" field of the node of the copied list.

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

It seems that you are duplicating every node in the list, if it's so, how the space complexity is O(1), isn't it O(n)?

Could you please elaborate on the space complexity?

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

Got the point, no need any explanation. thanks

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

``````Node* f(Node* h)
{
if (h==null) return null;

Hash<int, int> *ht = new Hash<int, int>();
Node *hp = h;
Node *nh = null;
Node *nt = null;
while (hp!=null)
{
Node *n = new Node(hp->value);
if (nh == null)
{
nh = nt = n;
}
else
{
nt->next = n;
nt = nt->next;
}
hp = hp->next;
};

hp = h;
while (hp != null)
{
if (hp->random == null)
{
ht[hp]->random = null;
}
else
{
ht[hp]->random = ht[hp->random];
}
hp = hp->next;
}

delete ht;
return nh;
}``````

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

Could you pls elaborate your alg bit? Thanks

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

can u please elaborate what is the point of "randolmy pointing "?otherwise its a simple enough question

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

``````// Initial value of source is head of original list
public Node copyList(Node source)
{
// base case
if(source == null)
return null;

// create new node for new list
Node newNode = new Node();
newNode.setData(source.getData());

// set new node's next to copy of original's next
newNode.setNext(copyList(source.getNext()));

return newNode;

}``````

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

Return value is the new head of copied list

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

You are in effect copying a graph, which may be circular, say a node points to one of its predecessors in the list.
The one thing notable is that you have a path with covers every node in the graph for only once.So if the nodes aren't many, you can traverse the old linked list or the new "graph" to check what you have already copied(the latter presumably better for it has less nodes, yet the pointers may overlap each other and point to the same nodes multiple times,the overlapping being proportional to the number of pointers of each node, plus you need to deal with the possibility of circling) instead of using a full-blown hash table; I leave out the implementation.

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

``````Node* copy(root)
{
Node* cur,*tail,*newroot=NULL;

cur=root;
while(cur)
{
temp=getNode(cur->data);

if(!newroot)
newroot=tail=temp;
else
{
tail->random=temp;
tail=tail->random
}
cur=cur->random;
}
return newroot;
}``````

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

i don't understand what is meaning of randomly pointing does it make a graph?or it follow the meaning of single link list where each node point to one node and that node not points it back or multiple nodes can point to one node m confused if it is graph then i think we have to use dfs which is of o(n2) any better and simple solution??

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

I'm confused as well. OP, can you please restate the question more clearly?

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

node* copy_list( node* original )
{
node* original_h=original;
store( original_h );
vector<node*> v;
node* copy_h=new node;
node* prev;
copy_h->data=original_h->data;
copy_h->next=NULL;
copy_h->random=original_h;
v.push_back(originl_h);
node* t=copy_h;
prev=original_h;

original_h=original_h->next;
prev->next=copy_h;
while(original_h)
{
node* tmp=new node;
tmp->data=original_h->data;
tmp->next=NULL;
tmp->random=original_h;
t->next=tmp;
t=t->next;
v.push_back(original_h);
prev=original_h;
original_h=original_h->next;
prev->next=tmp;
}
t=copy_h;
while(t)
{
t->random=t->random->random->next;
t=t->next;
}
node* restore= original;
for(int i=1;i<v.size();i++)
{
restore->next=v[i];
restore=restore->next;
}
return copy_h;
}

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

``````#include<stdlib.h>
#include<stdio.h>

typedef struct node_s{
int data;
struct node_s *next;
struct node_s *arbit;
} Node_s;

while(temp){
next = temp->next;
free(temp);
temp = next;
}
}
}
else{
Node_s * temp = (Node_s *)malloc(sizeof(Node_s));
if(temp){
temp->data = value;
}
}
}
void add_arbit(Node_s *L1, int a, int b){
Node_s * first = L1;
Node_s * second = L1;

while(first){
if(first->data == a)
break;
first = first->next;
}
while(second){
if(second->data == b)
break;
second = second->next;
}
if(first)
first->arbit = second;
}
Node_s * create_node(int val){

Node_s * temp =  (Node_s *)malloc(sizeof(Node_s));
if(temp){
temp->data = val;
temp->next = NULL;
}
return temp;
}

Node_s * clone(Node_s * node){

if(!node) return NULL;
Node_s * current = node;

//First insert clone nodes in original linked list.
while(current){
Node_s * current_next = current->next;
current->next  =  create_node(current->data);
current->next->next = current_next;
current = current_next;
}
current = node;

//Now copy arbit pointer of each node to cloned list
while(current){
Node_s * clone = current->next;
if(current->arbit){
clone->arbit    = current->arbit->next;
}
current = clone->next;
}

current = node;

while(current){
Node_s * clone  = current->next;
current->next = clone->next;
if(clone->next){
clone->next = clone->next->next;
}
current = current->next;
}
//return head pointer to the calling function
}

int main(){
Node_s * L1 = NULL;
push_1(&L1,1);
push_1(&L1,2);
push_1(&L1,3);
push_1(&L1,4);
push_1(&L1,5);
push_1(&L1,6);

print_list_1(L1);

free_list(L1);

return 0;
}``````

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

I think it is doubly linked list, not single linked list. Each node has two pointers next and arbitrary. Where next points to the next node, and arbitrary points to random node.

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.