y*****e
发帖数: 712 | 1 我当时放了i是因为自己写了几个test case，return的不是true or false, 而是
subarray的start和end index, 所以放了i好比较结果对不对。如果按原题只return
boolean的话，应该用hashset就可以。
了？ |
|
i******d
发帖数: 61 | 2 我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
办法？ |
|
|
W*********y
发帖数: 481 | 4 来自主题: JobHunting版 - G电面面经 不是的，其实是需要一个size 为 k+1的vector，其中k为最大increasing subarray 的
长度。
对本题只需找到k为3的解是否存在，因此空间constant，时间O(n)
bool kLIS(vector &data, int k){
vector stack(k+1);
int top = 0;
stack[0] = -1;
for(int i=0;i
if(data[i]>stack[top]){
stack[++top] = data[i];
}
else{
auto low = lower_bound(stack.begin(), top+stack.begin(), data[i]);
*low = data[i];
}
if(top==k)
return true;
}
return false;
} |
|
y*****e
发帖数: 712 | 5 是subarray还是subsequence啊，就是说是不是必须是连续的？ |
|
y*****i
发帖数: 141 | 6 subsequence。连续的。
subarray岂不是只要捡正数搞一起就行了？ |
|
C****t
发帖数: 53 | 7 There are 2 ways to do these.
|--A1--|---A2---|---B1---B2---|
Evenly divide An and Bn into (A1,A2), (B1,B2) respectively.
len(A2) - len(A1) = len(B2) - len(B1) == 1 or 0 depends on odd or even.
Method 1: O(n*logn)
1a. Exchange A2 and B1.
1B. recursively do this on two new subarrays A1+B1, A2+B2
Method 2 : O(n)
2a. The idea is the same as Method 1. Now for each index from 0 to 2*n-1, we
have 4 different domains A1, A2, B1, B2.
2b. Map index of A1 to even index of 2*len(A1)
Map index of B... 阅读全帖 |
|
b**********5
发帖数: 7881 | 8 恩， 以前在这板上看到过相似的另外一题， 就是只要return a boolean， whether
there's such subarray
1] |
|
t****m
发帖数: 140 | 9 楼主fresh MS，之前有大公司实习经历
谢谢版上的朋友refer了FB，之后拿到电面
一个中国小哥，人很nice，首先介绍了一下自己的组
问了一下我之前的经历
1.给你一个array of character，包括有digits， lower case char and upper case
char， 如何才能把他们sort成所有digits在前， 所有lower case在中间， upper
case 在最后，类似于sort color from leetcode
问了complexity，并且讨论了sort之后原有的digit的顺序是否改变， 各种讨论细节
这题依照leetcode，很顺利的写了出来
2.follow-up： 如果现在输入的array 包含有多种类型的char（lower case， upper
case， float。。。）， 如何改变input， 使得我们能写出类似的代码
我给出的意见是除了原有的array of chars 之外，再给出一个array of array， 每个
subarray cover 一个category的范围，例如[['1', '... 阅读全帖 |
|
|
|
d*****5
发帖数: 1920 | 12 弯曲小公司，最近面试了几个candidates，郁闷了。
某老中：
大哥题应该是刷了，出了两个简单的，很快bug free写出来了。我挺高兴。结果转头一
看隔壁烙印给他的Feedback一塌糊涂，因为几个基础知识题，什么JDK JRE区别，
arraylist and linkedlist 区别之类的，没答对，直接要fail。 转头给recruiter说
了说好话，又多给了一轮老美的phone interview。今天看feedback，凶多吉少。。。
某烙印女：
穿个脏兮兮的运动衫，还带这味就来面试了。算法一窍不通，binary tree访问告诉我
是O(1), 递归Fibonaci说是O(n). 题更是没刷过。max sum subarray连个最土的brute
force都写不出来。果断差评。转头看隔壁烙印给的feedback 非常好。会个singleton
就是会design pattern，知道啥是index就是数据库知识很强，知道java GC怎么工作就
是Java基础很好。擦。照例也被加试一轮老美的phone interview，今天看feedback，
很不错，估计要给... 阅读全帖 |
|
M**u
发帖数: 10158 | 13 很有道理啊
who cares binary tree, max sum subarray...
brute
singleton |
|
|
p*u
发帖数: 2454 | 15 pay attention to "contiguous subarray" |
|
w*****1
发帖数: 6807 | 16 第一次电面，刚电面完马鬃，面试官最后说hiring team稍后会联系我，然后就byebye了
请问我除了等待还是最好再需要做点什么？
面经就是max sum of subarray，经典题 |
|
r****8
发帖数: 22 | 17 networking背景。和web公司的风格不大一样。多个公司的面筋。希望对后来人，有帮
助。
implement a hash table
lru cache
two sum
void store(int val);
store the value
bool test(int target);
return true if two stored values who sum equals target
otherwise false
We want test really fast.
O(1) test
O(n) store
Given a binary tree where parent node value is minimum of two children node
values, find the second min.
given nested list, return sum. Sum is defined as depth*current sum
what is dead lock? how to prevent it?
implement a readlock
im... 阅读全帖 |
|
c******a
发帖数: 14 | 18 上周写了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. |
|
f********y
发帖数: 156 | 19 大概这样做:
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 -... 阅读全帖 |
|
|
|
g****c
发帖数: 11 | 22 挂了有段时间了。现在上面经以答谢本版。
phone:
1. max sum subarray
2. tree level order traversal
onsite:
1. design a hash table
2. design a hash table, where the value must be stored in an append-only
file system
3. design a logging system which stores streams of integers within a time
period. implement get, put, getAvg
4. design an RSS feed
5. Edit distance; implement strstr |
|
a*********8
发帖数: 140 | 23 这个版伙伴们积极分享的面经给我的帮助特别大。 看到常来的伙伴们，陆陆续续都拿
到offer，一直很受鼓舞， 我也终于拿到心仪的offer了。
我有过的严重教训和误区：
两年前，产生换工作念头后，不知道要刷leetcode题这一说， 也没来贵版查面经。因
为曾经差点拿到Google offer （没match上组）， 就随便看了看data structure和sql
， 结果Google和 Facebook 电面都没过，深受打击。
一年前，还是不知道刷leetcode这个事的重要，直接上Tango, C3Energy, Microsoft,
Yahoo, AOL，还有几个一般名气的中小公司练手，都过了电面， 当然都止步于
onsite。和朋友聊起，上Leetcode网站去看，几乎考到的题，都在上面，这个懊恼的。
我在目前的驴子处，做Java/J2EE有5-6年了，以为只能申请用Java的公司。 最近半年
我来贵版越来越勤，看到热心的同胞贴的内推要求，也看到没有相关经验的伙伴，靠算
法就拿到大offer，受了启发 – 现在的热门公司都重算法，不重这个靠时间笨人烂人
也会积累的经验。
因为... 阅读全帖 |
|
E******g
发帖数: 204 | 24 上来10min讲了讲我现在的project，然后问了一些machine learning相关的概念，
然后写了一道Maximum subarray (leetcode 原题)，
follow up：如果输入时Stream怎么办
代码写的比较快，后面又问了一些其他的和ML相关的概念
今天recruiter通知我onsite了，因为10月份比较忙，跟recruiter说了要到11月才可以
，不知道是不是拖的时间有点长？
求bless onsite一切顺利！ |
|
s*******t
发帖数: 255 | 25 Bless!
上来10min讲了讲我现在的project，然后问了一些machine learning相关的概念，然后
写了一道Maximum subarray (leetcode 原题)，f........ |
|
s****t
发帖数: 467 | 26 找工作告一段落，把前一段面试的题目整理一下一起发出来。各个公司的放在一起了，
包括flu亚麻等。有店面也有onsite。
1. LRU cache
2. 一个整数数组，先递增然后递减，也有可能只有递增或者递减。查找某个整数在不
在数组里。
3. 设计Boggle游戏
4. OO design, 用树形结构表示表达式。注意operator要用多态实现。
5. 2 sum，一个元素只能用一次
6. 1）判断一个数组中是否有3个元素和为0，元素可以重用。2）merge k sorted
array。3）稀疏向量的点乘。
7. 一个数组，把非0的元素移动到开头。
8. 1） maximum subarray 2）树里两个节点的最低公共祖先 3）LC subset
9. 设计fb newsfeed
10. 大数相乘
11. 1） 给一段话，再给两个单词，求这两个单词在这段话里的最小距离 2）打印二叉
树（level order遍历）
12. 随机洗牌算法
13. 1）给一个字符串，返回每个字符及其个数。比如：aaabcc-> 3a1b2c 2) 给字符及
其个数，返回原本的字符串 3）media... 阅读全帖 |
|
f*******r
发帖数: 976 | 27 多谢分享，希望你早日拿到大offer
找工作告一段落，把前一段面试的题目整理一下一起发出来。各个公司的放在一起了，
包括flu亚麻等。有店面也有onsite。
1. LRU cache
2. 一个整数数组，先递增然后递减，也有可能只有递增或者递减。查找某个整数在不
在数组里。
3. 设计Boggle游戏
4. OO design, 用树形结构表示表达式。注意operator要用多态实现。
5. 2 sum，一个元素只能用一次
6. 1）判断一个数组中是否有3个元素和为0，元素可以重用。2）merge k sorted
array。3）稀疏向量的点乘。
7. 一个数组，把非0的元素移动到开头。
8. 1） maximum subarray 2）树里两个节点的最低公共祖先 3）LC subset
9. 设计fb newsfeed
10. 大数相乘
11. 1） 给一段话，再给两个单词，求这两个单词在这段话里的最小距离 2）打印二叉
树（level order遍历）
12. 随机洗牌算法
13. 1）给一个字符串，返回每个字符及其个数。比如：aaabcc-> 3a1b2c 2) 给字符及
... 阅读全帖 |
|
k****r
发帖数: 807 | 28 版上好心人帮忙内荐的，在这里表示感谢。
店面：
sudoku solver。
昂塞：4轮
1.1 anagrams，秒了。
1.2 input String“[email protected]
/* */..[email protected]
/* */^^^2134nn..uber@
hello.edu.cn”
output 返回所有合理的address。java写到后来没写完，但是思路被认可。
2. input(String[] str1, String[] str2) 返回match str2里任一个的所有str1中的
元素（白板）。比如说str2是“hiw”，“abc”； str1是“hiw2”，“3hiw”， “
def”，“abc1”，应该返回“hiw2”，“3hiw”，“abc1”。这题交流不顺畅，写出
来一种方法，他看半天不懂，解释了半天，他似懂非懂，又说我的方法不efficient，
最后我似乎明白他要考啥，我说了一个treemap来解决的办法，他说ok，没时间再写
code了，也不知道是不是真的ok。
3. 聊messaging sy... 阅读全帖 |
|
f*******r
发帖数: 976 | 29 Move on.
店面：
sudoku solver。
昂塞：4轮
1.1 anagrams，秒了。
1.2 input String“[email protected]
/* */..[email protected]
/* */^^^2134nn..uber@
hello.edu.cn” output 返回所有合理的address。java写到后来没写完，但是思路被
认可。
2. input(String[] str1, String[] str2) 返回match str2里任一个的所有str1中的
元素（白板）。比如说str2是“hiw”，“abc”； str1是“hiw2”，“3hiw”， “
def”，“abc1”，应该返回“hiw2”，“3hiw”，“abc1”。这题交流不顺畅，写出
来一种方法，他看半天不懂，解释了半天，他似懂非懂，又说我的方法不efficient，
最后我似乎明白他要考啥，我说了一个treemap来解决的办法，他说ok，没时间再写
code了，也不知道是不是真的ok。
3. 聊messaging system，聊背景。考了个a... 阅读全帖 |
|
I**********a
发帖数: 1183 | 30 发一批跪了的面经吧，大多都是LC原题，所以一直也没发，跪的原因除个别是被黑，大
多确实是自己没吃透，大牛们看着笑笑就好了
1. Top K : Min/Max heap (搞对用哪个，不然 O(nlogk)就变成 O(nlogn), partial
quickselect
2. round robin iterator: 注意循环时，应该剪去空的sub-iterator以降低外层循环
次数
3. using stack implement queue: 1号stack倒到2号了，不用倒回来
4. LRU cashe: JAVA里linkedhashmap就已经实现了，被问到了不知道被鄙视。。
5. uni-value tree: 用了global variable图省事，被逮住问有什么不好，怎么解决
，以后再不给自己挖这种坑了，老老实实Pair返回
其他各种原题：
topology sort
maximum subarray ( less than a target sum, LC原题好像是〉=target)
text justification
number o... 阅读全帖 |
|
c*****m
发帖数: 271 | 31 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点 |
|
j*****8
发帖数: 3635 | 32 这个有啥tricky的地方吗，难道不是加个condition check currSum >= target 就行？ |
|
c*****m
发帖数: 271 | 33 curSum < target的时候怎么操作呢？ |
|
j*****8
发帖数: 3635 | 34 继续加
if currSum < 0 then currSum = 0
else if currSum >= target && currSum > curMax then currMax = currSum
没仔细想，可能不对 |
|
j*****8
发帖数: 3635 | 35 那个也一样吧，只是不记录currMaxSum，而是currMaxLength
contiguous |
|
c*****m
发帖数: 271 | 36 这种情况的话，在curSum < target时，不能把curSum重置０吧？比如target = 10,
array=[-1, 100]，最大长度是２，而不是１ |
|
|
|
|
i******l
发帖数: 270 | 40 我想到了一个办法，刚刚试了一下，确实是O(N)的。
思路就是从两头往中间凑，先得到全部的和，如果满足条件就返回了，
如果不满足，比较两头的大小，每次减去小的那个，然后走一步，代码如下：
int maxSubLen( vector& data, int bar ) {
int sz = data.size(), sum = 0;
for( int i=0; i
if( sum >= bar ) return sz;
int i = 0, j = sz-1;
while( i < j ) {
if( data[i] < data[j] ) sum -= data[i++];
else sum -= data[j--];
if( sum >= bar ) return j - i + 1;
}
return 0... 阅读全帖 |
|
a********g
发帖数: 36 | 41 有个反例子：｛1，1，1，1，1，-9，7｝，target:5
正确的答案是1，1，1，1，1长度是5
而你的解法的答案是7，长度只有1 |
|
y*********e
发帖数: 518 | 42 如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
slicing window就好。
若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。 |
|
b*****n
发帖数: 618 | 43 又想了一下，其实是有O(N)的解的。
先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
，并且要j - i的值最大。
所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
举个例子，如果b = [5, 4, 2, 8, 3, 7]
那么i的可能其实只有index 0,1,2,
j的可能其实只有index 3,5
然后用两个pointer分别从这两个序列的尾部开始往前移动就可以了，时间复杂度整体
上是O(N)因为上面每一步都是O(N) |
|
y*********e
发帖数: 518 | 44
tar
subsequence。
举个例子：b = [1, 5, 9, 4, 2, 8, 3, 7, 9]
按照你的算法，如何求 i 和 j 呢？ |
|
b*****n
发帖数: 618 | 45 这种情况下i只可能是0，因为后面没有比1小的了
j只可能是8，因为前面没有比9大的了
这个array里面没有比9-1更好也更长的b[j] - b[i]了 |
|
j*****8
发帖数: 3635 | 46 但如果当前 i, j 不满足条件并且 i 向右 j 向左 都可以时，先移动哪一个？
我把你的例子b稍微改了下 b = [6, 5,4,10,3,7], target = 4
i 还是可选 0,1,2；j 还是可选3，5
i = 0, j = 5 时不满足条件，这个时候先移 i 还是 j？ 感觉按你的算法应该先移 i
， 但那样就拿不到 i = 0 j = 3 的解了？
tar
subsequence。 |
|
b*****n
发帖数: 618 | 47 这个例子里面
i可以选 0，1，2，4
j可以选3，5
i和j都应该从最右边，也就是最大的index开始往左边走，跟sliding window的思路类
似，i开始是4，j开始是5，如果发现a[j] - a[i] >= tar就移动i，反之移动j，相当于
对每个可能的j求最小的i是多少
i |
|
j*****8
发帖数: 3635 | 48
~~~~~~~~~~~~~~~~~~~~~
那时间复杂度就不是线性的了。可能都从右开始能解
决这个例子，但我总觉得还会有别的反例，虽然现在没想出来。。 |
|
b*****n
发帖数: 618 | 49 仍然是线性的，i和j都最多有n个，每一步要么i往坐移要么j往坐移，最多O(2n)。
反例应该是没有的，利用的就是两个sequence其实都是从左往右递增的序列。 |
|
|
