CareerCup

this is wrong algorithm

This problem is not hard to solve but what Interviewer looking here is your skills to write Bug free program when it involves Pointers, Managing index and Boundary cases.
Think through for all boundary cases

Define a Method IsMirror(Tree t1, Tree t2);
Now problem is just to call this method appropriately

bool IsFoldable(Tree t)
{
  if (t == null) return true;
  return IsMirror(t.Left, t.Right);
}

bool IsMirror(Tree t1, Tree t2)
{
   if (t1 == null && t2 == null)
  {
     return true;
   }

   if (t1 == null || t2 == null)
   {
     return false;
   }
  if (t.data != t2.data)
 {
   return false;
 }
 return IsMirror(t1.right, t2.left) && (t1.left. t2.right);
}

No the output should not be as you mentioned.
You jut need to ensure that printing is reversed on alternative iterations

I would like to ask Interviewer whether he want to find out a loop for a given Spreadsheet or upon updating value of a cell. The complexity of the problem will differ in both the cases.

In case of doing this when updating value of a cell, I will follow this simple approach

For a given Cell value, Get all the referenced Node
Recursively try to find the referenced node. Dead end of the recursion would be no further reference to any cell. A reference back to the Start cell should tell us this is a loop.

Now someone can argue that it is possible to have a loop on the way, not to the start point. My answer would be, it will not be allowed when someone tried to edit value of C Cell.
E.g. A -> B ->C ->D ->C

If you really want to check loop in a given spread sheet, this is going to be little complex as one of the solution provided by thejediknight

We need to clarify certain things about the questions.
Will there be a sequence of one char followed by some number.
Assuming number can be bigger then 9 and smaller to 0

Based on this I have written a C++ code of O(n).
Also assuming given buffer have enough space to accommodate extended string
Idea is first calculate how much extra space will be required to expand the string.
There iterate from end to start, and keep track of Expanded End index
For each char find the length of chars to be expanded and then put it as end by Expanded End index. Continue this till you finish doing for all chars

bool IsDigit(char aChar);

// we have given char array like 'a1b2c3' we have to convert this array to array like this 'abbccc'
// Assumption there is digit after each char
// assupmtion there is enough space in the array
int ExpandCharByNumber(char s[], int length)
{
	if (s == NULL)
	{
		return 0;
	}
	int ExpandedLength = 0;
	int index = 0;
	while (index < length && s[index] != NULL)
	{
		if (IsDigit(s[index]))
		{
			int unit = 1;
			int value = (s[index++] - '0') * unit;
			ExpandedLength--; // Extra space released by longer digit
			unit *= 10;
			while (IsDigit(s[index]))
			{
				value = value * unit + (s[index++] - '0');
				unit *= 10;
				ExpandedLength--; // Extra space released by longer digit
			}

			ExpandedLength += value - 1; // -1 for one space released by the char
		}
		else {
			index++;
		}
	}

	int endIndex = index + ExpandedLength;
	int retValue = endIndex;
	s[endIndex--] = NULL;
	index--;

	// We will move backward from Extra length, use index to know what to expand
	while (endIndex > 0 && index > 0)
	{
		if (IsDigit(s[index]))
		{
			int unit = 1;
			int value = (s[index--] - '0') * unit;
			unit *= 10;
			while (IsDigit(s[index]))
			{
				value = value + (s[index--] - '0') * unit;
				unit *= 10;
			}

			for (int backIndex = value; backIndex > 0; backIndex--)
			{
				s[endIndex--] = s[index];
			}
		}
		index--;
	}
	return retValue;
}

bool IsDigit(char aChar)
{
	return aChar >= '0' && aChar <= '9';
}

int _tmain(int argc, _TCHAR* argv[])
{
	/* Test Driver for  ExpandCharByNumber */
	char anString[250] = "a2b3c1";
	int size = ExpandCharByNumber(anString, 250);
	PrintArray(anString, size);

	char anString1[250] = "a0b4c0";
	size = ExpandCharByNumber(anString1, 250);
	PrintArray(anString1, size);

	char anString2[250] = "a0b0c0";
	size = ExpandCharByNumber(anString2, 250);
	PrintArray(anString2, size);
	return 0;
}

Simple approach using O(n) algo.
Just need to keep two pointers for odd and even index and increase by 2 each, swap odd and even as required

#include "stdafx.h"
#include <iostream>

bool ArrangeEvenOddIndex(int evenOddArray[], int length)
{
	if (length % 2 != 0)
	{
		return false;
	}

	if (evenOddArray == NULL || length < 2)
	{
		return true;
	}

	int oddIndex = 1;
	int evenIndex = 0;
	while (oddIndex < length && evenIndex < length)
	{
		while (evenIndex < length && evenOddArray[evenIndex] % 2 == 0)
		{
			evenIndex += 2;
		}
		while (oddIndex < length && evenOddArray[oddIndex] % 2 == 1)
		{
			oddIndex += 2;
		}

		// Swap Even and Odd
		if (evenIndex < length && oddIndex < length)
		{
			int temp = evenOddArray[evenIndex];
			evenOddArray[evenIndex] = evenOddArray[oddIndex];
			evenOddArray[oddIndex] = temp;
		}
	}
	
	return true;
}

