Facebook Interview Question: Question is verbose, uses sea... | Glassdoor

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

Interview Answer

8 Answers

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 in mergedArray {
    if (high - low 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
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?

Felipe on Sep 29, 2014
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
############################

Anonymous on Oct 6, 2014
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

Anon on Oct 8, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.