Amazon Interview Question
Software Engineer / DevelopersTeam: Kindle
Country: India
Interview Type: In-Person
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.
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.
@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.
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.
// 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();
}
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
#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;
}
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 July 15, 2012