void PrintArray(int arr[], int length)
{
	for (int index = 0; index < length; index++)
	{
		std::cout << arr[index] << " ";
	}

	std::cout << std::endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int oddVernArray[] = {2, 5, 8, 6, 11, 23, 18, 1, 9, 10};
	std::cout << "Before Arranging even and Odd" << std::endl;
	PrintArray(oddVernArray, 10);
	ArrangeEvenOddIndex(oddVernArray, 10);
	std::cout << "After Arranging even and Odd" << std::endl;
	PrintArray(oddVernArray, 10);
	return 0;
}

There is minor bug in the code which is causing incorrect output for the cases mentioned above. Actually you don't need to reset head to i when condition fails.

Here is c# code after fixing the bug

public static void getMaxLength(int[] arr) {
        int len = arr.Length;
        int maxCount = 0;
        for(int i=0;i<len;i++) {
            int head = i; int tail = len-1;
            int max = 0; // Max value of smaller sub-array
            int min = int.MaxValue; // Min value of larger sub-array
            int currentCount = 0; // Max length sub-array for elements starting at index i
            int startMax = -1; // 1 = head represents larger sub-array ; 2 = tail represents larger sub-array

            while(tail > head) {
                if(startMax == -1)
                {
                    startMax = arr[head] > arr[tail] ? 1 : 0;
                    max = (startMax == 1) ? Math.Max(max, arr[tail]) : Math.Max(max, arr[head]);
                    min = (startMax == 1) ? Math.Min(min, arr[head]) : Math.Min(min, arr[tail]);
                    head++;
                    tail--;
                    currentCount++;
                    maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
                    continue;
                }
                else {
                    if((startMax == 1) && ((arr[head] < arr[tail]) || (arr[head] < max) || (arr[tail] > min))) {
                        startMax = -1; 
                        max = 0; 
                        min = int.MaxValue; 
                        //head = i; 
                        currentCount = 0;
                        continue;
                    }
                    else if((startMax == 0) && ((arr[head] > arr[tail]) || (arr[head] > min) || (arr[tail] < max))) {
                        startMax = -1; 
                        max = 0; 
                        min = int.MaxValue; 
                        //head = i; 
                        currentCount = 0; 
                        continue;
                    }
                }

                max = (startMax == 1) ? Math.Max(max, arr[tail]) : Math.Max(max, arr[head]);
                min = (startMax == 1) ? Math.Min(min, arr[head]) : Math.Min(min, arr[tail]);
                head++; 
                tail--; 
                currentCount++;
                maxCount = (currentCount >= maxCount) ? currentCount : maxCount;
            }
        }
        Console.WriteLine("Max Length = " + maxCount);
    }
    public static void Main(string[] args)
    {
        getMaxLength(new int[] { 20, 5, 7, 2, 11, 55, 9, 26, 48, 22, 12 }); // Expected 4
        getMaxLength(new int[] { 20, 5, 7, 2, 11, 55, 9, 26, 48, 22, 10 }); // Expeced 3
        getMaxLength(new int[] { 10, 5, 100, 2, 70, 3, 60, 1, 99, 4, 66 }); // expected 1

        getMaxLength(new int[] { 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4 }); // Expcted 4


    }

It fails for the following inputs

{ 5, 50, 6, 35, 0, 1, 2, 7, 45, 4, 30, 40, 41, 60, 3 });
{ 6, 50, 7, 35, 1, 2, 3, 8, 45, 5, 30, 40, 41, 60, 4 }
Expected Answer is : 4
Actual Answer is : 3

This seems working. Riku, can you provide subjective description of the solution

O(n^3) is obvious answer. I think interviewer is looking for a better solution (O(n^2) or more better), with the use of hint that all numbers in the sequence are unique

Here is my code in C#

public static void RemoveDupChars(ref char[] str)
        {
            bool[] found = new bool[256];
            int tailIndex = 0;
            for (int index = 0; index < str.GetUpperBound(0); index++)
            {
                if (found[str[index]])
                {
                    continue;
                }

                found[str[index]] = true;
                
                if (index > tailIndex)
                {
                    str[tailIndex] = str[index];
                }
                tailIndex++;
                
            }

            Array.Resize(ref str, tailIndex);

        }

n is number of nodes in the tree

int height(Tree n)
{
  if n == null return 0;
  return max(height(n.left), height(n.right)) + 1;
}

int count(Tree n)
{
  if n == null return 0;
  return count(n.left) + count(n.right)) + 1;
}

bool isFullTree(Tree t)
{
  int h = height(t);
  int count = count(t);
 return 2^h -1 == count

}

