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 ...
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