How did you solve it?

Software Engineer Interview Seattle, WA

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

8 Answers

▲

0

▼

How did you solve it?

▲

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 in mergedArray {

if (high - low inclusive

▲

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.

▲

0

▼

DFS

▲

4

▼

Assume k rows and total n vaues.

- Merge them all in order (n log n), while keeping the numbers themselves zipped up with the row they belonged too.

e.g. (1,0), (20,1), (55,2), (1000,0), (1001,1), ...

- Go through this sorted list keeping track of value of number last seen for each given row. In detail:

- Have a min-heap with k nodes, each node unique to a row; ensure you keep a reference to each for O(1) access.

- As you iterate, update value at corresponding node in the min-heap, and re-heapify.

- During each iteration peek at min-heap, and calculate range ( = current val in iteration - min-heap-val). Store it if it's the minimum range found so far.

Looks like O(n log n) ... anyone wish to verify?

▲

0

▼

You can do this in 2n iterations. The idea is to find a range (starting from the left side), which is feasible (i.e. contains at least one value from each row). The range is determined by the indices [start_idx, end_idx]. In each iteration, if we can decrease the interval by moving start_idx forward, then we do that (which gives us a potentially smaller range), otherwise we increase the range by incrementing end_idx by one. This will have a running time of 2n (where n is the total number of values in all rows) since the start and end indices are only ever moved forwards.

############################

# Setup

rows = [[1, 5, 7], [-1, 11], [0, 1, 2, 3, 4], [5, 1000]]

# Place rows into linear sorted list [(-1, 1), (0, 2), (1, 0), (2, 2), (3,2), ...]

linear_rows = []

for i, v in enumerate(rows):

linear_rows.extend(zip(v, [i] * len(v)))

linear_rows.sort()

# Number of rows

num_rows = len(rows)

# Histogram of number of values for each row in a specific interval

hist = [0] * num_rows

# Number of unique rows found so far

num_unique = 0

# Start index where in linear_rows

start_idx = 0

# Minimum range containing at least one value from each row

min_range = float("inf")

for end_idx, v in enumerate(linear_rows):

# Generate histogram of the number of values from each row that we've seen so far.

hist[v[1]] += 1

if hist[v[1]] == 1:

num_unique += 1

# Check if we've found a feasible solution (each row is covered)

if num_unique == num_rows:

# See if we can move the start forward

for j in range(start_idx, end_idx):

if hist[linear_rows[j][1]] > 1:

hist[linear_rows[j][1]] -= 1

else:

break

start_idx = j

# We have a new candidate for the minimum range.

min_range = min(min_range, linear_rows[end_idx][0] - linear_rows[start_idx][0])

print min_range

############################

▲

0

▼

I came up with the following, but it surely took me a good 20-30mins. I'ld hate it memorization is being tested rather than the process of arriving(eventually) at optimal solution after iterating.

1. Merge sorted lists in O(n) time, O(n) storage

2. Do the following in O(n.log(n)) time, O(n.log(n)) storage

RG

/ \

/ \ *(winner based on accumulated range from lower ranges)

RG RG RGB RGB RGB RG RGB GB

/ \ / \ / \ / \ / \ / \ / \ / \

/ \ / \ / \ / \ / \ / \ / \ / \

R RG RG RB BG RG RG GB B

/ \ / \ / \ / \ / \ / \ / \ / \ / \

/ \ / \ / \ / \ / \ / \ / \ / \ / \

R----R-----G----R-----B------G-----R------G-----B-----B

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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