Here is a simplified C# code. Essentially we rotate each level recursively.
We calculate the minIndex and MaxIndex of the level. This makes writing the code for rotation very easy

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    ///  Write code to rotate a square matrix:
     /// </summary>
    /// <author>Pramod Kumar Chandoria</author>
    class RotateSquareArray
    {
        public static void Main(string[] arg)
        {
            int[,] a = new int[4,4] {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
            Console.WriteLine("Printing array before rotate");
            printArray(a);
            rotateArray(a, 0, a.GetUpperBound(0) + 1);
            Console.WriteLine("Printing array after rotate");
            printArray(a);

            a = new int[3, 3] { { 1, 2, 3}, { 4, 5, 6, }, { 7, 8, 9} };
            Console.WriteLine("Printing array before rotate");
            printArray(a);
            rotateArray(a, 0, a.GetUpperBound(0) + 1);
            Console.WriteLine("Printing array after rotate");
            printArray(a);
        }

        private static void printArray(int[,] a)
        {
             for (int i = 0; i <= a.GetUpperBound(0); i++)
            {
                for (int j = 0; j <= a.GetUpperBound(1); j++)
                {
                    Console.Write(a[i, j] < 10 ? "  " : " ");
                    Console.Write(a[i, j]);
                  
                }

                Console.WriteLine();
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="array">array in question to roate</param>
        /// <param name="minIndex">minimum index of the level in question to rotate</param>
        /// <param name="levelWidth">width of the level, essentially size of the square we are rotating</param>
        internal static void rotateArray(int[,] array, int minIndex, int levelWidth)
        {
            if (levelWidth <= 1)
            {
                return;
            }

            int maxIndex = minIndex + levelWidth - 1;

            // Rotate Left column
            var topCorner = array[minIndex, minIndex];
            for (int x = minIndex; x < maxIndex; x++ )
            {
                array[x, minIndex] = array[x + 1, minIndex];
            }

            // Rotate bottom Row
            for (int y = minIndex; y < maxIndex; y++)
            {
                array[maxIndex, y] = array[maxIndex, y + 1];
            }

            // Rotate Right column
            for (int x = maxIndex; x > minIndex; x--)
            {
                array[x, maxIndex] = array[x - 1, maxIndex];
            }

            // Rotate Top Row
            for (int y = maxIndex; y > minIndex; y--)
            {
                array[minIndex, y] = array[minIndex, y - 1];
            }

            array[minIndex, minIndex + 1] = topCorner;

            rotateArray(array, minIndex + 1, levelWidth - 2);
        }
    }
}

1. For given group size take two var min and max index
2. reverse array elements between min and max by swapping from the end
3. Increase min and max by group size and repeat step 2 till we reach the end

Check for boundary condition when actual size will be less then group size if array size is not multiplier of the group size

This works and here is C# code for it

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    /// There are three threads in a process. The first thread prints 1 1 1 …, 
    /// the second one prints 2 2 2 …, and the third one prints 3 3 3 … endlessly.
    /// How do you schedule these three threads in order to print 1 2 3 1 2 3 …? 
    /// </summary>
    /// <author>Pramod Kumar Chandoria</author>
    public class ThreeThreadsInSync
    {
        private static object Lock = new object();
        internal static int State = 1;
        public static void Main(string[] arguments)
        {
            var task1 = new Thread(MethodA);
            var task2 = new Thread(MethodB);
            var task3 = new Thread(MethodC);
            task1.Start();
            task2.Start();
            task3.Start();
        }

        internal static void MethodA()
        {
            while(true)
            {
                if (State == 1)
                {
                    lock (Lock)
                    {
                        State = 2;
                        Console.Write("1 ");
                    }
                }
            }

        }
        internal static void MethodB()
        {
            while (true)
            {
                if (State == 2)
                {
                    lock (Lock)
                    {
                        State = 3;
                        Console.Write("2 ");
                        Thread.Sleep(100);
                    }
                }
            }

        }
        internal static void MethodC()
        {
            while (true)
            {
                if (State == 3)
                {
                    lock (Lock)
                    {
                        State = 1;
                        Thread.Sleep(1000);
                        Console.Write("3 ");
                    }
                }
            }

        }
    }


}

not an answer for the given problem

Looks like Trie is the right solution, above solution is one level of trie

I think we can solve this problem like this
For simplicity Lets assume that given words are only alphabetical words, we can expand it further no other characters. Also assume that all alphabets are lower case. We can amend algo to accommodate both case.

Two words can be palindrome combined if start char of one is same as end char of another word. Here Idea is create 2 Maps, one for the start char of each word and another for end char of each word.If there are more then one words with same start or end char then they should be stored in the linked list for same key.

Pseudo code:

1. Take two map. Key of the map is char and Value is a list with each node containing a word

2. Iterate through the given array of words

3. For each word, create entry in the first Map for the first char of the word
e.g. for word "pramod" add key value p -> pramod

4. Also create entry in second map for the last char of the word
e.g. for word "pramod" add key value d -> pramod

These steps will complete in O(n) time

5. Now lets iterate through all Keys of the First Map

6. For each key found, get its corresponding value list e.g. key "p" with value "pramod", "praveen" "prime"

7. Iterate over each word in the list for key "P"
Check last char of the value e.g. "d" here for "pramod"

8. Look for the entry in another map with key "d"
8.1 If entry not found there is no possibility of palindrome for this word, just skip it
8.2 If entry found then look for the palindrome property of the word in second dictionary.
8.2.1 If both are the match then save it into the result

O(n) to iterate through all keys
For each key we are comparing only with words which ends by same char so discarding everything else. This is reducing the comparison from O(n2) to O(n) best case. However in worst case it can turn out to O(n2). Eg if all words given starts with 'p' and ends with 'd'

I am thinking if we can further improve this algo to make it work O(n) for worst case
I am ignoring O(k) which is implicit here when words are compared for palindrome

Please point out any mistake in algo or computation of complexity

This can be done without creating the tree

1. Traverse each Key in the Map
{
    1. For the key, find corresponding value
    2. Increase count for the value in the output Map
   3. Search Map by value(manager of Key) to find it's parent - Repeat this step till we    reach to the root and increase the count for each parent found of the way
}

This solution will change the original tree. Is there a way without changing original tree

Approach
1. Check Left and right sub tree of the root recursively if they are identical.

bool IsFoldable(Tree t)
{ 
   return t !=null && recursiveSameTree(t.left, t.right);
}
bool recursiveSameTree(Tree  t1, Tree t2)
{
  if (t1 == null && t2 == null )
  {
     return true;
  }
  if (t1 == null || t2 == null )
  {
     return false;
  } 

  return recursiveSameTree(t1.left, t2.left) && recursiveSameTree(t1.right, t2.right) 
}

Traverse the tree using Breadth First approach.
On each level print the element, Print should be reversed on each level to have zigzag effect

/// <solution>
/// For each node , if we know right and left sub tree satisfy the criteria, we increment the count.
/// If self node also satisfy the criteria we retun true to parent node to account that for counting
/// Algoritham: Traverse each node's left and right child recursively to know the min Left child and max Right child value.
/// If the min and max value are in the range [x,y] we increase count by one.
/// If self value is in range of [x,y] return true to parent that we all are in range
///
/// </solution>

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    /// Problem:
    /// Given a Binary search tree of integer values, return the count of nodes where
    /// all the nodes under that sub-tree lies between a given range [x, y]. 
    /// Assume there are more than 100,000 nodes
    /// </summary>
    /// 
    /// <solution>
    /// For each node , if we know right and left sub tree satisfy the criteria, we increment the count. 
    /// If self node also satisfy the criteria we retun true to parent node to account that for counting
    /// Algoritham: Traverse each node's left and right child recursively to know the min Left child and max Right child value.
    /// If the min and max value are in the range [x,y] we increase count by one.
    /// If self value is in range of [x,y] return true to parent that we all are in range
    /// 
    /// </solution>
    /// <author>
    /// Pramod Kumar Chandoria
    /// </author>
    public class BSTNodeCountByRange
    {
        public static int CountNodeBySubTreeValueInGivenRange(Node tree, int minRange, int maxRange)
        {
            int count = 0;
            recusiveCountNode(tree, minRange, maxRange, ref count);
            return count;
        }

        private static bool recusiveCountNode(Node tree, int minRange, int maxRange, ref int count)
        {
            if (tree == null)
            {
                return true;
            }
            bool isLeft = recusiveCountNode(tree.left, minRange, maxRange, ref count);
            bool isRight = recusiveCountNode(tree.right, minRange, maxRange, ref count);
            if ( isLeft && isRight)
            {
                if (tree.left != null || tree.right != null) // This check to avoid counting leaf nodes
                {
                    count++;
                }
                if (tree.data >= minRange && tree.data <= maxRange)
                {
                    return true;
                }
            }
            return false;
        }

        public static void Main(string[] args)
        {
            var count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(null, 100, 100);
            Console.WriteLine("Null tree expected count 0, actual count is:" + count);

            Node tree = new Node(5);
            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 3);
            Console.WriteLine("Tree with only 1 node (5) for range [1,3], expected 0, actual count  is:" + count);

            tree = new Node(4);
            tree.left = new Node(2);
            tree.right = new Node(6);
            tree.left.left = new Node(1);
            tree.left.right = new Node(3);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 3);
            Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,3], expected 1, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 6);
            Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,6], expected 1, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 6, 6);
            Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,6], expected 0, actual count  is:" + count);

            tree = new Node(20);
            tree.left = new Node(10);
            tree.right = new Node(25);
            tree.left.left = new Node(5);
            tree.left.right = new Node(16);
            tree.left.right.left = new Node(14);
            tree.left.right.right = new Node(18);

            tree.right.left = new Node(24);
            tree.right.right = new Node(30);
            tree.right.right.left = new Node(28);
            tree.right.right.right = new Node(40);
            tree.right.right.right.left = new Node(35);
            tree.right.right.right.right = new Node(45);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 24, 45);
            Console.WriteLine("Tree with range [24, 45], expected count is 3, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 35, 45);
            Console.WriteLine("Tree with range [35, 45], expected count is 1, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 14,18);
            Console.WriteLine("Tree with range [14, 18], expected count is 1, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 5, 18);
            Console.WriteLine("Tree with range [5, 18], expected count is 2, actual count  is:" + count);
            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 4, 46);
            Console.WriteLine("Tree with range [4, 46], expected count is 6, actual count  is:" + count);

 
        }
    }

    public class Node
    {
        public Node(int data)
        {
            this.data = data;
            left = right = null;
        }

        public Node left;
        public Node right;
        public int data;
    }
}

