ps
 0of 0 votes
AnswersGiven an nary tree, find the closest common ancestor ? Discuss the time complexity and write testcases.
 ps on April 24, 2012 in United States Edit  Report Duplicate  Flag
Microsoft Software Engineer in Test Trees and Graphs  0of 0 votes
AnswersImplement a stack with 3 operations: push, pop and findmiddle(). At any point in time, findmiddle() should return the middle element of the stack (n/2+1) without popping out the elements. ie. in O(1) time
 ps on April 20, 2012 in United States Edit  Report Duplicate  Flag
Microsoft Software Engineer in Test  0of 0 votes
AnswersWrite a program for binary tree (not BST) where left is connected to right and the whole structure is connected.
 ps on April 16, 2012 in United States Edit  Report Duplicate  Flag
Microsoft Software Engineer in Test Data Structures
Here is my approach :
placing the numbers in the matrix as below :
1 2 3
4 5 6
7 8 9
print the rows : 123 , 456, 789
print the columns: 147, 258, 369
now for the rest of the numbers, there is some kind of a pattern for columns with (1, 2 &3 )
Its permutation of 123(columns )
Example :
for i from 1 to 3 // standard rows
for j in 1 3 2 // taking one of the permute (columns)
print matrix[i][j] // print 168
So get the all permutations of 123 in a list (for example). Do the above for all the elements in the list.

ps
on April 25, 2012 Edit  Flag View
Reply
You have to discuss with the interviewer as how the expression is going to be.
What kind of braces ( { [ ] } )
Whether it contains numbers/ characters
 3a + 2b // legal , a3+b4 // illegal ?
What operators it can have ?
*,+,/,,++,,+,+=,=,*=,/=, ~ . Should you consider the operator precedence ?
Adding ..
Check how many letter/characters you can write
Check if it is too glossy so that your shadow appears on it ?Thats not you want the whiteboard to be.
If you leave the writings on it for days and how easy it is to wipe it off.
check if marker pen is the only thing used to write on it. What happens with pencil/pen ?
How much stress you need to erase?
How can I erase it? What happens with a tissue/paper ?
How heavy it is to be hung on the wall?
Can we have a separate stack for min, max and middle element. So that they all operate on O(1) time . Suppose if, I push(11) to the stack, I add the 1st element to all the 3 stacks. Now, push(5)
 minstack  compares 11 with 5. Since 5 is less than 11, 5 is pushed to the minstack.
 maxstack  compares 11 with 5. since 11>5 , 5 is not pushed onto maxstack.
 middlestack  keep track of the number of elements pushed. when push(5), n=2 (number of elements in stack). middle=2 , so push 5 onto the middle stack.
Please advise if I am wrong. Also, can someone explain me, what happens for a stack with maximum number of elements.
Thanks.
Algorithm:
foreach element in the array
look if element exist in hashmap
if it doesn't exisit
add to hasmap with count as 1
else
if value of that element from hasmap returns 1
update hashmap value to 1 // 1 values will be skipped from adding it to the
//array
increment counter
output array[counter] = array element // ad to the output array
 ps on May 01, 2013 Edit  Flag View Reply