Restricted category To view older posts, you must first submit an approved post in that category

Postmates SWE interview - need help! didn't solve it right

so my interview lasted about 70 minutes and i got four questions
first two questions were super easy

The third question: relatively trivial, string manupulation raw string, align, etc.

Fourth question is where I think I tanked- does anyone have a solution?

a = [-2, 2, 5, -6]; b = [0, -6, -7, 10, 100] [/mw_shl_code] (a and b can be very large lists) lower = num1, upper = num2, lower and upper can be very big or small number
return total_count such that lower <= (a ** a + b[j]b[j]) <= upper

3 Likes

For the last one:
N: total number of different a[i] * a[i] + b[j]*b[j] == m * n
N0: count how many a[i] * a[i] + b[j]*b[j] <low (two points) in O(m + n)
N1: count how many a[i] * a[i] + b[j]*b[j]> high (two points) in O(m + n)
return N-N0-N1

I also interviewed there and remember this question
given a list “a”, which is the length of each rope, you can cut the rope, and an integer k, which represents the last required rope root Count and return the longest possible length of each rope. eg a = [7, 2, 3, 4, 9], k = 5, return 3. By cutting, the first rope can get 2 ropes of length 3, and the following ropes can get 0, 1, in turn 1, 3 roots, total 7 roots greater than 5 roots. If the length is 4, you can only get a total of 4 1 + 0 + 0 + 1 + 2, and there is no way to get 5.

the general idea is to quickly find the maximum and minimum possible values ​​of the answer through the question, and then use the dichotomy in this interval-each intermediate number can verify whether it meets the requirements

For example, a = [7, 2, 3, 4, 9], k = 5, is sort, and see if the intermediate value (3) meets the condition, go to the right if it is satisfied, and go left if it is not. Take the middle number of the new interval.

I don’t think that looks right to me