Interview Question

Software Engineer Interview Seattle, WA

Question is verbose, uses search engine, string matching

  etc., but at the end boils down to this: There is two dimensional array where each sub array (row) is sorted, i.e. [[1 1000 2000] [20 10001 5000] [55 10002 222222]] Find a minimum range contain a number from each row. For above array it should be (1000-1002) range.

Interview Answer

5 Answers


I solved this question, but didn't have time to code.

Interview Candidate on Mar 7, 2014

How did you solve it?

Anonymous on Mar 11, 2014

Brute force approach:

mergedArray = merge(array1, array2, ...);
minLength = infinity;
minLow = null; // low end of the solution interval
minHigh = null; // high end of the solution interval
Loop over all pairs <low, high> in mergedArray {
    if (high - low < minLength) {
         isSolution = checkAllArraysForNumberBetween(low, high);
         if (isSolution) {
              minLength = high - low;
              minLow = low;
              minHigh = high;
// solution is the interval <minLow, minHigh> inclusive

Anonymous on Mar 24, 2014

Perhaps this is a better idea: It's a one pass algorithm. For each row, keep a current pos. Initially, it's zero. This is the first so far.
Now, move the smallest value's pos in this range to the right. If you have a range, keep repeating and storing max so far.
I think that this might lead to an O(n-cube) or better solution.

Henry David Thoreau on Apr 12, 2014


Anonymous on Aug 3, 2014

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up