vinaysachdeva23
BAN USER- 0of 0 votes
AnswersGiven a linked list with each node having two pointers: A next pointer pointing to the next node and a random pointer pointing to a random node in the link list. The random pointer can also point to null.
- vinaysachdeva23 in India
Struct Node
{
int val;
Struct Node* next;
Struct Node* random;
}
Write a function Node* CloneList(Node* head) to clone the list.| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test
Thanks for the solution, the question was asked in the online test for Amazon Bangalore.
- vinaysachdeva23 October 13, 2011small edit::
temp1=start;
temp2=start;
while(temp1 != NULL)
{
if(temp1 != temp2 || temp2->next != temp1)
{
printf(""cycle exist");
break;
}
temp1 = temp1->next;
temp2=temp2->next->next;
}
temp1=start;
temp2=start;
while(temp1 != NULL)
{
if(temp1 != temp2 || temp1->next != temp2)
{
printf(""cycle exist");
break;
}
temp1 = temp1->next;
temp2=temp2->next->next;
}
both are wrong solutions... as the cycle may be present anywhere... something like this:
1->2->3->4->5->6->4.....
I mean the node at 6 is pointing to node at 4
In this case your solution will fail as you are just checking for the circular linj list rather than cycle in the list
use tries
- vinaysachdeva23 November 03, 2010what a stupid.... he couldn't even explain the question... leave abt answer...!!!!
- vinaysachdeva23 November 03, 2010sorry the width would be 15 for the above question pointed by vladmirmee.
7 nodes to the left of root, 7 to the right and one root....
Hence the width would be 15
yes its width would be 256 if the leftmost and the rightmost elements are present.
The width is the distance between leftmost and the rightmost node.
Like for example a tree with root node and its left node has a width of 2 while the width of a tree with a root node and one left node and one right node will be 3
Important point: The width of a tree with root node A, a left node B and a right node to B , say C, will be 2.Since A and B will be on the same column. Hence the leftmost node is B while the right most node will be A (or C).
Hence their difference is 2 and hence the width.
I hope you get it now....
yes its width would be 256 if the leftmost and the rightmost elements are present.
The width is the distance between leftmost and the rightmost node.
Like for example a tree with root node and its left node has a width of 2 while the width of a tree with a root node and one left node and one right node will be 3
Important point: The width of a tree with root node A, a left node B and a right node to B , say C, will be 2.Since A and B will be on the same column. Hence the leftmost node is B while the right most node will be A (or C).
Hence their difference is 2 and hence the width.
I hope you get it now....
yes its width would be 256 if the leftmost and the rightmost elements are present.
The width is the distance between leftmost and the rightmost node.
Like for example a tree with root node and its left node has a width of 2 while the width of a tree with a root node and one left node and one right node will be 3
Important point: The width of a tree with root node A, a left node B and a right node to B , say C, will be 2.Since A and B will be on the same column. Hence the leftmost node is B while the right most node will be A (or C).
Hence their difference is 2 and hence the width.
I hope you get it now....
The question is about the width of a tree not the maximum number of nodes on a particular level...
The width of a tree means how wide it is.
Like as explained above by xenon, the width of tree is not equal to 2 but will be much more than 2 as it extends too wide in 10 levels.
So its clear that the width means the extension of tree not the max number of nodes on a particular level.
If that would have been the case, then a tree with 3 levels would have had same width as a tree with 10 levels(above tree) which contradictorily proves wrong.
Hence the width of a tree actually means how wide it is.
Do an Inorder traversal of the tree and check if that is sorted. If in-order traversal is sorted then it is a BST
- vinaysachdeva23 October 13, 2011