pc
BAN USER 0of 0 votes
AnswersFind out if there is cycle in Directed graph
 pc in United States Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures  1of 1 vote
AnswersGiven billions of Rectangle, find rectangle with minimum area overlapping to a given point P(x,y)
 pc in United States
There is a simple way to achieve answer in O(n) by processing each rectangle sequentially, but optimize it further provided large number of Rectangle array. Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures  0of 0 votes
AnswersHow to debug deadlock or heap corruption from DUMP using WinDbg tool?
 pc in United States Report Duplicate  Flag  PURGE
Microsoft SDE2 Debugging  0of 0 votes
AnswersDesign classes and interface for BookShelf
 pc in United States Report Duplicate  Flag  PURGE
Microsoft SDE2 design  1of 1 vote
AnswersGiven a file, read last n lines from the file
 pc in United States
string ReadNLines(sttring fileName, int n); Report Duplicate  Flag  PURGE
Microsoft SDE2 Algorithm  0of 0 votes
AnswersImplement Priority Queue
 pc in India Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures  0of 0 votes
AnswersImplement Least Recently Used Cache for IPAddress lookup. Assume max cache size is 1000 but it should scale well with larger number
 pc in India
Key of the cache is server name and value is IPAddress. Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures
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);
}

pc
May 26, 2015 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;
}

pc
May 26, 2015 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;
}

pc
May 26, 2015 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 = len1;
int max = 0; // Max value of smaller subarray
int min = int.MaxValue; // Min value of larger subarray
int currentCount = 0; // Max length subarray for elements starting at index i
int startMax = 1; // 1 = head represents larger subarray ; 2 = tail represents larger subarray
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
}

pc
May 23, 2015 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);
}

pc
May 17, 2015 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
}
 pc May 16, 2015Here 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);
}
}
}

pc
May 16, 2015 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 ");
}
}
}
}
}
}

pc
May 16, 2015 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
}

pc
May 10, 2015 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)
}

pc
May 10, 2015 /// <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 subtree 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;
}
}

pc
May 09, 2015 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));
}
}
}

pc
May 09, 2015 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 (N1, N1)
/// 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);
}
}
}

pc
May 02, 2015 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 . . .

pc
May 02, 2015 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));
}
}
}

pc
May 02, 2015 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);
}
}
}
}

pc
November 05, 2014 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;
}

pc
October 17, 2014 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);
}
}

pc
October 17, 2014 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?
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
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
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
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
Open Chat in New Window
this is wrong algorithm
 pc May 26, 2015