CareerCup

How about just traversing the tree based on the given index and setting isValid flag to false. That should be O(n).

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)

That's great. Thank you!

Only one question: O(n) makes sense. Where did you get O(1) from?

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;
}