Abcd
BAN USER- 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 | PURGE
Amazon Software Developer Data Structures
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;
}
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, 2017I 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;
}
Repmariacbrister, Graphics Programmer at Graphic Systems
Hey, I am Maria and I am from Bluefield. Currently, I work as a freelancer graphic artist. From an early ...
RepDonnaWHale, Data Engineer at ADP
Hi, I am passionate writer with a BA in English from the Ohio State University.5+ years of experience writing ...
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