Software Engineering Interview Questions - 11

Q1. Give an algorithm to serialize a binary tree into stream, and then reconstruct the binary tree from the stream.

Hint:  a) If binary tree is in array, we can serialize ans deserialize in a straight forward manner. 

         b) Preorder and Inorder traversal.

         c) Serialize using pattern {parent} {left subtree} {right subtree} recursively.

Q2.  Print all the M size combinations of a N size set in a sequence such that each set of the sequence can be obtained from its preceding set by removing one element and adding a new element. 

Q3. Find all the duplicates in a given Binary Search Tree without using any extra space. 

Hint: Use an inorder traversal and match the current node with the last node to check if they are duplicates.

Q4. Given a list of numbers A= {5, 10, 15, 20, 21, 23} and associated probability of occurrence P={ 0.1, 0.3, 0.05. 0.13, 0.02,  0.4} such that sum(P[i]) = 1, construct a Binary Search Tree that minimizes the expected access time of the nodes  given a message having the numbers in A. The cost of access of a node at depth d (the number of comparisons required to access the node at depth d ) is d+1.  Let n be a node at depth d in the BST with probability of occurrence p, then the minimization function is sum(p(n)*(d+1) over all n)

Hint: Use dynamic programming.


Q5. Given two tumblers of capacity 5 (m) liters and 3 (n) liters where m-n=k, design a technique to measure 4 (x) liters.
Note: This is famous as puzzle. Here, we want an actual algorithm to do it.


Q6.Write an algorithm to solve Tower of Hanoi .


Q7.  Given a N x N matrix of numbers, design an  efficient algorithm to perform a 90 degree rotation of the  matrix.

Hint:  Assume matrix A to be made up of layers similar to an Onion. Perform a  layer by layer rotation starting from the outermost layer to the innermost layer. To perform a rotation at a given layer, start from any corner and move the corner elements in clockwise directions by n-1 steps. We start from A[0][0]. We
move as follows:
A[0][0] -> A[n-1][0] -> A[n-1][n-1] -> A[0][n-1] -> A[0][0]
Then move, A[0][1] -> A[n-2][0] -> A[n-1][n-2] -> A[1][n-1] -> A[0][1] and so on.


Q8.  Given a linked list where each node also has a pointer to some arbitrary node in the list, design an algorithm to clone the linked list.


Hint:  Let A be a linked list. Insert a new node in front of the every node of A and copy value from the previous node to create a new linked list B.  Now to copy the arbitrary pointers use following logic

B(Current).Next.Arbitray_Pointer = B(Current).Arbitrary_Pointer.Next

Finally restore the original linked list as follows:

Original_Head = Original_Current = B(Head)
Clone_Head= Original_Current.Next
-- Begin For loop
Clone_Current = Original_Current.Next
Original_Current .Next = Clone_Current .Next
Original_Current  = Original_Current .Next
--End loop


Q9.  Given a histogram, find the maximum area rectangle within the histogram.

Hint: For each bar, the largest rectangle obtained by the bar would be:
 The  height of the bar (h) *
 The maximum left extension without decreasing the bar height  (l) *
 The maximum right extension without decreasing the height of the bar (r) .

To efficiently obtain l and h use following idea of stack.
Initialize a stack with top of the stack, TOS= 0
Compute l as ( i - TOS)

For bar i = 1, l = i - TOS = 1 - 0 = 1
Push bar 1 is the stack, TOS = 1
For bar i = 2,  pop out bars til we find a bar of height smaller than second bar, and recompute TOS
l = i - TOS
...

Similarly compute r.

All this will have a time complexity of O(n)


Q10.  Given an array of integers, design an algorithm to find:
          a) the largest sub-array whose elements can be arranged into a continuous sequence.
          b) the longest continuous sequence.


Hint (b) Sort and then do a linear scan. For fixed interval,  a bitset can be used.