c******a
发帖数: 14 | 1 上周写了liveramp的OA题，分享给大家：）
之前也看了大家的许多面经，回馈一下。
两道题比较第二道比较新。
1) Given an array A, find the index p, in which A[0] + A[1] +...+ A[p-1] = A
[p+1] + A[p+2] +.. + A[n-1]. Time complex O(n)
2) Given an array A, find the longest subarray which biggest element minus
smallest element not less than 1. | e********2
发帖数: 495 | 2 第二题要么无解，要么整个array？
A
【在 c******a 的大作中提到】
: 上周写了liveramp的OA题，分享给大家：）
: 之前也看了大家的许多面经，回馈一下。
: 两道题比较第二道比较新。
: 1) Given an array A, find the index p, in which A[0] + A[1] +...+ A[p-1] = A
: [p+1] + A[p+2] +.. + A[n-1]. Time complex O(n)
: 2) Given an array A, find the longest subarray which biggest element minus
: smallest element not less than 1.
| c******a
发帖数: 14 | 3 数组的顺序不能变，例如：A = [ 3, 5, 7,7,6], 最长的应该是[7, 7, 6]
【在 e********2 的大作中提到】
: 第二题要么无解，要么整个array？
:
: A
| g********i
发帖数: 770 | 4 这个是no more than 1吧，用sliding window做。 | j**********3
发帖数: 3211 | | b***e
发帖数: 1419 | 6 这个用sliding window的确可以做到线性，但是很难。
【在 g********i 的大作中提到】
: 这个是no more than 1吧，用sliding window做。
| f********y
发帖数: 156 | 7 大概这样做:
use an array len[ ] to keep track of the longest subarray ending at A[i]
use {min, minIndex } and {max, maxIndex} to keep track of current min/max
and their indices.
if A[i] > max + 1, then update max and clear min; set len[i] = 1
if A[i] < min -1, then update min and clear max; set len[i] = 1
if A[i] is between min and max, then set len[i] = len[i-1] + 1
if A[i] == max + 1 && minIndex < maxIndex, then min = max; max = A[i],
len[i] = len[i-1] + (maxIndex - minIndex)
if A[i] == min -1 && minIndex > maxIndex, then max = min; min = A[i], len[i
] = len[i-1] + (minIndex - maxIndex)
第一遍走完，len[ ] 就设好了；第二遍遍历 len[ ] 找最大值
【在 b***e 的大作中提到】
: 这个用sliding window的确可以做到线性，但是很难。
| b***e
发帖数: 1419 | 8 Are you assuming each number is an integer?
Anyways, the general approach requires sliding window max/min algorithm,
which is non-trivial. I think this problem is too hard for an interview
question.
[i
【在 f********y 的大作中提到】
: 大概这样做:
: use an array len[ ] to keep track of the longest subarray ending at A[i]
: use {min, minIndex } and {max, maxIndex} to keep track of current min/max
: and their indices.
: if A[i] > max + 1, then update max and clear min; set len[i] = 1
: if A[i] < min -1, then update min and clear max; set len[i] = 1
: if A[i] is between min and max, then set len[i] = len[i-1] + 1
: if A[i] == max + 1 && minIndex < maxIndex, then min = max; max = A[i],
: len[i] = len[i-1] + (maxIndex - minIndex)
: if A[i] == min -1 && minIndex > maxIndex, then max = min; min = A[i], len[i
|
|
