Title: Solving Hard Algorithm Interview Questions

Date and Place:

This is the information for the event:
Start Time End Time Resource List
10/03/13, 7:30PM 10/03/13, 9:30PM G5
10/10/13, 7:30PM 10/10/13, 9:30PM G5
10/17/13, 7:30PM 10/17/13, 9:30PM G5
10/24/13, 7:30PM 10/24/13, 9:30PM G5
10/31/13, 7:30PM 10/31/13, 9:30PM G5
11/07/13, 7:30PM 11/07/13, 9:30PM G5
 

 in ROLCC

Description

Overview

Now it is very common for software companies to ask very tough algorithm related questions during interview regardless you are a fresh grad or not. The purpose of this class is to help you refresh your algorithm knowledge by using a lot of real interview questions compiled from a variety sources, so you become better prepared when your next opportunity comes. The solutions are mostly givens either in C/C++ or java code. We also have some examples for what we will cover in the class in this material.

 

Prerequisite

You should know fundamentals for software programming; Understanding one of programming languages like C/C++, Java or Python is expected.

 

Sample Questions:

Question 1: how to verify a binary search tree?

First, what is a BST? A binary search tree (BST) is a node based binary tree data structure which has the following properties:

1.    The left subtree of a node contains only nodes with keys less than the node’s key.

2.    The right subtree of a node contains only nodes with keys greater than the node’s key.

3.    Both the left and right subtrees must also be binary search trees.

In the above definition, the BST does not have duplicated key nodes, which may not be true always, you should discuss with your interviewer.

 

A simple and incorrect method is to just make sure the left node has value less than the parent node, and the right node has value greater than the parent code, and do this recursively. This is not correct, as it does not work for the following example.

 

                                           10

                                         /      \

                                       5        15

                                             /    \

                                           7      20

                               (This is not a BST).

 

Another method is to find the maximum value of a subtree and then compare it with the parent node and do this recursively for all the nodes. This works but is inefficient as it visits the lower nodes so many times.

 

Solution 1:  Keep track a needed range for a subtree while traveling down the tree.

 

Keep tracks the range a subtree needs to satisfy as we travel down the binary tree and check the current node against the range.  For the root node, the range is wide open, as we travel down, the range gets smaller and smaller.

 

bool  isBST(Node *root, Node *min, Node *max)

{

   if (root == NULL)

           return true;

   if (min != NULL && min->val > root->val)

           return false;

   if (max != NULL && root->val > max->val)

           return false;

 

    /* check left and right subtrees, pay attention to on how   min/max nodes are updated. */

   return isBST(root->left, min, root) &&

               isBST(root->right, root, max);

}

 

bool isBST(Node *root)

{

          return isBST(root, NULL, NULL);

}

 

Solution 2: Use in order tree traversal

Do you remember what happens during in order traversal for a BST? It visits the nodes in sorted increasing order. We can use this to verify the BST assuming the BST does not have duplicated keys.

 

Please note this solution does not work for the all the BST types, it depends on the definition of BST.  For example, if we allow duplicated keys and assume right subtrees are strictly bigger than the parent, then this method will fail for the following example.

          20

         /   \

      15   20

 

bool isBSTInOrderHelper(Node *root, Node * &prev)

 {

    if (root == NULL)

 return true;

   

     if (!isBSTInOrderHelper(root->left, prev))

          return false;

     if (prev != NULL &&  prev->data > root->data)

          return false;

    prev = root;

     

   return isBSTInOrderHelper(root->right, prev));

}

 

bool isBST(Node *root) {

  Node *prev = NULL;

  return isBSTInOrderHelper(root, prev);

}

 

Question 2: Find the number of inversions in an integer array.

 

An inversion is an out of order pair in the array, or a pair (a[i], a[j]) such that a[i] > a[j] && i < j given an integer array a. apparently, for a sorted array, the number of inversions is 0, for an array sorted by reverse order, the number of inversions is the maximum.

 

Solution 1: Simply compare all the pairs and count, this is O(N^2).

int getInvCount(int arr[], int n)

{

  int count = 0;

  int i, j;

 

  for(i = 0; i < n - 1; i++)

    for(j = i+1; j < n; j++)

      if(arr[i] > arr[j])

        count++;

 

  return count;

}

 

Solution 2: Enhance merge sort with inversion count.

We know merge sort is a divide and conquer sorting algorithm, in which we first recursively divide the array into multiple 1 element lists, and then repeatedly merging all the sorted lists into one final sorted list. The time is O(nlogn), space is O(n). We can count number of inversions while we do merge sort.

How to exactly count? When we merge two lists (left and right list), the number of inversions is the sum of:

1)    Number of inversions we have already counted in the left list.

2)    Number of inversions we have already counted in the right list.

3)    The number of elements in the left list that is not merged yet when an element from the right list is picked up during the merge.

 

Please note: this algorithm modifies the original array and also need a same size array for extra storage. The recursion uses storage in the stack too, but it is O(logn), less than O(n), so the space is still O(n).

 

int getNumInversions(int arr[], int array_size)

{

    int *temp = (int *)malloc(sizeof(int)*array_size);

int count = mergeSort(arr, temp, 0, array_size - 1);

free(temp);

return count;

}

  

int mergeSort(int arr[], int temp[], int left, int right)

