NetApp Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
I don't understand why you did
if (p->pRandom != NULL)
{
r->pRandom = p->pRandom->pNext;
}
I mean it should be r->pRandom = p->pRandom, shouldn't it?
Struct node* clone(Struct node *linked_list)
{
Struct node *clone_list = (Struct node *)malloc(sizeof(Struct node));
Struct node *temp = clone_list;
Struct node *next = linked_list;
int length = 0;
while (next != 0){
temp->pNext = (Struct node *)malloc(sizeof(Struct node));
temp = temp->pNext;
next = next->pNext;
length++;
}
temp = clone_list;
next = linked_list;
Struct node * random;
int count = 0;
while (temp != 0){
count = 0;
random = next->pRandom;
while (random != 0){
random = random->pRandom;
count++;
}
random = clone_list;
for (int i=0;i<length - count;i++){
random = random->pNext;
}
temp->pRandom = random;
temp = temp->pNext;
next = next->pNext;
}
}
I believe this works, though it's not really efficient. Not sure there's a faster solution.
#include <stdio.h>
#include<string.h>
#include <stdlib.h>
#include<stdbool.h>
//#include "codeEval.h"
struct elem
{
int data;
struct elem *next;
struct elem *random;
};
typedef struct elem node;
node *head=NULL,*copy=NULL;
node* newNode(int );
void addLast(int );
void display();
void freelist();
node* newNode(int c)
{
node *new = (node*)malloc(sizeof(node));
new->data =c;
new->next=NULL;
return new;
}
void addLast(int c)
{
if(!head)
head = newNode(c);
else
{
node *walk=head;
while(walk->next)
walk = walk->next;
walk->next = newNode(c);
}
}
void display()
{
node *walk=head;
while(walk)
{
printf("%d ->",walk->data);
walk = walk->next;
}
printf("\n");
}
void displayCopy()
{
node *walk=copy;
while(walk)
{
printf("c: %d ->",walk->data);
walk = walk->next;
}
printf("\n");
}
void freelist()
{
node *temp=head;
while(temp)
{
head=temp->next;
free(temp);
temp=head;
}
}
void setRandom(int from, int to)
{
node *walk=head, *toRand=head;
int i;
if(to == -1)
toRand = NULL;
else
{
for(i=1;i<to;i++)
toRand = toRand->next;
}
for(i=1;i<from;i++)
{
walk = walk->next;
}
if(toRand) printf("From %d to Random %d\n",walk->data,toRand->data);
walk->random = toRand;
}
void populateList()
{
addLast(12);
addLast(5);
addLast(25);
addLast(23);
addLast(8);
display();
//set Random from <index> to <index> index - 1 based
setRandom(1,3);
setRandom(2,4);
setRandom(3,2);
setRandom(5,4);
setRandom(4,-1);
}
void insertList()
{
node* walk=head;
while(walk)
{
node *newN = newNode(walk->data);
newN->next = walk->next;
walk->next = newN;
walk=walk->next->next;
if(!copy)
copy=newN;
}
}
void displayRandom()
{
node *walk=head;
while(walk)
{
printf("%d ->",walk->data);
walk = walk->random;
}
printf("\n");
node *c=copy;
while(c)
{
printf("c: %d ->",c->data);
c = c->random;
}
printf("\n");
}
void copyRandom()
{
node* walk=head;
while(walk)
{
if(walk->random)
walk->next->random = walk->random->next;
else
walk->next->random=NULL;
walk=walk->next->next;
}
displayRandom();
}
void revertOriginal()
{
node *walk=head;
while(walk)
{
walk->next = walk->next->next;
walk = walk->next;
}
}
void cloneList()
{
insertList();
display();
copyRandom();
displayCopy();
revertOriginal();
display();
displayCopy();
}
int main(int argc, char **argv) {
populateList();
cloneList();
printf("End\n");
return EXIT_SUCCESS;
}
how abt this code??
// let llhead be the starting of the linked list that need to be cloned
struct node * clone(struct node * llhead)
{
struct node * cchead;
struct node * temp;
struct node * lltemphead;
lltemphead = llhead;
if(lltemphead)
{
temp = (Struct node *)malloc(sizeof(Struct node));
temp->nPtr = lltemphead->nPtr;
temp->rPtr = lltemphead->rPtr;
cchead = temp;
lltemphead = lltemphead->nPtr;
}
while(lltemphead)
{
temp = (Struct node *)malloc(sizeof(Struct node));
temp->nPtr = lltemphead->nPtr;
temp->rPtr = lltemphead->rPtr;
//cchead = temp;
lltemphead = lltemphead->nPtr;
}
return cchead ;
}
Firstly, duplicate each list node and insert them after their correspondent copied nodes, then a list with 2 * n nodes have been created;
Secondly, because every copied node's member "pNext" points to their copying node, so you can traverse the whole new list and set all new nodes' "pRandom" member;
Thirdly, split the new list into two list , one is the original list, the other is what we need。
code is as follows, may have some small bug for I have not tested it。
- ctang January 28, 2014