## Interview Question

Country: United States

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

We can use hashmaps to do it in O(n) time
algo::
1.copy the linked list with next pointers(arbitrary may be NULL)
All use a hash function
so,while creating cloned linked list...store h(Pi)=Qi for all pointers
2.Now,once the list is created.repeat for each Pi
h(Pi)->arbitrary=h(Pi->arbitrary)
Pi=Pi->next;

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

// Cloning a linked list in O(n)
#include<conio.h>

#include<stdio.h>
#include<malloc.h>

typedef struct NODE
{
int data;
struct NODE *next;
struct NODE *arbt;
}node;

{
node *point;
}book;
void printli(node *href)
{
node *counter = href;
while(counter)
{
printf("%d\t",counter->data);
counter = counter->next;
}
}

{
// printf("Entereed the add node fucntion\n");
node *newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->next = NULL;
node *temp;// (node*)malloc(sizeof(node));
temp = (*href);
if(temp == NULL)
(*href) = newNode;
else
{
while(temp->next)
{
temp = temp->next;
}
temp->next = newNode;
}
}

void printList(node *href)
{
node *counter = (node*)malloc(sizeof(node));
counter = href;

int i=0;
while(counter)
{
printf("CURRENT NODE = %d\t ARBT NODE = %d\n",counter->data,counter->arbt->data);
counter = counter->next;
}
}

void cloneList(node **href1, node **href2)
{
book b[5];
node *currNode;
node *prevNode = (node*)malloc(sizeof(node));
node *nextNode = (node*)malloc(sizeof(node));
currNode = (*href1);
node *temp = (*href2);
int i = 0;
while(currNode)
{
// printf("currNode ->data1 = %d\n", currNode->data);
temp = (*href2);
b[i].point = currNode->next;
i++;
nextNode = currNode->next;
prevNode = currNode;
currNode = nextNode;
// printf("temp->val = %d\n",temp->data);
while(temp->next)
{
temp = temp->next;
}
prevNode->next = temp;
temp->arbt = prevNode;
// printf("currNode ->data2 = %d\n", currNode->data);
}
temp = (*href2);
while(temp)
{
temp->arbt = temp->arbt->arbt->next;
temp = temp->next;
}

temp =(*href1);
i=0;
while(temp)
{
temp->next = b[i].point;
temp = temp->next;
i++;
}

}

int main()
{
node *root= (node*)malloc(sizeof(node));
root = NULL;

//printli(root);

root->arbt = root->next;
(root->next)->arbt = root->next->next;
(root->next->next)->arbt = root->next->next->next->next;
(root->next->next->next)->arbt = root;
root->next->next->next->next->arbt = root->next;
//

printList(root);

node *list2 = (node*)malloc(sizeof(node));
list2 = NULL;
cloneList(&root,&list2);
printf("\n");
printList(list2);

// printList(list2);
return 0;

}

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

Is that even possible with a singly linked list? How do you access the previous pointers?

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.