what about the leaf nodes, I assume they will not be counted but want to make sure

Approach: Keep two List for Inorder traversal of each tree. Traverse both tree in inorder parallel and keep updating the inorder list. Whenever adding new element, check top of the small is same to corresponding larger list. Break early whenever inorder is not same.
In the worst case list size will grow as many number of nodes in both tree.
In best case it will detect as early possible without much memory usage.

Here is the C# code with Test driver

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    /// Given two binary trees ( not BST) ,   return true if both of them have same inorder  else return false.
    /// Approach: Keep to List for Inorder traversal of each tree. Whenver adding new element, check top of the small is same to corresponding larger list.
    /// Break early whenever inorder is not same. In the worst case list size will grow as many number of nodes in both tree. 
    /// In best case it will detect as early possible without memory usage.
    /// Author: Pramod Kumar Chandoria
    /// </summary>
    public class Node
    {
        public Node(int data)
        {
            this.data = data;
            left = right = null;
        }

        public Node left;
        public Node right;
        public int data;
    }
    public class SimilarInorderTree
    {
        public static void Main(string[] args)
        {
            var areSame = SimilarInorderTree.TreeWithSameInorder(null, null);
            Console.WriteLine("Null tree expected same, actual result is:" + areSame);

            Node tree1 = new Node(5);
            Node tree2 = new Node(5);
            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree with only 1 same node are expected same, actual result is:" + areSame);

            tree1 = new Node(4);
            tree1.left = new Node(2);
            tree1.right = new Node(6);
            tree1.left.left = new Node(1);
            tree1.left.right = new Node(3);

            tree2 = new Node(3);
            tree2.left = new Node(2);
            tree2.right = new Node(4);
            tree2.left.left = new Node(1);
            tree2.right.right = new Node(6);

            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree with same Inorder, but not same structure are expected same, actual result is:" + areSame);

            tree1 = new Node(4);
            tree1.left = new Node(2);
            tree1.right = new Node(6);
            tree1.left.left = new Node(1);
            tree1.left.right = new Node(3);

            tree2 = new Node(3);
            tree2.left = new Node(2);
            tree2.right = new Node(4);
            tree2.left.left = new Node(6);
            tree2.right.right = new Node(6);

            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree NOT same Inorder, are expected NOT same, actual result is:" + areSame);

    
        }

        //
        public static bool TreeWithSameInorder(Node tree1, Node tree2)
        {
            IList<int> inOrder1 = new List<int>();
            IList<int> inOrder2 = new List<int>();
            return SameInorder(tree1, tree2, inOrder1, inOrder2) && inOrder1.Count == inOrder2.Count;
        }

        internal static bool SameInorder(Node tree1, Node tree2, IList<int> inOrder1, IList<int> inOrder2)
        {
            
            int topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);
            
            if (tree1 == null && tree2 == null)
            {
               return topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
            }

            bool isMinTopSame = false;
            if (tree1 != null && tree2 != null)
            {
                if (!SameInorder(tree1.left, tree2.left, inOrder1, inOrder2))
                {
                    return false;
                }

                //topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);

                //isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
                //if(!isMinTopSame)
                //{
                //    return false;
                //}

                inOrder1.Add(tree1.data);
                inOrder2.Add(tree2.data);
                topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);
                //topIndex++;
                isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
                if (!isMinTopSame)
                {
                    return false;
                }

                return SameInorder(tree1.right, tree2.right, inOrder1, inOrder2);
            }

            // One tree is null;
            isMinTopSame = tree1 != null ? SameInorder(tree1.left, null, inOrder1, inOrder2) : SameInorder(null, tree2.left, inOrder1, inOrder2);
                
            if (!isMinTopSame)
            {
                return false;
            }
                
            if (tree1 != null) 
            {
                inOrder1.Add(tree1.data);
            } 
            else 
            {
                inOrder2.Add(tree2.data);
            }

            topIndex = Math.Min(inOrder1.Count -1, inOrder2.Count -1);
            isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
            if (!isMinTopSame)
            {
                return false;
            }

            return (tree1 != null ? SameInorder(tree1.right, null, inOrder1, inOrder2) : SameInorder(null, tree2.right, inOrder1, inOrder2));
        }

    }
}

