Trilogy Interview of Manmohan

Hi these are the question asked to me in Trilogy Interview.

Hope these questions help you too :D All the best :)

1st Round

Only postorder of bst given regenerate the tree

Approach

Code

Complexity

Optimization improve the order of ur solution

2nd Round

1) Spiral printing n*n matrix not m*n actually discussed for that also but coded for n*n only

2) LCA least common Ancestor

3rd Round

LinkList merging Y shaped find the common point or merging point

char array is given find the first repeating character in the array

eg. char a[ ] = "abcdcad"

return "a" here...not "c"

Reverse link list: Code and explanation of calls made

Test case : when llist contains a loop then it will fail then what will u do

1) Then find the loop

2) Remove the loop then reverse the list using this function

3) Camal Banana puzzle 4000 banana and 1000 km and 1000 banana max limit per trip

What is the maximum number of bananas u can take to the other side.

4) Pure virtual function

5) Sinlgeton class Implementation

6) Diameter of a tree: Code and Complexity

4th Round

1) 1-d array given find the sum of the elements between 2 indices say i and j in constant time

eg. a[] = "1 4 2 5 6 3"

and if i = 2 and j = 4 then it should return the sum 4+2+5 from the array in constant time .

U need to do some preprocessing on array for this

2) Now the same for a 2-d array. Now two indices are given say (i1,j1) and (i2,j2)

Find the sum of elements of the rectangle formed by these indices in constant time again do some preprocessing computation for this and return the result in constant time.

3) check IsBst() check if a binary tree is bst or not

do it in o(n) now

do it in o(n) with o(1) space complexity now

4) 2 candles each burns 1 hr Measure 45 minutes