Work in HR? Unlock Free Profile

## 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.

0

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

Interview Candidate on Mar 7, 2014
0

How did you solve it?

Anonymous on Mar 11, 2014
0

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
0

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 range...best 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
0

DFS

Anonymous on Aug 3, 2014