{

  int mid, inv_count = 0;

  if (right > left)

  {

      mid = (right + left)/2;

      inv_count  = mergeSort(arr, temp, left, mid);

      inv_count += mergeSort(arr, temp, mid+1, right);

      inv_count += merge(arr, temp, left, mid+1, right);

  }

  return inv_count;

}

 

int merge(int arr[], int temp[], int left, int mid, int right)

{

  int i, j, k;

  int inv_count = 0;

   i = left;

  j = mid;

   k = left;

  while ((i <= mid - 1) && (j <= right))

  {

 if (arr[i] <= arr[j])    { 

      temp[k++] = arr[i++];

     }   else    {

         temp[k++] = arr[j++];

         inv_count = inv_count + (mid - i); 

     }

  }

 

  /* Copy the remaining  left subarray */

  while (i <= mid – 1)

      temp[k++] = arr[i++];

 

  /* Copy the remaining right subarray */

  while (j <= right)

     temp[k++] = arr[j++];

  

  /*Copy back the merged elements to original array*/

  for (i=left; i <= right; i++)    arr[i] = temp[i];

  

  return inv_count;

}


 

Question 3:  Find maximum water trapped.

 

Given a non-negative integer array representing an elevation map where the width of each bar is 1, find how much water it is able to trap after raining.

 

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], the answer is 6.

The blue color in the picture below indicates the trapped rain water.

 

 

 

Solution 1:  Find max height on its left and max height on its right for each position.

 

This is very intuitive solution. For each position, assume its height is h,  if we can find its max height on the left (lh), max height on the right(lr), this position can only hold water if min(lh, lr) > h, the water this position can hold is  min(lh, lr) - h.

 

We can use an extra array to hold the max height for each position on its left side, another extra array to hold the max height for each position on its right side. The two arrays can be calculated by scanning the array once for each.

This leads to our first O(n) time and O(n) space solution.

 

int trap(int A[], int n) {

      if (n <= 2 || A == NULL)

     return 0;

     

      int sum = 0;

      int *lmax= (int*) malloc(n*sizeof(int));

      int *rmax= (int*) malloc(n*sizeof(int));

     

       lmax[0] = rmax[n-1] = 0;

       int i;

       for (i =1; i < n; i++) {

           lmax[i] =   max(lmax[i-1], A[i-1]);

           rmax[n-1-i] = x(rmax[n-i], A[n-i]);       

        }

 

      for (i =0; i < n; i++) {

          int h = min(lmax[i], rmax[i])

           if (A[i] < h)  {

               sum += h – A[i];

          }

       }

      

        free(lmax);

        free(rmax);

        return sum;

    }

 

 

Solution 2: Find the max height.

 

We do not like the extra space cost. Can we do better? Can the max height help us? The max height can service as the max left height for all the positions on its right, and the max right height for all the positions on its left, we can then calculate the unknown max left height or right height on the fly.

 

 int trap(int A[], int n) {

      if (n <= 2 || A == NULL)

     return 0;

     

      int sum = 0;

      int i;

 

      /* find the max height position */

      int maxPos = 0;

      for (i = 1; i < n; i++) {

           if (A[i] > A[maxPos])

                  maxPos = i;

        }

 

      /* calculate the water on the left side of the max position */

      int  lmax = A[0];

      for (i = 1; i < maxPos; i++) {

If (A[i] > lmax)

                 lmax = A[i];

          else

                sum += lmax – A[i];

     }

     

     /* calculate the water on the right side of the max position */

      int  rmax = A[n-1];

      for (i = n - 2; i > maxPos; i--) {

If (A[i] > rmax)

                 rmax = A[i];

           else

                 sum += rmax – A[i];

       }

 

        return sum;

    }

 

Solution 3: Start from two ends of the array.

In the above two solutions, we have been trying to find the max height on its left and max height on its right for each position. Actually only the lower of the two max height matters, knowing lower of the two is enough to calculate the water trapped. This leads to our third solution.

We can start from the two ends of the array, keep track the max height find so far on the left and right, assume leftMax is the max height for elements a[0..i], and rightMax is the max for a[j..n-1]. If leftMax < rightMax, we can calculate how much water is trapped for position i+1 and also update leftMax if needed. If rightMax < leftMax, we can calculate how much water is trapped for position j-1 and update rightMax if needed.

int trap(int A[], int n) {
        if(n == 2 || A == NULL) return 0;
        int i = 0, j = n-1;

         int  lm = A[0], rm = A[n-1];

         int  sum = 0;
        while(i < j) {
            if(lm < rm) {
                if(A[++i] < lm)
                    sum += (lm - A[i]);
                else
                    lm = A[i];
            } else {
                if(A[--j] < rm)
                    sum += (rm - A[j]);
                else
                    rm = A[j];
            }
        }
        return sum;
    }

 



Defa

About Instructor Defa Sun

Defa is currently a Sr Member of Technical Staff in Vmware. Before that, he had worked in several top silicon valley companies including Yahoo and Ebay as well as early startups. Before coming to US, he worked as a instructor in Computer Science Department, Shandong University, China. Defa obtained his master degree in computer science from Virginia Tech. Having worked in the tech industry for more than 10 years, he is an experienced C++ programmer and has extensive knowledge in the industry.




Reserve your seat now for $65! Last day of cancellation for full refund is 9/29 Sunday.

Quick class cancellation, just enter the Paypal Transaction ID from the Paypal payment receipt email which you receive when you register.

Online Database by Caspio
Click here to load this Caspio Online Database.