here you go http : //ideone.com/U6YVpR

Forgot to handle the case when destination and gray point are same.

I have written code to confirm whether metric contains a path via gray point. However it is not able to print the path found.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    /// <p>There is a matrix which contains white cells , black cells and  only one gray cell, need to go from (0,0) to (N-1, N-1) 
    /// if Array[N][N]
    /// <br>constraints: 
    /// <br>a. The path should cover only white cells and should go via grey cell.
    /// <br>b. The node once visited cannot be visited again. 
    /// <br>
    /// <br>White cells are represented by 0, black cells by 1 and grey cell by 2.</p>
    /// @Author : Pramod Kumar Chandoria
    /// </summary>
    public class MetrixPath
    {
        public static bool FindPath(Cell[,] array, int destination)
        {
            var queue = new Queue<Cell>();
            bool midPointVisited = false;
            //var path = new List<Cell>();
            Cell lastSplit = null;

            EnqueCell(queue, array[0, 0], destination);
            while (queue.Count > 0)
            {
                var cell = queue.Dequeue();
                if (cell.x == destination && cell.y == destination)
                {
                    if (midPointVisited)
                    {
                        Console.WriteLine("Path found via gray point");
                        return true;
                    }
                    else  
                    {
                        continue;
                    }
                }
                else if (cell.value == 2)
                {
                    midPointVisited = true;
                }

                int count = queue.Count();
                if (cell.x < destination)
                {
                    EnqueCell(queue, array[cell.x + 1, cell.y], destination);
                }
                if (cell.y < destination)
                {
                    EnqueCell(queue, array[cell.x, cell.y + 1], destination);
                }
                if (cell.x > 0)
                {
                    EnqueCell(queue, array[cell.x - 1, cell.y], destination);
                }
                if (cell.y > 0)
                {
                    EnqueCell(queue, array[cell.x, cell.y - 1], destination);
                }
            }

            Console.WriteLine("Path not found");
            return false;
        }

        public static void EnqueCell(Queue<Cell> queue, Cell currentCell, int destination)
        {
            if (currentCell.x <= destination 
                && currentCell.y <= destination 
                && !currentCell.visited 
                && currentCell.value > 0 
                && currentCell.value < 3)
            {
                currentCell.visited = true;
                queue.Enqueue(currentCell);
            }
        }

    }
    public class Cell
    {
        internal bool visited;
        internal int x;
        internal int y;
        internal int value;
    }

    public class TestMatrixPath
    {
        public static void Main(string[] args)
        {
            int[,] intArray = new int[4, 4] { 
                                                { 1, 1, 1, 0 }, 
                                                { 1, 1, 2, 1 }, 
                                                { 1, 0, 0, 1 }, 
                                                { 1, 1, 0, 1 } 
                                            };
            intArray = new int[4, 4] { 
                                        { 1, 1, 2, 1 }, 
                                        { 1, 1, 0, 1 }, 
                                        { 1, 0, 0, 1 }, 
                                        { 1, 0, 0, 1 } 
                                    };
            Cell[,] array = new Cell[4, 4];
            for (int i = 0; i < 4; i++ )
            {
                for (int j = 0; j < 4; j++)
                {
                    array[i, j] = new Cell { value = intArray[i, j], visited = false, x = i, y = j };
                }
            }
            MetrixPath.FindPath(array, 3);
        }
    }
}

