hari@hbiz.in
BAN USER 0of 0 votes
AnswersWhat is the data structure you will use to model Tennis tournament of size number of players n=8. Splitted into 2 groups? What is the complexity of finding the winner and the runner.
 hari@hbiz.in in India Report Duplicate  Flag  PURGE
Synopsys R&D Software Engineer / Developer Data Structures
Not sufficient in this case. Amazon expects us to check for subtrees.
 hari@hbiz.in August 29, 2012Very good point. But preorder testing is required only if you are given the tree in form of list or array. If the tree itself is given, then any one traversal is sufficient with node by node comparison.
 hari@hbiz.in August 27, 2012What is the logic behind checking preorder too?
 hari@hbiz.in August 26, 2012Sorry. It is a binary tree but not a BST
 hari@hbiz.in August 26, 2012typedef struct TNode
{
int value;
TNode *left;
TNode *right;
} TNode;
bool ifExist(const TNode* treeA, const TNode* treeB);
bool isSubtree(const TNode* treeA, const TNode* treeB)
{
if (treeB == NULL)
{
// if treeB is null no point in searching.
return true;
}
bool a_has_b = ifExist(treeA,treeB);
bool b_has_a = false;
// Check only if treeB is not found in treeA.
if (!a_has_b)
b_has_a= ifExist(treeB,treeA);
return a_has_b  b_has_a;
}
bool ifExist(const TNode* treeA, const TNode* treeB)
{
if ( treeA == NULL && treeB != NULL)
{
// We reached the end of path. No subtree found.
return false;
}
if ( treeA == treeB)
{
return CompareTheSubtree(treeA,treeB);
}
return ifExist(treeA>left,treeB) ifExist(treeA>right,treeB);
}
Note : I have not written CompareTheSubtree() method as it is trivial.
 hari@hbiz.in August 26, 2012Travel through tree A, and search for node B if not found, travel through Tree B and search for node A. If you found in either case, compare the elements.
 hari@hbiz.in August 26, 2012Why recursion when the following code can do the same.
K=A;
for ( i=1;i<n;i++)
{
k= K*A;
}
Can somebody throw some explanation here.
 hari@hbiz.in August 16, 2012This is what it doing
Input
4
2 5
1 7
After completing swapping at 2
4
2 5
1 7
Swapping at 4
4
5 2
7 1
Swapping at 2
4
5 2
7 1
This is mirror image of structure but not data.

hari@hbiz.in
August 16, 2012 Say the set N =3 { 1,2,3}
Combinations are {1,2} {2,3} {1,3}
Say the set N= 4 {1,2,3,4}
Combinations are {1,2,3 }, {1,2,4}, {1,3,4}, {2,3,4}
Slightly modified
void verticalSum( TNode* node, int *arr, int Level)
{
if (node==NULL) return;
verticalSum(node>Left,arr, Level1);
arr[Level]=arr[Level]+node>value;
verticalSum(node>Right,arr,Level+1);
}

hari@hbiz.in
August 14, 2012 Solution using a queue and stack. No hack. o(n2)
Convert2DLL(Queue queue,int level, list** head)
{
Queue nextqueue;
Stack stack;
if (queue.empty())
return;
while ( !queue.emtpy() )
{
TNode *node= queue.pop();
if (level%2 == 1)
{
stack.push(node>left);
stack.push(node>right);
}
else
{
nextqueue.push(node>left);
nextqueue.push(node>right);
}
*head>right=node;
node>left=*head;
*head=node;
*head>right=null;
}
if ( level%2 == 1)
{
while ( !stack.empty)
{
node *temp = stack.pop();
nextqueue.push(temp);
}
}
queue = nextqueue;
Convert2DLL(queue,level++, head);
}

hari@hbiz.in
August 14, 2012 No need of 2 digits if we can XOR the a[num] with 1 (assume all the a[elements] initialized with 0) . If at all an XOR with 1 returns a 0, we can assume it is a duplicate and return it. Only thing is we don't know whether a number occurred or not, which is not required in the current case.
 hari@hbiz.in August 12, 2012Can you please help me to understand why do we require 2 bits? A 1 bit array of size 4294967295 is sufficient right?
 hari@hbiz.in August 12, 2012I believe your algorithm won't work or I misunderstood it, can you prove how your algorithm will generate a value 15?
 hari@hbiz.in August 11, 2012Good approach. But when large number of elements checked out, a BST, would give a better performance than linked list.
 hari@hbiz.in August 11, 2012For minheap, we can use a BST.
 hari@hbiz.in August 11, 2012No. Complexity is O(n+m+ (nm) ). Worst case is o(3n.)
 hari@hbiz.in August 10, 2012
RepJennyReimer, Dev Lead at Adobe
Badminton lover, coffee addict, guitarist, International Swiss style practitioner and TDC honorary member. Acting at the nexus of simplicity and ...
RepShastri Ji is well known hindi and tamil vashikaran specialist. He will give you effective and simple totke to control ...
RepSpent 20012006 licensing the elderly in Jacksonville, FL. Spent 20012004 consulting about Break Up Spell. Spent two years deploying crickets ...
RepWilliamDGiles, Cloud Support Associate at ADP
Spent 20012006 creating marketing channels for tar worldwide. Was quite successful at building tobacco for farmers. Won several awards for ...
RepSoccer lover, coffee addict, guitarist, International Swiss style practitioner and TDC honorary member. Acting at the nexus of simplicity and ...
RepRichardWParks, Accountant at ADP
Open Chat in New Window
knock outs
 hari@hbiz.in September 26, 2012