Amazon Interview Question Software Engineer / Developers


Team: Kindle
Country: India
Interview Type: In-Person


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

In the original list insert dummy nodes between each node, and then update the rand pointers of dummy nodes using rand pointers of the original list, thereafter, pop out all dummy nodes, it's nothing but copy of the original list.

- nik on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

By doing it your way..isnt the original list gets modified??

- rambo on July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, it will not get modified.
e.g. Brackets represent rand pointer
a(c)->b(d)->c(b)->d(c)
Now, add dummy nodes, and populate rand pointers using the rand pointers of the previous nodes (of the original list)
a(c)->a1(c1)->b(d)->b1(d1)->c(b)->c1(b1)->d(c)->d1(c1)
Finally, pop-out all dummy nodes, lists are:
a(c)->b(d)->c(b)->d(c)
a1(c1)->b1(d1)->c1(b1)->d1(c1)
FYI: Original list will be modified in between, but at last it will come back to its original state.

- Anonymous on July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In your example below, how do you know the address of c1 ?

- Aamir on July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have a o(n) solution, but it assumes the nodes are unique.

soln:
While traversing the original list, build a dictionary with node data as the key and node address as the value for the next nodes and the random nodes that get created.
As you build the copy, before creating new nodes check for the existence of a node with the data for the next node and random node in the dictionary. If it exists,m then just do pointer assignment.

- Aamir on July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@nik....you are modifying orig. list. This is read-only list, you are not allowed to change it.
Adding 1 more cond...time complexity should be O(n) and there is no constraints on space.

- gautamkumar on July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the right approach. The list will be modified, but will be returned to its original state before the function returns. This is a good way to do it if you want to avoid using extra space and do it in O(N) deterministic (not expected, like with a hash) time.

@Aamir: that's a good objection. The poster was a little short with the details. But certainly this can be done; I've done it before.

- eugene.yarovoi on July 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the table approach.
First create a copy of the LL by parsing ones, keep the random node as NULL. Also create the table of address let assume hash on original address which store the address of corresponding duplicate node.
In the second parse look for the address of random node in the LL. look for corresponding duplicate address in the table. put this address on random part of corresponding duplicate node.

- Sanjay Kumar on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cant we just deep clone the linked list?

- codingAddicted on July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// A singly link list having next and random pointer . we have to replicate of this link list.


#include<stdio.h>

// structure of link list node
struct node
{
int data;
struct node *next;
struct node *random;
};

void push(struct node **head_ref, int new_data)
{
struct node* current = *head_ref;
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = NULL;
new_node->random = NULL;

if(*head_ref == NULL )
{
*head_ref = new_node;
}
else
{
while(current->next!=NULL)
{
current=current->next;
}
current->next = new_node;
}
}

/* this function will assign the random pointer to the node. random_pointer_no is the node number
which is assign as random pointer for node_number node.
*/
void random(struct node *node, int node_number, int random_pointer_no)
{
int count = 1;
struct node *temp = node;
struct node *current = node;

while(current != NULL && count != node_number ) // find out the node for which we want to assign the random pointer
{
current = current->next;
count++;
}
count = 1; // again initialize the variable for below loop
if(random_pointer_no !=1)
{
while(temp != NULL && count != (random_pointer_no-1)) // assign the next node as random pointer to the current node.
{
temp = temp->next;
count++;
}
current->random = temp->next;
}
else
current->random = node;
}

// for clone of link list
void cloneLinkList(struct node *node, struct node **node_clone)
{
// copy the original link list to new link list
struct node *current = node;
while(current != NULL)
{
struct node *current_clone = *node_clone;
struct node* new_node_clone = (struct node*) malloc(sizeof(struct node));
new_node_clone->data = current->data;
new_node_clone->next = NULL;
new_node_clone->random = NULL;

if(*node_clone == NULL )
{
*node_clone = new_node_clone;
}
else
{
while(current_clone->next!=NULL)
{
current_clone=current_clone->next;
}
current_clone->next = new_node_clone;
}
current = current->next;
}
// now i am working for random pointer of new link list
current = node;
struct node *current_clone = *node_clone;
while(current != NULL)
{
int toggle = 1;
struct node *temp = current;
struct node *temp_clone = current_clone;
while(temp->next != current->random)
{
if(temp->next == NULL) // if we reach end of first link list
{
temp = node;
temp_clone = *node_clone;
if(current->random == temp) // if first node is random pointer
{
current_clone->random = temp_clone;
toggle = 0;
break;
}
}
else
{
temp = temp->next;
temp_clone = temp_clone->next;
}
}
if(toggle) // if we dont set the random pointer already
{
current_clone->random= temp_clone->next;

}
current = current->next;
current_clone = current_clone->next;

}
}



