## Amazon Interview Question for Software Engineer / Developers

• 0

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

Comment hidden because of low score. Click to expand.
2
of 2 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.

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

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

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

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.

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

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

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

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.

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

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

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

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.

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.

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

Cant we just deep clone the linked list?

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* new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = NULL;
new_node->random = NULL;

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

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

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);
}
printf("Entered link list is :: \n");

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

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

// for clone of link list
printf("\n process for clone link list\n");

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

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

getch();
}

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.

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

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

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.