this code is incorrect. Also what is the impl of getPath()?

Here is console output of this program

56789= Fifty Six Thousand Seven Hundred Eighty Nine
1000= One Thousand
1= One
0= Zero
20= Twenty
100= One Hundred
111= One Hundred Eleven
999,999,999= Ninty Nine Crore Ninty Nine Lakh Ninty Nine Thousand Nine Hundred N
inty Nine
-999,999,999= Number supported between 0 to 999,999,999
1999,999,999= Number supported between 0 to 999,999,999
Press any key to continue . . .

Here is my solution, assuming printing it using Indian Number (Lakh, Crore)
It can be converted to Million/Billion convention, keeping same concept

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    /// Given a number give its english form
    /// Max number is: 999, 999, 999
    /// Author: Pramod Kumar Chandoria
    /// </summary>
    public class NumberToWord
    {
        private IDictionary<int, string> mUnitByIndex = new Dictionary<int, string> {{2, ""}, {3, " Hundred "},{5, " Thousand "}, {7, " Lakh "}, {9, " Crore "}};
        private IDictionary<int, string> mNumberBetween11To19 = new Dictionary<int, string> {{1, "Eleven"},{2, "Twelve"}, {3, "Thirteen"}, {4, "Fourteen"}, {5, "Fifteen"},{6, "Sixteen"}, {7, "Seventeen"}, {8, "Eighteen"}, {9, "Ninteen"}};
        private IDictionary<int, string> mTenNumberWordMap = new Dictionary<int, string> {{1, "Ten"},{2, "Twenty"}, {3, "Thirty"}, {4, "Fourty"}, {5, "Fifty"},{6, "Sixty"}, {7, "Seventy"}, {8, "Eighty"}, {9, "Ninty"}};
        private IDictionary<int, string> mUnitNumberWordMap = new Dictionary<int, string> { { 0, "Zero" }, { 1, "One" }, { 2, "Two" }, { 3, "Three" }, { 4, "Four" }, { 5, "Five" }, { 6, "Six" }, { 7, "Seven" }, { 8, "Eight" }, { 9, "Nine" } };

        
        public string ToWord(int number)
        {
            int n = number;
            if (n < 0 || n > 999999999)
            {
                return "Number supported between 0 to 999,999,999";
            }

            if (n < 10)
            {
                return mUnitNumberWordMap[n];
            }
            String sNumber = "";
            IList<short> numbers = new List<short>();
            int index = 0;
            int lastDigit = 0;
            while (n > 0)
            {
                index++;
                int currentDigit = n%10;
                if (index == 1)
                { 
                    // NO OOP
                }
                else if (index == 2)
                {
                    sNumber = getWordByTwoDigit(currentDigit, lastDigit) + " " + sNumber;
                }
                else if (index == 3)
                {
                    if (currentDigit > 0)
                    {
                        sNumber = mUnitNumberWordMap[currentDigit] + " Hundred " + sNumber; // TODO: Add AND
                    }
                }
                else if (index %2 == 0) {
                    // Do something only if last unit
                    if (n < 10)
                    {
                        sNumber = mUnitNumberWordMap[currentDigit] + mUnitByIndex[index + 1] + sNumber;
                    }
                 }
                else
                {
                    sNumber = getWordByTwoDigit(currentDigit, lastDigit) + mUnitByIndex[index] + sNumber;
                }

                lastDigit = currentDigit;
                n = n / 10;
            }

            return sNumber;
        }

        private string getWordByTwoDigit(int unit, int lastDigit)
        {
            if (unit == 0)
            {
                if (lastDigit > 0)
                {
                    return mUnitNumberWordMap[lastDigit];
                } else {
                    return "";
                }
            }
            if (unit == 1)
            {
                return mNumberBetween11To19[lastDigit];
            }
            var result = mTenNumberWordMap[unit];
            if (lastDigit > 0)
            {
                result += " " + mUnitNumberWordMap[lastDigit];
            }
            return result;
        }

        static void Main(string[] args)
        {
            var nToW = new NumberToWord();
            Console.WriteLine("56789= " + nToW.ToWord(56789));
            Console.WriteLine("1000= " + nToW.ToWord(1000));
            Console.WriteLine("1= " + nToW.ToWord(1));
            Console.WriteLine("0= " + nToW.ToWord(0));
            Console.WriteLine("20= " + nToW.ToWord(20));
            Console.WriteLine("100= " + nToW.ToWord(100));
            Console.WriteLine("111= " + nToW.ToWord(111));
            Console.WriteLine("999,999,999= " + nToW.ToWord(999999999));
            Console.WriteLine("-999,999,999= " + nToW.ToWord(-999999999));
            Console.WriteLine("1999,999,999= " + nToW.ToWord(1999999999));
        }
    }
}