void printlist(struct node *node)
{
while(node->next != NULL)
{
printf(" %d ->",node->data);

node = node->next;
}
printf(" %d ->NULL",node->data);

}
void printAddress(struct node *node)
{
printf("\n node value node address node next add node random address \n");
while(node != NULL)
{
printf(" %3d \t %12d \t %12d \t %12d \n",node->data,node,node->next,node->random);

node = node->next;
}

}
int main()
{
int no_node;
int index;
int val;
int random_pos;
struct node *head = NULL;
struct node *head_clone = NULL;

printf("how many node you want in link list::");
scanf("%d",&no_node);
while(no_node < 1)
{
printf("Cheater you enter less than 1 node ,\nPlease again enter number of node in link list:: ");
scanf("%d",&no_node);
}
printf("Enter the integer node data ");
for(index = 0; index < no_node; index++)
{
printf("Enter the %d data ::",(index+1));
scanf("%d",&val);
push(&head,val);
}
printf("Entered link list is :: \n");
printlist(head);

printf("\nFor Random pointer ::\n Please enter the number between 1 to %d \n", no_node);
for(index = 0;index < no_node; index++)
{
printf("for node %d , Enter Random pointer node :: ",(index+1));
scanf("%d",&random_pos);
if(random_pos < 1 || random_pos > no_node)
{
printf("You entered wrong number so i am quitting from this program");
exit(0);
}
random(head,index+1,random_pos);
}

printf("For original link listnode values with next pointer and random pointer::\n");
printAddress(head);

// for clone of link list
printf("\n process for clone link list\n");
cloneLinkList(head,&head_clone);


printf("\n clone link list is :: \n");
printlist(head_clone);

printf("\n For clone link list ,node values with next pointer and random pointer::\n");
printAddress(head_clone);


getch();
}

- Gupta on July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This seems like a graph representation using adjacency list. This can be easily cloned.

- Victor on July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a map to do this - map<old list node, new list node>
do
begin
if(cur node not in map)
begin
  create new node, add that node in map
end
//set new node pointer
if(cur->next not in map)
begin
  create new node, add that node in map
  map[cur->next] = new node
end
node->next = map[cur->next]

//set random pointer

if(cur->rnd not in map)
begin
  create new node, add that node in map
  map[cur->rnd] = new node
end
node->rnd = map[cur->rnd]

cur = cur->next
End

- PS on July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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


struct SLNode {
	int i;
	struct SLNode* next;
	struct SLNode* rand;
};

struct SLNode* create_random_list()
{
	/*rand()*/
	struct SLNode* v[10];
	int i;
	for ( i = 0; i < 10; i++ ) {
		v[i] = (struct SLNode*) malloc(sizeof(struct SLNode));
		v[i]->next = v[i]->rand = NULL;
		v[i]->i=i;
	}

	for ( i = 0; i < 9; i++ ) {
		v[i]->next = v[i+1];
		v[i]->rand = v[ rand() % 10 ];
	}
	
	v[9]->rand = v[ rand() % 10 ];

	return v[0];
}

void print_rand_list(struct SLNode* node) {

	if ( node == NULL ){
		printf("EOFL\n");
		return ;
	}

	if (node->rand != NULL)
		printf("%d(%d)->",node->i, node->rand->i);

	print_rand_list(node->next);
}

int isNodeVisited(struct SLNode* node) {
	static struct SLNode* v[10] = { NULL,NULL,NULL,NULL,NULL,
								    NULL,NULL,NULL,NULL,NULL,};
	static int cursor = 0;

	int i;

	for ( i = 0; i < cursor; i++ ) {
		if ( node == v[i] )
			return 1;
	}
	v[cursor++] = node;

	return 0;
}

struct SLNode*  DFS( struct SLNode* node ) 
{
	if ( node == NULL )
		return NULL;


	if ( !isNodeVisited(node) ) {
		struct SLNode* new_node = (struct SLNode*) malloc(sizeof(struct SLNode));
		new_node->i = node->i;
		new_node->next = DFS(node->next);
		new_node->rand = DFS(node->rand);

		return new_node;
	}

	return node;
}


void print_p( struct SLNode* p) 
{
	if ( p == NULL ) {
		printf("EOFL\n");
		return;
	}

	printf ("%p->", p);

	print_p(p->next);

}
int main(int argc, char* argv[])
{
	srand(time(NULL));
	struct SLNode* rand_lst = create_random_list();
	print_rand_list(rand_lst);
	print_p(rand_lst);

	struct SLNode* new_lst = DFS(rand_lst);
	print_rand_list(new_lst);
	print_p(new_lst);
	return 0;
}

- alex on August 07, 2012 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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