Grab Interview Question - SDE


There is a board with 2 rows and N columns, represented by a matrix M . Rows are numbered from 0 to 1 from top to bottom and columns are numbered from 0 to N-1 from left to right. Each cell contains either a 0 or a 1. You know that:

  • the sum of integers in the 0-th (upper) row is equal to U,
  • the sum of integers in the 1-st (lower) row is equal to L,
  • the sum of integers in the K-th column is equal to C[K].

Your job is to recover M based on this information.
Write a function: function solution(U, L, C); that, given two integers U, L and an array C of N integers, as described above, returns a string describing the matrix M in the following format. The first part of the string should be the description of the upper row ( N characters: 0 or 1), then there should be comma (,) , and finally there should be the description of the lower row (N characters: 0 or 1.)

The output string should not contain any whitespace. If there exist multiple valid Ms, your function may return any one of them. If no valid M exists, your function should return the word IMPOSSIBLE.

Examples: 1. Given U = 3, L = 2, C = [2, 1, 1, 0, 1] , your function may, for example, return 11001,10100 which describes the following board:



  • Date: 8-Oct-2019
  • Description:
  • John was sitting near to a fireplace in his house, trying to get some warmth
  • from the fire. Fighting his cold at the end of a freezing, Short, dark winter
  • day, he started wondering why it always had to be so cold during this season.
  • That was when he came up with an idea.
  • John stated that winter is the initial pan of the year in which it is always
  • colder than in the remaining part. This latter part is called ‘summer’.Then
  • he assumed that summer is always warmer than winter; that is, any temperature
  • measured in winter is colder than every temperature measured in summer.
  • Then he searched the Internet and found the previous years meteorological
  • data, which contained the years temperature measurements. He began to wonder
  • if it might be possible to divide the year into winter and summer so that
  • winter comes before summer and each winter’s temperature measurement is
  • smaller than any temperature measured in summer. In case there are many such
  • possible partitions, find the one in which the winter period is as short as
  • possible. (It is quite cold now; there is really no reason for winter to be
  • longer than necessary…)
  • Write a function that, given a sequence T of temperature measurements
  • (specified as integer numbers), finds the partition of the year into winter
  • and summer that meets the conditions above and makes winter as short as
  • possible, then returns the length of the winter. Both winter and summer have
  • to be at least one day long. You can assume that there exists at least one
  • partition that satisfies this condition.
  • For example, given: T = [5, -2, 3, 8, 6]
  • the function should return 3, as after partitioning the year into
  • winter: [5, -2, 3] and summer: [8, 6], each winter’s measurement is smaller
  • than each summer’s temperature.
  • On the other hand, for the following array: T = [-5, -5, -42, 6, 12]
  • the function should return 4. The partition that minimizes the length of the
  • winter is [-5, -5, -5, -42] and [6, 12]. Winter could also have length 5,
  • but the function should return the shortest possible winter.
  • Assume that:
  • N is an integer within the range [2…300,000];
  • each element of array T is an integer within the range
  • There will be at least one correct way to divide the year into winter and
  • summer.
  • Complexity:
  • expected worst-case time complexity is O(N)
  • In programming words:
  • Write a program to divide an array in such a way that all left side
  • elements are smaller than any right side element .i.e.
  • max of left sub-array < min of right sub-array.
  • Output should be the count of number of elements in left sub-array.
  • Implementation:
  • Keep track of max number while moving from left to right, increment
  • right-sub-array-count if new number is greater than max otherwise set counter
  • to 0 and update max.


这是社招吧? OA还是店面呢?

1 Like


grab电面这么变态??我感觉读完一道题都要半天了,他们还让做两道? 请问面试官是哪国人啊


没办法 他们就是给我这样的题


150 分钟。大概用了30 分钟来理解题目。。 Q_Q


现在他们都先online 再决定要不要onsite