Category Archives: Interviews

How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.

For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]

The algorithm here is simple. 
  • Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
  • Do the following until we reach the end of any sequence.
  • If both the elements are same, increment both indices.
  • Otherwise increment j only.

At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!

Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.

Finding the pivot element

Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it.

For example in the array [1, 2, 3], the pivot element is 2, as all the elements to the left of it are less than 2, and all the elements to the right of it are greater than 2.

The array [6, 9, 1, 2, 4] does not contain any pivot element.

Simple brute force solution:

For each element, check if all the left elements are smaller, and all the right elements are bigger. If there exists any such element we return it’s index, otherwise we return -1.
But this solution takes O(n2) time.

Is there any better approach? Can we do it in O(n) time probably using extra space?

Yes, it can be done using two extra arrays.
  • One array stores the maximum element seen so far from the left.
  • Second array stores minimum element seen so far from the right

For example for the array [6, 9, 1, 2, 4]
Prefix maximum: [6, 9, 9, 9, 9]
Suffix minimum: [1, 1, 1, 2, 4] 

We first calculate the above two arrays. In the next iteration, For each element in the array, we check if the maximum element in the left is lesser, and the minimum element in the right is greater than it. If this condition is satisfied we are done. Since checking for maximum element in the left and minimum element in the right takes constant time (O(1)), the overall time complexity of this solution is O(n) and space complexity is O(1).

Below is the C++ implementation of the above. 

Duplicate elements in array at given distance

Given an array of numbers A, which might contain duplicate elements, 

How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k?

Look at the following examples.
1. A = [9, 5, 6, 9, 3, 0, 1], K =3
The answer is “Yes” because 9 is present at index 0, and 3

2. A = [10, 0, 10, 20, 30], K = 1
The answer is “No” because there are no duplicate elements at a distance less than or equal to 1

A simple and straight forward algorithm is to have two loops, the outer loop fixing one element, and the inner loop checks if that element exists within a distance of K. This algorithm runs in O(n2) in worst case.

Let us look at an efficient algorithm using the map data structure. The map stores the element as the key and it’s most recent index as it’s value. Here are the steps.

  • For each element in the array
    • Store the element and it’s index in the map if does not exist already.
    • If already exists, 
      • Check if the difference between the recent index and current index is less than K. 
      • If so return true.
      • Otherwise update the map with recent index

This algorithm runs in O(n log n) time, and take O(n) extra space for the map. Here is the C++ code given below. For the Python implementation checkout this link. For Java implementation check this link.

Mirror-2Bimage-2Bbinary-2Btree

Mirror image of a binary tree

Given a binary tree, how to convert it to it’s mirror image?
For example consider the following binary tree and it’s mirror image.

Here simply, the left and right sub trees of each node are inverted. So we have to simply invert the given binary tree. It is a simple implementation problem. Using recursion we can solve it by following the below steps

  1. If root is NULL, simply return
  2. Invert the left sub tree
  3. Invert the right sub tree
  4. Swap left and right sub trees.

Here is the C++ code which implements the above algorithm. It runs in O(n) time.

Generating all possible parenthesis expressions

Given a number N, how do we generate all possible valid expressions with N pairs of brackets?

For example for N = 2, there are 2 such expressions
()()
(())
For N = 3, there are 5 expressions
((()))
(()())
(())()
()(())
()()()

We have a simple solution to this problem by using recursion. We design this method as follows.

It takes two parameters left count, right count, buffer and an index. At each index we can either fill a left bracket or a right bracket.

As long as we have left brackets, we try to fill them and recursively call the method with one less left brace.


Then we check if we have more right braces than left braces, then fill it up with right brace. Recursively call the method with one less right brace.

When we don’t have any left or right braces remaining, we can print the contents of the buffer.

Here is the Java implementation.

Check if a binary tree is the mirror image of itself

Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree. 
A binary tree is called a symmetric tree if it’s left and right sub-trees are mirror images of each other.

For example Let us consider the following examples of some symmetric and asymmetric trees.

    1
   / Symmetric
  2   2  
    1
   / Asymmetric
  2   3 
      1
     /
    2   2  Symmetric
   /    
  3       3

We can design a recursive algorithm like the following.

  1. An empty tree is a symmetric tree.
  2. At each node we check the following
    1. If the left value and right value are same
    2. If the left sub-tree of left node and right sub-tree of the right node are mirror images
    3. If the right sub-tree of left node and left sub-tree of the right node are mirror images
  3. If all the above conditions are satisfied then the tree is symmetric.

Here is the C++ implementation of this.

Level order traversal of the binary tree from the bottom

Given a binary tree, how do we print the nodes in level order starting from the bottom.

For example for the following tree, the output should be 2 3 1

    1
  / 
 2    3

An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level to minimum level. This is not so efficient, because to print each level we need to traverse all the nodes.

Another solution is that we can modify the level order traversal. We need an additional stack to store the nodes. Instead of printing the values of the nodes as soon as they are deleted from the queue, we can add them to stack. Later, we can pop the elements from the stack and print them. This will print the elements in reverse level order.

Here is the C++ code for the second approach.


Creating a balanced binary search tree from sorted array

Given a sorted array, how do we create binary search which height balanced.

For example the array [1,2,3,4,5] must be transformed to the following binary tree

                           3
                / 
               2    4
              /       
             1        5

We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the left sub-tree should be almost equal to that of right sub-tree.

How do we do it?
 

The create method is provided the lower and higher index parameters in addition to the actual array. We create the root node with the middle element and create the left and right sub trees with the left and right portions of the array.

Here is the C++ code.

Checking if a binary tree is balanced

Given a binary tree, how do we check if it is balanced or not?
We say that a binary tree is balanced if height difference of left  and the right sub-trees is at most 1 at  any node.

Consider the following examples

  1          1               1             1
 /                       /              
2   3          2           2                 2
                                           /
                                          3
Balanced    Balanced     Balanced       Unbalanced

Solution:

We can simply implement a recursive solution based on the above definition of balance. At each node we check the height of the left sub tree and the right sub-tree and call the same function for it’s left child and right child recursively. But this is inefficient because we calculate the height repeatedly. This solution is O(n2).

Because we are calculating the height at each node, we can reuse the height of sub-tree to check the balance at the root node. Here is how we can do it. 

We write a method called balance. This method returns the actual height of the tree if it is balanced. Otherwise it returns -1. So at any point if the balance of left or right sub-tree is -1 or their difference is greater than 1, we can simply return false.

Here is the C++ implementation of this algorithm. It runs in O(n) time.

Binary-2Bsearch-2Btree

Finding the kth element in Binary search tree

Given a binary search tree, how do we find a kth smallest or kth largest element?
For example, given the following binary search tree.
Third largest element is 6
Second smallest element is 2
Fifth largest element is 5 and so on…

Solution:


We can solve this problem by modifying the the in-order traversal method of a binary tree. In addition to the root node, we can pass two more parameters one is K, and current count of the nodes visited as a reference parameter. When the current count reaches K we found the kth order element.

To find out the kth smallest element, we need to visit left sub-tree, then root and then the right sub-tree as usual. To find the kth largest element we need to do reverse in-order traversal i.e First visit right sub-tree, then root and then the left sub-tree.

Here is the C++ implementation. This includes the recursive and iteration versions of finding kth smallest and kth largest elements. The iterative version is simply the manual implementation of a recursion using a stack.