s********u
发帖数: 1109 | 1 二维平面上有很多圆，圆心都在原
点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
难道不是算所有点离原点的距离，然后看落在哪个范围，对应的count就加1，然后最后
找count数组的最大值？跟subarray和最远距离有何关系。。
就是“看落在哪个范围”没想到好办法，只能将圆环按半径排序后，用二分法去找么 |
|
s********u
发帖数: 1109 | 2 二维平面上有很多圆，圆心都在原
点，同时平面上有很多点，问哪两个相邻的圆环之间的点最多
难道不是算所有点离原点的距离，然后看落在哪个范围，对应的count就加1，然后最后
找count数组的最大值？跟subarray和最远距离有何关系。。
就是“看落在哪个范围”没想到好办法，只能将圆环按半径排序后，用二分法去找么 |
|
s********u
发帖数: 1109 | 3 嗯，其实核心思想就是dp吧。我觉得跟那个maximum subarray是类似的。
我写的：
for(int i = 0; i < size; i++){
sum += gas[i] - cost[i];
if(subSum > 0)
subSum += gas[i] - cost[i];
else{
subSum = gas[i] - cost[i];
index = i;
}
}
if(sum < 0) return -1;
return index;
} |
|
s********u
发帖数: 1109 | 4 嗯，其实核心思想就是dp吧。我觉得跟那个maximum subarray是类似的。
我写的：
for(int i = 0; i < size; i++){
sum += gas[i] - cost[i];
if(subSum > 0)
subSum += gas[i] - cost[i];
else{
subSum = gas[i] - cost[i];
index = i;
}
}
if(sum < 0) return -1;
return index;
} |
|
P**********k
发帖数: 1629 | 5 这个不就是用integral image
先建一个NxN的pre-sum数组，然后这个数组的(i,j)元素存的是从(0, 0)到(i, j)的
subarray的和，
这样每次query任意sub-array的和，只用取出对应这个pre-sum数组的四个顶点的值
A -----B
| |
| |
C-----D
然后计算A+D-B-C就行了,这样query就是O(1). |
|
P**********k
发帖数: 1629 | 6 这个不就是用integral image
先建一个NxN的pre-sum数组，然后这个数组的(i,j)元素存的是从(0, 0)到(i, j)的
subarray的和，
这样每次query任意sub-array的和，只用取出对应这个pre-sum数组的四个顶点的值
A -----B
| |
| |
C-----D
然后计算A+D-B-C就行了,这样query就是O(1). |
|
f********e
发帖数: 91 | 7 谢谢LZ的面经
问一个问题 Longest increasing subarray 的O（n）解法是什么呀？我知道O（n^2）
和O（nlgn）的解法。。。
。 |
|
f********e
发帖数: 91 | 8 谢谢LZ的面经
问一个问题 Longest increasing subarray 的O（n）解法是什么呀？我知道O（n^2）
和O（nlgn）的解法。。。
。 |
|
p*****e
发帖数: 537 | 9 Subarray sum那道题，我觉得如果O(n^2)可以的话，有至少2种解法，prefix sum
array，或是一个2D DP, 其实本质都一样。
有没有大牛说说优于O(n^2)的解法？ |
|
n******f
发帖数: 318 | 10 “对于题目所求，我们希望s[i]越大越好，s[j + 1]越小越好，这样他们的差才会小”
我觉得这个不对。这样求出来的是平均值较小的，而不是满足条件的最长的subarray。
有时候，s[j+1+1]对应的数a[j+1]（不是递减点），由于a[j+1]较小，但是跟前面的
suarray平均下，依旧满足条件。
愚见而已，还请大神们指点。 |
|
c*******2
发帖数: 60 | 11 then with an additional condition that subarray.length <= A.length ? |
|
n****e
发帖数: 678 | 12 一样的方法，
用两个index来表示subarray的beg和end。当beg > end，说明跨界。 |
|
|
a*********2
发帖数: 194 | 14 divide and conquer.
分段找，中间合并检查，n*logn。 |
|
s*******z
发帖数: 83 | 15 是的, 当结果都是N^2的时候, 复杂度应该低不了N^2 |
|
b****p
发帖数: 216 | 16 一个一个加起来，sum array排序，然后两个指针一个从头一个从屁股扫一下就好了。 |
|
|
F********9
发帖数: 44 | 18
你这样会漏掉一些解吧。 比如合并 【2 -5】 【6-7】时会漏了 【4-6】等可能的解呀
。 |
|
x*******i
发帖数: 26 | 19 "跨mid的区间O(n)找到。"
这个不行吧？ 比如说 左边 （1 ，2， 3）， 右边 （4， 5 ，6），range (0, 100),
那跨中间的组合是 9种 {(3, 4), (3,4, 5), (3,4,5,6), (2,3,4)...}， n^2.
1 |
|
|
c******n
发帖数: 100 | 21 这样不行吧。
比如 dp[i]+num[i+1] 不在range中不代表 dp[i+1] 不存在啊。（可以drop之前的元素） |
|
x*******9
发帖数: 138 | 22 数组长度为N，把整个数组分为K段。这里取 K=sqrt(N)。
一段子数组我们用[st, end]来表示。
我们要统计每段子数组[st...x]的取值。
例如，[1, 2, 3]。sum([1]) = 1, sum([1, 2]) = 3, sum([1, 2, 3]) = 6。 然后排
序累加，使得类似“这一段子数组在和大于3有多少个”的Query的时间复杂度为O(log(
K))。
然后遍历数组，通过预处理好的子数组序列进行计算。
预计时间复杂度为O(n * sqrt(n) * log(n))。
比O(n^2)要好一点。不过比较难写。。。=。= |
|
l******6
发帖数: 340 | 23 integer数组分三份，使彼此有最小difference.
Does it require all subarray have equal size? |
|
|
g******y
发帖数: 143 | 25 Interviewed with Kinect group
Phone interview
1.implement an image convolution and optimize it
2. find the intersection of two rectangles
Onsite
Round1
1. Implement strstr() and optimize it
2. Implement histogram equalization algorithm
3. Bayes conditional probability
Round2
1. Implement a fixed floating point class
2. Square root of a number (the number can be less than 1)
Round3
1. Find subarray which has max sum
2. Find the kth element in two sorted arrays
Round4
1. Im... 阅读全帖 |
|
l***i
发帖数: 1309 | 26 面试的人问了个题，第一问用个hashtable就搞出来了，第二问只能用hungarian做，但
是我说了一半发现对方确实是不知道这个算法，估计面试官不知道从哪个难题集里面搞
了个题来欺负人。还有一次一个兄弟问max sum subarray，然后不知道O(1) space的做
法，当时我也没证明我的做法是对的，回家的路上才想起来他可能要的是dp[k] = max(
dp[k-1] + a[k], a[k])这样的做法。
一般来说FLGT这种级别的公司可以认为面试的人是比较懂他出的题的，一般的公司就先
给个笨办法，然后讲高级做法。另外就是如果对方表示不懂你的做法，你有义务证明你
的做法的正确性。 |
|
l******e
发帖数: 54 | 27 只能用那个算法…这是什么难题
subarray 就是想问证明吧 比如反证就可以
max( |
|
j**********3
发帖数: 3211 | 28 Subarray with max prod 用什么方法做简单？如果不用divided & conquer |
|
a*******e
发帖数: 455 | 29 subarray max prod, 要考虑负数不？ 谢谢 |
|
m******x
发帖数: 58 | 30 max product of subarray |
|
c*5
发帖数: 130 | 31 这题肯定不是这样啊 毕竟是google面试, 肯定要用快慢指针linear那个解法, 最后返
回整个array的subarray?? leetcode那是返回长度 |
|
t*******i
发帖数: 4960 | 32 L家小姑娘给我出了 max product of subarray 和一道leetcode原题。
想了半天才想到解法，又没写完。 ：（ |
|
t*******i
发帖数: 4960 | 33 我不是 local。
女面试官给考了道 max product of subarray， 没作完，从来没作过。
这还要加难度啊？ |
|
w*********e
发帖数: 207 | 34 这 max product subarray 和lc上的max sum有什么区别 |
|
o****n
发帖数: 937 | 35 别想太多，L，外地的话，本身就是2轮电面。其实和第一轮差别不大。好好准备放轻松
心态。
另外，max p of subarray，思路当时说清楚了么？写不完没关系，说清楚自己怎么思
考的，可能遇到什么问题，比背答案更有用 |
|
|
|
h*******e
发帖数: 1377 | 38 大家讨论讨论。。。我想到比较naive的想法 对于不为零的一段空间， 是做个 dp[
10001][10] 10是任意取的 一个是 无穷大的，一个保存靠近 1 大于 和 小于 1 的 靠
近 0的 大于小于 负一的
，然后 相乘后update当前的index里面各个dp value~~
然后再和前面的index 相除 得到 sub array sum(double val) 然后取最大值
然后大概复杂度 O(N^2) 思路不严密
，有没有心细的版友 补充完全。 |
|
|
|
h*******e
发帖数: 1377 | 41 好的，你的做法很好，用了一个性质，2个极值 *新的数 依然是 ２个极值～～然后
不断用新数刷新极值。 依次得到最后的极值，开始我也想到这种dp但是想得不深入～
～～以
为此路不通～～。你的方法给我很大启发。
本身
及A |
|
h*******e
发帖数: 1377 | 42 新技能get..3数求max 比我之前用的好～～～ |
|
|
C********e
发帖数: 492 | 44 为什么要leftSum[i] == leftSum[j] ?
这意味着i ~ j 之间都是0，并不是要找的subarray啊 |
|
s***5
发帖数: 2136 | 45 the hash table uses the sum up to each index i + the target sum as the key,
and index i as the mapping value,
the "acc" array contain the sum up to each index j
if acc[j] is the key in the hash table with mapping value i, you know the
subarray [i+1,j] is summed up to the target sum
clear? |
|
|
y*****e
发帖数: 712 | 47 我当时放了i是因为自己写了几个test case，return的不是true or false, 而是
subarray的start和end index, 所以放了i好比较结果对不对。如果按原题只return
boolean的话，应该用hashset就可以。
了？ |
|
i******d
发帖数: 61 | 48 我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
办法？ |
|
s***5
发帖数: 2136 | 49 the hash table uses the sum up to each index i + the target sum as the key,
and index i as the mapping value,
the "acc" array contain the sum up to each index j
if acc[j] is the key in the hash table with mapping value i, you know the
subarray [i+1,j] is summed up to the target sum
clear? |
|
|
