Abcd
Questions (1)
Comments (5)
Reputation 15
 0of 0 votes
AnswersPerform an efficient DeepCopy of a linked list whose node is like below:
public class Node { public int Value {get;set;} public Node Next{get;set;} public Node Random{get;set;} }
The Random field points to any random node in the list.
 Abcd in United States Report Duplicate  Flag
Amazon Software Developer Data Structures
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
My solution tested with a?b?c:d:e, a?b:c?d:e and a?b?c:d:e?f:g
Node ConstructTreeHelper(string expression)
{
if(expression == null  expression.Length == 0) {
return null;
}
//Console.WriteLine("Expression is " + expression);
if(expression.Length == 1)
return new Node(expression);
int questionIndex = expression.IndexOf("?");
var root = expression.Substring(0, questionIndex);
//Console.WriteLine("\tRoot is " + root);
var lhsEnd = FindLeftResultLength(expression.Substring(questionIndex+1));
//Console.WriteLine("\tFirst Result Length is " + lhsEnd);
var lhs = expression.Substring(questionIndex + 1, lhsEnd);
var rhs = expression.Substring(lhsEnd+3);
//Console.WriteLine("\tLHS is " + lhs);
//Console.WriteLine("\tRHS is " + rhs);
var rootNode = new Node(root);
rootNode.Left = ConstructTreeHelper(lhs);
rootNode.Right = ConstructTreeHelper(rhs);
return rootNode;
}
int FindLeftResultLength(string expression)
{
int questionIndex = expression.IndexOf("?");
int lastColonIndex = expression.LastIndexOf(":");
int firstColonIndex = expression.IndexOf(":");
if(firstColonIndex == 1)
return 1;
var charArray = expression.ToCharArray();
var pairCount = 0;
int i =1;
for(; i< charArray.Length; i++)
{
if(charArray[i] == '?')
pairCount++;
if(charArray[i] == ':')
pairCount;
if(pairCount == 0 && (i == charArray.Length  charArray[i+2] == ':'))
return i+2;
}
return 1;
}

Abcd
May 08, 2017 Comment hidden because of low score. Click to expand.
1
of 1 vote
I am assuming that the destination is a BST and it needs to be kept that way. My solution is below
void MergeTrees(Node firstTree, Node secondTree)
{
if(secondTree.Left != null)
MergeTrees(firstTree, secondTree.Left);
if(secondTree.Right != null)
MergeTrees(firstTree, secondTree.Right);
secondTree.Left = null;
secondTree.Right = null;
InsertNode(firstTree, secondTree);
}
void InsertNode(Node destHead, Node sourceNode)
{
if(destHead.Value > sourceNode.Value)
{
if(destHead.Left != null)
InsertNode(destHead.Left, sourceNode);
else
destHead.Left = sourceNode;
}
if(destHead.Value < sourceNode.Value)
{
if(destHead.Right != null)
InsertNode(destHead.Right, sourceNode);
else
destHead.Right = sourceNode;
}
}
Complexity is O(n+m)
 Abcd April 21, 2017Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I came up with below answer after modifying the Node class. The complexity is O(n) even though I might have to go through the entire list thrice. Correct me on complexity if I am wrong.
public class Node
{
public int Value {get;set;}
public Node Next{get;set;}
public Node Random{get;set;}
public int NodeCountFromHead {get;set;}
}
static Node DeepCopy(Node sourceHead)
{
if(sourceHead == null)
return null;
int index = 1;
sourceHead.NodeCountFromHead = index;
Node sourceCurrent = sourceHead;
Node destHead = new Node {Value = sourceHead.Value, Next = null};
Node destCurrent = destHead;
while(sourceCurrent.Next != null)
{
sourceCurrent.Next.NodeCountFromHead = ++index;
destCurrent.Next = new Node{Value = sourceCurrent.Next.Value, Next = null, Random = null, NodeCountFromHead = index};
sourceCurrent = sourceCurrent.Next;
destCurrent = destCurrent.Next;
}
// second loop to set the Random node values
sourceCurrent = sourceHead;
destCurrent = destHead;
while(sourceCurrent != null)
{
destCurrent.Random = GetNthNode(destHead, sourceCurrent.Random.NodeCountFromHead);
sourceCurrent = sourceCurrent.Next;
destCurrent = destCurrent.Next;
}
return destHead;
}
static Node GetNthNode(Node destHead, int nodeCountFromHead)
{
Node current = destHead;
int index = 1;
while (index != nodeCountFromHead)
{
current = current.Next;
}
return current;
}

Abcd
April 20, 2017 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
How about just traversing the tree based on the given index and setting isValid flag to false. That should be O(n).
 Abcd May 09, 2017