It can be solved using recursive approach

class MaxPathTriangleMetrix
    {

        int[][] Matrix = new int [5][];

        public MaxPathTriangleMetrix()
        {
            InitializeMatrix();
        }

        public void PrintMaxPath()
        {
            List<string> path = new List<string>();
            path.Add("Start at " + Matrix[0][0]);
            Console.WriteLine("Max path weight is :" + GetPathWeight(0, 0, path));
            string msg = string.Empty;
            foreach(string move in path)
            {
                Console.WriteLine(move);
            }
        }
        private int GetPathWeight(int row, int col, List<string> path)
        {
            if ((row + 1) == Matrix.GetLength(0))
            {
                return Matrix[row][col];
            };
            List<string> path1List = new List<string>();
            List<string> path2List = new List<string>();
            int path1 = GetPathWeight(row + 1, col, path1List);
            int path2 = GetPathWeight(row + 1, col + 1, path2List);
            if (path1 > path2)
            {
                path.Add("Move to " + Matrix[row + 1][col]);
                path.AddRange(path1List);
                return path1 + Matrix[row][col];
            } else
            {
                path.Add("Move to " +Matrix[row + 1][col + 1]);
                path.AddRange(path2List);
                return path2 + Matrix[row][col];
            }

        }

        public void PrintMatrix()
        {
            for(int row = 0; row < 5; row++)
            {
                for (int column = 0; column <= row; column++)
                {
                    Console.Write(Matrix[row][column] + ", ");
                }
                Console.WriteLine();
            }
        }

        private void InitializeMatrix()
        {
            var rand = new Random(DateTime.Now.Millisecond);
            for(int row = 0; row < 5; row++)
            {
                Matrix[row] = new int[row + 1];
                for (int column = 0; column <= row; column++)
                {
                    Matrix[row][column] = rand.Next(1, 10);
                }
            }
        }
    }

what will happen in case of
a="xayyz"
b="xyz"
will you skill when you encounter the y after y?
I think skipping is possible only on start boundary,

What if a="xayyzxybcd as here answer is zyx
means we also need to check from each start found

