# Grab Interview Question - SDE

Q1.

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:

Q2.

/*

• 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.
*/

1 Like

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

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