And This is optimized solution

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FindMaxSequence(new int[] { 2, 1, 5, 3, 1, 7, 9, 8, 2, 8 }));
            Console.WriteLine("Count=" + called + " for n=10");
            called = 0;

            Console.WriteLine(FindMaxSequence(new int[] { 8, 1, 1, 3, 1 }));
            Console.WriteLine("Count=" + called + " for n=5");
            called = 0;

            Console.WriteLine(FindMaxSequence(new int[] { 9, 2, 8, 1 }));
            Console.WriteLine("Count=" + called + " for n=4");
            called = 0;
            
            var sequence = new int[]
                                 {
                                     1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 3, 3, 4, 5, 6, 7, 8, 9, 6, 5, 3, 2, 1, 4, 4, 100,
                                     12, 1, 34, 45
                                 };
            Console.WriteLine(FindMaxSequence(sequence));
            Console.WriteLine("Count=" + called + " for n=" + sequence.Length);
            called = 0;

        }

        static int FindMaxSequence(int[] sequence)
        {
            int secondSum = 0;
            int firstSum = 0;
            FindMaxSequence(sequence, 0, out firstSum, out secondSum);
            return Math.Max(firstSum, secondSum);
        }

        
        static int called = 0;
        /// <summary>
        /// Contributed by Pramod Chandoria
        /// We will devide the problem and solve it recursively
        /// </summary>
        /// <param name="sequence"></param>
        /// <param name="startIndex"></param>
        /// <param name="firstSum"></param>
        /// <param name="secondSum"></param>
        static void FindMaxSequence(int[] sequence, int startIndex, out int firstSum, out int secondSum)
        {
             called++;
            int elements = sequence.Length - startIndex;
            if (elements <=0)
            {
                secondSum = 0;
                firstSum = 0;
                return;
            }
            
            if (elements == 1)
            {
                secondSum = 0;
                firstSum = sequence[startIndex];
                return;
            }
            else if (elements == 2)
            {
                secondSum = sequence[startIndex + 1];
                firstSum = sequence[startIndex];
                return;
            }

            FindMaxSequence(sequence, startIndex + 2, out firstSum, out secondSum);
            firstSum = sequence[startIndex] + Math.Max(firstSum, secondSum);
            secondSum = sequence[startIndex + 1] + secondSum;

            return;
        }

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FindMaxSequence(new int[] { 8, 1, 1, 3, 1 }));
            Console.WriteLine(FindMaxSequence(new int[] { 2,1,5,3,1,7,9,8,2,8 }));
            Console.WriteLine(FindMaxSequence(new int[] { 9,2,8,1 }));
        }

        /// <summary>
        /// Contributed by Pramod Chandoria
        /// We will devide the problem and solve it recursively
        /// </summary>
        /// <param name="sequence"></param>
        /// <param name="startIndex"></param>
        /// <returns></returns>
        static int FindMaxSequence(int[] sequence, int startIndex = 0)
        {
            int elements = sequence.Length - startIndex;
            if (elements <=0)
            {
                return 0;
            }
            
            if (elements == 1)
            {
                return sequence[startIndex];
            }
            int max1 = FindMaxSequence(sequence, startIndex + 1);
            int max2 = sequence[startIndex] + FindMaxSequence(sequence, startIndex + 2);
            return Math.Max(max1, max2);
        }
    }

What is the cause of behind schedule?
Wrong estimate - Increasing the resources to fill in the gap
External dependency - Was this risk identified already. Communicate now
Less resources: Engage more resources
something else?

Is it okay to deliver little late, or time is critical?

@D3^!L Can you please help to point out any one example which will be left in this method

Which is O(n^2 log n) solution. The top answer makes some extra assumptions?

This is correct answer
By sorting on second element of pair, we are making sure that we choose the one which finish early and that gives max window to select next optimum pair. It does not matter when it started but it matter most when it finished. When started matter when we have to select next pair from sorted group so it should just be good enough to start from where previous one stopped

I think this is correct answer
Just check minimum height of child left and right tree recursively. For each node the complete tree depth would be the min heights of left and child node

Say we are looking for a + b + c + d = x
1. Sort the array
2. Iterate over each element of the sorted array as a
Iterate over each element of the array which is right to the a, as b
For remaining array right side of b, take two pointers from front and back
Check if c (front) + d (back) = x - a- b
if yes then you got the answer
if no and if c+d is smaller then move front pointer
if no and if c+d is greater then move back pointer

Time Complexity:
n logn for sorting the array
n*n*n for searching the sum
O(n^3) is the complexity

No extra space is required

This will fail with smaller numric list followed by longer apphabetic list

Won't this algorithm fail for this input
1->2->a->b->c->d->3->4->5->e->f->null
From 2 node, you will traverse to a with a circular link list created

It is not that easy, you need to also consider when first Numeric list will reach to alphanumeric list

1. 5 Group of 5 horses, We eliminate 2*5 = 10 horses, 15 left
2. 3 Group of 5 horses, We eliminate 2*3 = 6 horses , 9 left
3. Race one group of 5 horses, 3 left, and total 4+3 == 7 left
4. Race one group of 5 horses to eliminate 2 horses and we are left with 5 horses
5. One more race and all 3 top mighty horses are known to you
So total minimum race required 5+ 3 + 1+ 1 + 1 = 11
Cheers

I think it is good , just PersonNameList is not being used anywhere

It require O(n) memory space

Can we take advantage of the fact that atleast one number must be negative.
say a + b + c = 0 and a = - (b+c);
say a is negative here. Then we search for combination of b and c such that summation is equal to negative of a. However our search is limited only for number of -ve number in the list. If list does not contain any negative number we probably can exit at start.

I am thinking we first sort the list
Then for each negative number do a search in nlog(n) time for the two number
O(n log n) + O(number of negative numbers * nlog(n))
= O(number of negative numbers * nlog(n))
For less number of negative numbers, this should work even better as O(nlogn), for large number of negative it should be O(n2)

Any comment