logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
FB电面面经
avatar
FB电面面经# JobHunting - 待字闺中
x*j
1 楼
投了2个月简历，就一共电面了3家。。。长期求内推啊！！！
一个小时前的FB电面， 电面的是个老印，一共出了3个题。
1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
which sums to total.
都是正数， 第一次没注意contiguous，给了个back tracking的解法。然后说是
contiguous， 给了
个维护窗口的解法，不过犯了个小错误。时间过去了半小时。。。
2) palindrome String
边讲边写，写了一半3分钟时说我明白你的思路了。继续下一个题吧。
3) decode ways.
边讲边写，做了7，8分钟刚写完就说我明白你的思路了，好了。
目测得跪。。。求祈福哦。。。。
avatar
p*p
2 楼
第一题，为什么搞得这么复杂呢？
不就是求所有（element i, element j）之间的和，然后检查是不是等于target吗？用
一个数组存 accumulative sum. 得到任意 i, j 之间的和只需要 constant time。
total runtime: O(n^2).
难道你的方法能比这个更优化吗？

【在 x***j 的大作中提到】
: 投了2个月简历，就一共电面了3家。。。长期求内推啊！！！
: 一个小时前的FB电面， 电面的是个老印，一共出了3个题。
: 1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
: which sums to total.
: 都是正数， 第一次没注意contiguous，给了个back tracking的解法。然后说是
: contiguous， 给了
: 个维护窗口的解法，不过犯了个小错误。时间过去了半小时。。。
: 2) palindrome String
: 边讲边写，写了一半3分钟时说我明白你的思路了。继续下一个题吧。
: 3) decode ways.
avatar
u*x
3 楼
第一题
用一个滑动窗口 left=right=0
根据窗口内sum大小决定动left还是right
复杂度N

【在 p**p 的大作中提到】
: 第一题，为什么搞得这么复杂呢？
: 不就是求所有（element i, element j）之间的和，然后检查是不是等于target吗？用
: 一个数组存 accumulative sum. 得到任意 i, j 之间的和只需要 constant time。
: total runtime: O(n^2).
: 难道你的方法能比这个更优化吗？
avatar
u*x
4 楼
不知输入是否sorted?

【在 u****x 的大作中提到】
: 第一题
: 用一个滑动窗口 left=right=0
: 根据窗口内sum大小决定动left还是right
: 复杂度N
avatar
k*r
5 楼
array 是sorted的？

【在 p**p 的大作中提到】
: 第一题，为什么搞得这么复杂呢？
: 不就是求所有（element i, element j）之间的和，然后检查是不是等于target吗？用
: 一个数组存 accumulative sum. 得到任意 i, j 之间的和只需要 constant time。
: total runtime: O(n^2).
: 难道你的方法能比这个更优化吗？
avatar
x*j
6 楼
不是sorted
sorted和unsorted 都可以用窗口吧？
avatar
k*r
7 楼
如果不是sorted，left右边滑动了，current sum要是又少了或是多了，还要左滑动回
来吗。。。。。
avatar
u*x
8 楼
嗯 但需不需要考虑负数或0呢
比如
-1, 1, -1, 1, ..., -1, 1
target是0
那有O(N^2)种sequence吧
难道只要求求有还是没有？

【在 x***j 的大作中提到】
: 不是sorted
: sorted和unsorted 都可以用窗口吧？
avatar
g*3
9 楼
不是sorted 没法用窗口
avatar
h*9
10 楼
话说今天不是他家office不上班吗？楼主怎么面的？
avatar
c*g
11 楼
O(n) solution for unsorted array.
An example
arr=[-1 4 1 0 -2 -3 7],
sum = 2
step 1: accumulate the sums
arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
step 2: traverse the acc with hash table
the hash table will store the following values
ht = [0+2, -1+2, 3+2, 4+2]
It returns when finding an element of acc in the hash table (2 in this case)
avatar
x*j
12 楼

case)
mark, 拜读一下

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
x*j
13 楼
应该上吧，我反正接到电话了。

【在 h**********9 的大作中提到】
: 话说今天不是他家office不上班吗？楼主怎么面的？
avatar
l*a
14 楼

能解释一下这步scan是怎么store这些值并使用这些值的吗
thanks
case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
c*g
15 楼
In step 2, it will go through each element in acc, check if it is in the
hash table. If not, insert the "element+target value" to the hash table, and
go on. Otherwise, it finds the contiguous elements that sum up to the
target value, returning true.

【在 l*****a 的大作中提到】
:
: 能解释一下这步scan是怎么store这些值并使用这些值的吗
: thanks
: case)
avatar
s*5
16 楼
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?

【在 l*****a 的大作中提到】
:
: 能解释一下这步scan是怎么store这些值并使用这些值的吗
: thanks
: case)
avatar
f*n
17 楼
解释的好仔细啊，我同事要被迫换题了 :)

,

【在 s***5 的大作中提到】
: 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?
avatar
g*3
18 楼
It is O(N) to find true or false, but it is still O(N*N) if want to find all
possible solution, isn't it?

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
z*m
19 楼
面自己人就接着用这题，面其他人，比如南亚的，就换题吧

【在 f******n 的大作中提到】
: 解释的好仔细啊，我同事要被迫换题了 :)
:
: ,
avatar
s*l
20 楼
smart~

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
b*g
21 楼
好牛的方法！感觉这方法也是有源可寻的，LeetCode那道Longest Consecutive
Sequence O(n)解法的升级版.
如果定义sum[i] = A[0]+A[1]+...+A[i-1]，sum本身也是一个序列
题目就转化为了在sum序列中寻找"consecutive"的两个数
而这里"consecutive"的条件是：sum[j]-sum[i]=target，且j>i
这样基本就和LC那题大同小异了。不过即使这样，面试真第一次碰到这题，能想出这样
的解法，绝对属于牛人了。

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
u*x
22 楼
对了！一看hashtable反应过来
这是leetcode最近加的那道题 求连续乘积最大值的简化版
唉 看来吃透leetcode 不容易啊

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
l*a
23 楼

这两道题有关系吗？

【在 u****x 的大作中提到】
: 对了！一看hashtable反应过来
: 这是leetcode最近加的那道题 求连续乘积最大值的简化版
: 唉 看来吃透leetcode 不容易啊
:
: case)
avatar
b*g
24 楼
好像和连续乘积那题完全两回事吧。。。那题不是min/max大法来做么。。。。

【在 u****x 的大作中提到】
: 对了！一看hashtable反应过来
: 这是leetcode最近加的那道题 求连续乘积最大值的简化版
: 唉 看来吃透leetcode 不容易啊
:
: case)
avatar
u*x
25 楼
哈 那可能就是我做那道题没用常用解 我自己鼓捣的算法
也是用total处以前半段 推出后半段的乘积
这里是用一段的和减去target 去hashtable匹配是不是有子段等于 total-target

【在 l*****a 的大作中提到】
:
: 这两道题有关系吗？
avatar
h*e
26 楼
又出极品了是吧，你干嘛非要告诉你同事？？

【在 f******n 的大作中提到】
: 解释的好仔细啊，我同事要被迫换题了 :)
:
: ,
avatar
E*Q
27 楼
如果正数array的话，可以用移动窗口的吧
avatar
h*o
28 楼
这个可以~·

【在 E****Q 的大作中提到】
: 如果正数array的话，可以用移动窗口的吧
avatar
c*q
29 楼
mark这个解法。
avatar
l*1
30 楼
好像用前后指针更好吧，O（n）time and constant space，求指导。
public boolean sumExist(int[] array, int target){
int l=0, h=0, sum=array[0];
while(l<=h){
if(sum==target)
return true;
else if(sumh++;
sum+=array[h];
}
else{
sum-=array[l];
if(ll++;
else{
h++;
l++;
}
}
}
return false;
}
avatar
g*s
31 楼
反例：
* {1,3}, 2
* {3, -1}, 2

【在 l**********1 的大作中提到】
: 好像用前后指针更好吧，O（n）time and constant space，求指导。
: public boolean sumExist(int[] array, int target){
: int l=0, h=0, sum=array[0];
: while(l<=h){
: if(sum==target)
: return true;
: else if(sum: h++;
: sum+=array[h];
: }
avatar
B*l
32 楼
also need to check i < j?

,

【在 s***5 的大作中提到】
: 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?
avatar
g*n
33 楼
我写了一下，可是结果总是不对
public boolean consum(int[] a, int target){

int[] sum = new int[a.length+1];
sum[0] = 0;
for(int i=1; isum[i] = a[i-1]+sum[i-1];
}
HashMap hm = new HashMap();
for(int i=0; iif(hm.containsKey(sum[i]+target)){
int j = hm.get(sum[i]+target);
if(jreturn true;
}

}else{
hm.put(sum[i]+target, i);
}
}
return false;

}

,

【在 s***5 的大作中提到】
: 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?
avatar
g*n
34 楼
我也觉得应该加check,不然是-2

【在 B******l 的大作中提到】
: also need to check i < j?
:
: ,
avatar
s*6
35 楼
lz收到通知没
avatar
x*j
36 楼
没有，应该挂了

【在 s******6 的大作中提到】
: lz收到通知没
avatar
h*e
37 楼
Non-negative, 移动窗口, 请指教
public static boolean sumExist(int[] array, int target){
int left = 0,right = 0;
int n = array.length;
int sum = 0;
while(rightsum += array[right];
if(sum==target){
return true;
}else if(sumright++;
}else{
while(left<=right&&sum>target){
sum -= array[left++];
if(sum==target) return true;
}
right++;
}
}
return false;
}
avatar
s*6
38 楼
哎 我25号面试的，也没有通知。。同学安慰我可能是感恩节请假的人比较多有延迟。
。希望如此。。bless

【在 x***j 的大作中提到】
: 没有，应该挂了
avatar
x*j
39 楼
bless,
不管怎样，move on 吧！

【在 s******6 的大作中提到】
: 哎 我25号面试的，也没有通知。。同学安慰我可能是感恩节请假的人比较多有延迟。
: 。希望如此。。bless
avatar
m*j
40 楼
如果都是正数的话，unsorted array应该也可以用窗口？
avatar
j*r
42 楼
有像我一样看了半天还是看不懂的吗？
给个testcase{3,-1,2} target 1，如何返回1，2？
acc[0,3,2,4]，然后？

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
w*a
43 楼
我觉得g4g的解法很赞啊，果断学习之
avatar
z*c
44 楼
楼上关于hashtable的key其实就是这个等式：
Sum(0,j)+target=sum(0,i)
Target=sum(0,i)-sum(0,j)
Return j+1,i
还是g4g的比较好理解

【在 j******r 的大作中提到】
: 有像我一样看了半天还是看不懂的吗？
: 给个testcase{3,-1,2} target 1，如何返回1，2？
: acc[0,3,2,4]，然后？
:
: case)
avatar
a*2
45 楼
典型的DP:
dp[i,j] = 1, if exists contiguous subseq up to ith element in seq summing up
to j
dp[i,j] = 0, otherwise
dp[i,0] = sep[i] == 0? 1: 0, i= 0,...,len(seq)-1
dp[0,j] = 0, j = 1,...,total
dp[i,j] = max(dp[i-1,j-seq[i]], seq[i] == j ? 1: 0)
i = 1,...,len(seq)-1
j = 1,...,total
return max(dp[i,total]) i = 0,...,len(seq)-1
O(n)
avatar
y*i
46 楼
g4g那个解法只能针对非负吧？前面那个hash的针对负数也可以？
至于楼上那个DP就完全没看懂了。。。
avatar
y*e
47 楼
hashMap 应该放sum，不是sum + target吧
public static boolean sumToTarget(int[] arr, int target){
int[] acc = new int[arr.length];
acc[0] = arr[0];
for(int i = 1; i < arr.length; i++){
acc[i] = acc[i - 1] + arr[i];
}

Map hashMap = new HashMap();
hashMap.put(0, -1);
for(int i = 0; i < acc.length; i++){
if(hashMap.containsKey(acc[i] - target)){
return true;
}
else{
hashMap.put(acc[i], i);
}
}
return false;
}

【在 g********n 的大作中提到】
: 我写了一下，可是结果总是不对
: public boolean consum(int[] a, int target){
:
: int[] sum = new int[a.length+1];
: sum[0] = 0;
: for(int i=1; i: sum[i] = a[i-1]+sum[i-1];
: }
: HashMap hm = new HashMap();
: for(int i=0; i
avatar
i*d
48 楼
hm.continsKey()里面的东西和hm.put()里面的东西应该符合下面等式
sum[i] - sum[j] = target //sum[j]是put进去的， sum[i]是后来判断contains的
你的相当于 sum[i] + target = sum[j] + target 所以不对
如果put了(sum[i]+target). 后面就要判断 hm.containsKey(sum[i])
或者可以
put(sum[i]), 后面判断hm.containsKey(sum[i]-target)
if(hm.containsKey(sum[i]+target)){
int j = hm.get(sum[i]+target);
if(jreturn true;
}

}else{
hm.put(sum[i]+target, i);

【在 g********n 的大作中提到】
: 我写了一下，可是结果总是不对
: public boolean consum(int[] a, int target){
:
: int[] sum = new int[a.length+1];
: sum[0] = 0;
: for(int i=1; i: sum[i] = a[i-1]+sum[i-1];
: }
: HashMap hm = new HashMap();
: for(int i=0; i
avatar
i*d
49 楼
你的代码里put hashmap时 i 作为value,后来没有用到，是不是用个hashset就可以了？

【在 y*****e 的大作中提到】
: hashMap 应该放sum，不是sum + target吧
: public static boolean sumToTarget(int[] arr, int target){
: int[] acc = new int[arr.length];
: acc[0] = arr[0];
: for(int i = 1; i < arr.length; i++){
: acc[i] = acc[i - 1] + arr[i];
: }
:
: Map hashMap = new HashMap();
: hashMap.put(0, -1);
avatar
y*e
50 楼
我当时放了i是因为自己写了几个test case，return的不是true or false, 而是
subarray的start和end index, 所以放了i好比较结果对不对。如果按原题只return
boolean的话，应该用hashset就可以。

了？

【在 i******d 的大作中提到】
: 你的代码里put hashmap时 i 作为value,后来没有用到，是不是用个hashset就可以了？
avatar
i*d
51 楼
我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
办法？

【在 y*****e 的大作中提到】
: 我当时放了i是因为自己写了几个test case，return的不是true or false, 而是
: subarray的start和end index, 所以放了i好比较结果对不对。如果按原题只return
: boolean的话，应该用hashset就可以。
:
: 了？
avatar
l*o
52 楼
哈希是不错的思路，不过这道题哈希就复杂化了吧
都是正数，那么左指针进则和减小（有负数则可能增大），右指针进则和增大（有负数
则可能减小），即全是正数和已排序的整数是等价的。
bool arrSum(vector &num, int sum){
int i=0,j=0,tmp=0;
while(jtmp +=num[j];
while(isum)
tmp -=num[i++];
if(tmp==sum)
return true;
j++;
}
return false;
}
avatar
l*o
53 楼
sum[i]重复有影响吗？
void arrSum(vector &num, int sum){
//vector num{1,1,1,1,1,1,1};
map mp;
vector acc(num.size());acc[0]=num[0];
for(int i=1;iacc[i]=acc[i-1]+num[i];

mp.insert(make_pair(0,-1));
for(int i=0;iif(mp.find(acc[i]-sum)==mp.end()) mp.insert(make_pair(acc[i],i));
else
cout<}
}
测试结果：
0 3
1 4
2 5
3 6

【在 i******d 的大作中提到】
: 我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
: 没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
: 办法？
avatar
l*o
54 楼
都是正数的情况下，sum[i]应该是线性增加的，如何重复？

【在 i******d 的大作中提到】
: 我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
: 没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
: 办法？
avatar
i*d
55 楼
你给的test case是原数组有重复，但是acc sum数组没有重复
考虑下面的例子：
num={5, 4, 2, -1, 3, 3, -9, 3}
acc={0, 5, 9, 11, 10, 13, 16, 7, 10}
acc出现了2个10，put hashmap的时候会有冲突，可能会丢失数据
我的实现跑上面的例子里面就漏了一组输出 (target=3应该有3组，只输出了2组，也可
能是我的实现有bug)
当然acc出现重复的条件是num里面有负数，或者0， 与原题不符

【在 l**o 的大作中提到】
: sum[i]重复有影响吗？
: void arrSum(vector &num, int sum){
: //vector num{1,1,1,1,1,1,1};
: map mp;
: vector acc(num.size());acc[0]=num[0];
: for(int i=1;i: acc[i]=acc[i-1]+num[i];
:
: mp.insert(make_pair(0,-1));
: for(int i=0;i
avatar
J*o
56 楼
这个题要马克
avatar
J*u
57 楼

all
No, it's still O(N). After you build the hash table with accumulated sum as
the key and index as the value, you iterate through the hashtable. You add
the target to the accumulated sum and get the expected sum. If you find the
expected sum in the hashtable, you know get one result. But you keep
iterating through the hash table. So it's O(N).

【在 g***3 的大作中提到】
: It is O(N) to find true or false, but it is still O(N*N) if want to find all
: possible solution, isn't it?
:
: case)
avatar
c*w
58 楼
lz说了所有都是正数.这样unsorted的可以用sliding window

【在 k****r 的大作中提到】
: 如果不是sorted，left右边滑动了，current sum要是又少了或是多了，还要左滑动回
: 来吗。。。。。
avatar
y*8
59 楼
O(n) solution for unsorted array.
这道题的正确序列是index 0-4和3-6
而hashtable存的
key value
0+2=2 , 0
-1+2=1 , 1
3+2=5 , 2
4+2=6 , 3
4+2=6 , 4
2+2=4 , 5
-1+2=1 , 6
6+2=8 , 7
key有两个1和两个6,但index对应貌似不对
请问怎么用hash table得到正确index，thanks
,
avatar
d*8
60 楼
正解, 怒顶!!

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
f*t
61 楼
key = acc[index] + target
value = list of index
放到hashtable里
如果有多个index使得acc[index]相同，那么把这些index都加到list of index里。
找的时候得到key对应的list of index，然后一个个遍历过去那些index < j的index就
是符合条件的区间[index, j]

【在 y*********8 的大作中提到】
: O(n) solution for unsorted array.
: 这道题的正确序列是index 0-4和3-6
: 而hashtable存的
: key value
: 0+2=2 , 0
: -1+2=1 , 1
: 3+2=5 , 2
: 4+2=6 , 3
: 4+2=6 , 4
: 2+2=4 , 5
avatar
d*s
62 楼
palindrome string 是 valid palindrome 还是 palindrome partition啊？

【在 x***j 的大作中提到】
: 投了2个月简历，就一共电面了3家。。。长期求内推啊！！！
: 一个小时前的FB电面， 电面的是个老印，一共出了3个题。
: 1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
: which sums to total.
: 都是正数， 第一次没注意contiguous，给了个back tracking的解法。然后说是
: contiguous， 给了
: 个维护窗口的解法，不过犯了个小错误。时间过去了半小时。。。
: 2) palindrome String
: 边讲边写，写了一半3分钟时说我明白你的思路了。继续下一个题吧。
: 3) decode ways.
avatar
I*7
63 楼
方法确实赞。
avatar
t*5
64 楼
mark
avatar
k*f
65 楼
hashTable[2,4,3]
此时对照的返回的就是 对应的index就是 0，1,2,，与acc相等下标i为1，acc里面和它
相等的就是j为2,0的下标应为-1，不就是【1,2】了
这个人说的很清楚了。
发信人: zshrc (zshrc), 信区: JobHunting
标 题: Re: FB电面面经
发信站: BBS 未名空间站 (Sat Jan 3 17:13:30 2015, 美东)
楼上关于hashtable的key其实就是这个等式：
Sum(0,j)+target=sum(0,i)
Target=sum(0,i)-sum(0,j)

【在 j******r 的大作中提到】
: 有像我一样看了半天还是看不懂的吗？
: 给个testcase{3,-1,2} target 1，如何返回1，2？
: acc[0,3,2,4]，然后？
:
: case)
avatar
t*5
66 楼
mark一下
avatar
x*j
67 楼
投了2个月简历，就一共电面了3家。。。长期求内推啊！！！
一个小时前的FB电面， 电面的是个老印，一共出了3个题。
1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
which sums to total.
都是正数， 第一次没注意contiguous，给了个back tracking的解法。然后说是
contiguous， 给了
个维护窗口的解法，不过犯了个小错误。时间过去了半小时。。。
2) palindrome String
边讲边写，写了一半3分钟时说我明白你的思路了。继续下一个题吧。
3) decode ways.
边讲边写，做了7，8分钟刚写完就说我明白你的思路了，好了。
目测得跪。。。求祈福哦。。。。
avatar
p*p
68 楼
第一题，为什么搞得这么复杂呢？
不就是求所有（element i, element j）之间的和，然后检查是不是等于target吗？用
一个数组存 accumulative sum. 得到任意 i, j 之间的和只需要 constant time。
total runtime: O(n^2).
难道你的方法能比这个更优化吗？

【在 x***j 的大作中提到】
: 投了2个月简历，就一共电面了3家。。。长期求内推啊！！！
: 一个小时前的FB电面， 电面的是个老印，一共出了3个题。
: 1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
: which sums to total.
: 都是正数， 第一次没注意contiguous，给了个back tracking的解法。然后说是
: contiguous， 给了
: 个维护窗口的解法，不过犯了个小错误。时间过去了半小时。。。
: 2) palindrome String
: 边讲边写，写了一半3分钟时说我明白你的思路了。继续下一个题吧。
: 3) decode ways.
avatar
u*x
69 楼
第一题
用一个滑动窗口 left=right=0
根据窗口内sum大小决定动left还是right
复杂度N

【在 p**p 的大作中提到】
: 第一题，为什么搞得这么复杂呢？
: 不就是求所有（element i, element j）之间的和，然后检查是不是等于target吗？用
: 一个数组存 accumulative sum. 得到任意 i, j 之间的和只需要 constant time。
: total runtime: O(n^2).
: 难道你的方法能比这个更优化吗？
avatar
u*x
70 楼
不知输入是否sorted?

【在 u****x 的大作中提到】
: 第一题
: 用一个滑动窗口 left=right=0
: 根据窗口内sum大小决定动left还是right
: 复杂度N
avatar
k*r
71 楼
array 是sorted的？

【在 p**p 的大作中提到】
: 第一题，为什么搞得这么复杂呢？
: 不就是求所有（element i, element j）之间的和，然后检查是不是等于target吗？用
: 一个数组存 accumulative sum. 得到任意 i, j 之间的和只需要 constant time。
: total runtime: O(n^2).
: 难道你的方法能比这个更优化吗？
avatar
x*j
72 楼
不是sorted
sorted和unsorted 都可以用窗口吧？
avatar
k*r
73 楼
如果不是sorted，left右边滑动了，current sum要是又少了或是多了，还要左滑动回
来吗。。。。。
avatar
u*x
74 楼
嗯 但需不需要考虑负数或0呢
比如
-1, 1, -1, 1, ..., -1, 1
target是0
那有O(N^2)种sequence吧
难道只要求求有还是没有？

【在 x***j 的大作中提到】
: 不是sorted
: sorted和unsorted 都可以用窗口吧？
avatar
g*3
75 楼
不是sorted 没法用窗口
avatar
h*9
76 楼
话说今天不是他家office不上班吗？楼主怎么面的？
avatar
c*g
77 楼
O(n) solution for unsorted array.
An example
arr=[-1 4 1 0 -2 -3 7],
sum = 2
step 1: accumulate the sums
arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
step 2: traverse the acc with hash table
the hash table will store the following values
ht = [0+2, -1+2, 3+2, 4+2]
It returns when finding an element of acc in the hash table (2 in this case)
avatar
x*j
78 楼

case)
mark, 拜读一下

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
x*j
79 楼
应该上吧，我反正接到电话了。

【在 h**********9 的大作中提到】
: 话说今天不是他家office不上班吗？楼主怎么面的？
avatar
l*a
80 楼

能解释一下这步scan是怎么store这些值并使用这些值的吗
thanks
case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
c*g
81 楼
In step 2, it will go through each element in acc, check if it is in the
hash table. If not, insert the "element+target value" to the hash table, and
go on. Otherwise, it finds the contiguous elements that sum up to the
target value, returning true.

【在 l*****a 的大作中提到】
:
: 能解释一下这步scan是怎么store这些值并使用这些值的吗
: thanks
: case)
avatar
s*5
82 楼
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?

【在 l*****a 的大作中提到】
:
: 能解释一下这步scan是怎么store这些值并使用这些值的吗
: thanks
: case)
avatar
f*n
83 楼
解释的好仔细啊，我同事要被迫换题了 :)

,

【在 s***5 的大作中提到】
: 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?
avatar
g*3
84 楼
It is O(N) to find true or false, but it is still O(N*N) if want to find all
possible solution, isn't it?

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
z*m
85 楼
面自己人就接着用这题，面其他人，比如南亚的，就换题吧

【在 f******n 的大作中提到】
: 解释的好仔细啊，我同事要被迫换题了 :)
:
: ,
avatar
s*l
86 楼
smart~

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
b*g
87 楼
好牛的方法！感觉这方法也是有源可寻的，LeetCode那道Longest Consecutive
Sequence O(n)解法的升级版.
如果定义sum[i] = A[0]+A[1]+...+A[i-1]，sum本身也是一个序列
题目就转化为了在sum序列中寻找"consecutive"的两个数
而这里"consecutive"的条件是：sum[j]-sum[i]=target，且j>i
这样基本就和LC那题大同小异了。不过即使这样，面试真第一次碰到这题，能想出这样
的解法，绝对属于牛人了。

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
u*x
88 楼
对了！一看hashtable反应过来
这是leetcode最近加的那道题 求连续乘积最大值的简化版
唉 看来吃透leetcode 不容易啊

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
l*a
89 楼

这两道题有关系吗？

【在 u****x 的大作中提到】
: 对了！一看hashtable反应过来
: 这是leetcode最近加的那道题 求连续乘积最大值的简化版
: 唉 看来吃透leetcode 不容易啊
:
: case)
avatar
b*g
90 楼
好像和连续乘积那题完全两回事吧。。。那题不是min/max大法来做么。。。。

【在 u****x 的大作中提到】
: 对了！一看hashtable反应过来
: 这是leetcode最近加的那道题 求连续乘积最大值的简化版
: 唉 看来吃透leetcode 不容易啊
:
: case)
avatar
u*x
91 楼
哈 那可能就是我做那道题没用常用解 我自己鼓捣的算法
也是用total处以前半段 推出后半段的乘积
这里是用一段的和减去target 去hashtable匹配是不是有子段等于 total-target

【在 l*****a 的大作中提到】
:
: 这两道题有关系吗？
avatar
h*e
92 楼
又出极品了是吧，你干嘛非要告诉你同事？？

【在 f******n 的大作中提到】
: 解释的好仔细啊，我同事要被迫换题了 :)
:
: ,
avatar
E*Q
93 楼
如果正数array的话，可以用移动窗口的吧
avatar
h*o
94 楼
这个可以~·

【在 E****Q 的大作中提到】
: 如果正数array的话，可以用移动窗口的吧
avatar
c*q
95 楼
mark这个解法。
avatar
l*1
96 楼
好像用前后指针更好吧，O（n）time and constant space，求指导。
public boolean sumExist(int[] array, int target){
int l=0, h=0, sum=array[0];
while(l<=h){
if(sum==target)
return true;
else if(sumh++;
sum+=array[h];
}
else{
sum-=array[l];
if(ll++;
else{
h++;
l++;
}
}
}
return false;
}
avatar
g*s
97 楼
反例：
* {1,3}, 2
* {3, -1}, 2

【在 l**********1 的大作中提到】
: 好像用前后指针更好吧，O（n）time and constant space，求指导。
: public boolean sumExist(int[] array, int target){
: int l=0, h=0, sum=array[0];
: while(l<=h){
: if(sum==target)
: return true;
: else if(sum: h++;
: sum+=array[h];
: }
avatar
B*l
98 楼
also need to check i < j?

,

【在 s***5 的大作中提到】
: 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?
avatar
g*n
99 楼
我写了一下，可是结果总是不对
public boolean consum(int[] a, int target){

int[] sum = new int[a.length+1];
sum[0] = 0;
for(int i=1; isum[i] = a[i-1]+sum[i-1];
}
HashMap hm = new HashMap();
for(int i=0; iif(hm.containsKey(sum[i]+target)){
int j = hm.get(sum[i]+target);
if(jreturn true;
}

}else{
hm.put(sum[i]+target, i);
}
}
return false;

}

,

【在 s***5 的大作中提到】
: 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?
avatar
g*n
100 楼
我也觉得应该加check,不然是-2

【在 B******l 的大作中提到】
: also need to check i < j?
:
: ,
avatar
s*6
101 楼
lz收到通知没
avatar
x*j
102 楼
没有，应该挂了

【在 s******6 的大作中提到】
: lz收到通知没
avatar
h*e
103 楼
Non-negative, 移动窗口, 请指教
public static boolean sumExist(int[] array, int target){
int left = 0,right = 0;
int n = array.length;
int sum = 0;
while(rightsum += array[right];
if(sum==target){
return true;
}else if(sumright++;
}else{
while(left<=right&&sum>target){
sum -= array[left++];
if(sum==target) return true;
}
right++;
}
}
return false;
}
avatar
s*6
104 楼
哎 我25号面试的，也没有通知。。同学安慰我可能是感恩节请假的人比较多有延迟。
。希望如此。。bless

【在 x***j 的大作中提到】
: 没有，应该挂了
avatar
x*j
105 楼
bless,
不管怎样，move on 吧！

【在 s******6 的大作中提到】
: 哎 我25号面试的，也没有通知。。同学安慰我可能是感恩节请假的人比较多有延迟。
: 。希望如此。。bless
avatar
m*j
106 楼
如果都是正数的话，unsorted array应该也可以用窗口？
avatar
j*r
108 楼
有像我一样看了半天还是看不懂的吗？
给个testcase{3,-1,2} target 1，如何返回1，2？
acc[0,3,2,4]，然后？

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
w*a
109 楼
我觉得g4g的解法很赞啊，果断学习之
avatar
z*c
110 楼
楼上关于hashtable的key其实就是这个等式：
Sum(0,j)+target=sum(0,i)
Target=sum(0,i)-sum(0,j)
Return j+1,i
还是g4g的比较好理解

【在 j******r 的大作中提到】
: 有像我一样看了半天还是看不懂的吗？
: 给个testcase{3,-1,2} target 1，如何返回1，2？
: acc[0,3,2,4]，然后？
:
: case)
avatar
a*2
111 楼
典型的DP:
dp[i,j] = 1, if exists contiguous subseq up to ith element in seq summing up
to j
dp[i,j] = 0, otherwise
dp[i,0] = sep[i] == 0? 1: 0, i= 0,...,len(seq)-1
dp[0,j] = 0, j = 1,...,total
dp[i,j] = max(dp[i-1,j-seq[i]], seq[i] == j ? 1: 0)
i = 1,...,len(seq)-1
j = 1,...,total
return max(dp[i,total]) i = 0,...,len(seq)-1
O(n)
avatar
y*i
112 楼
g4g那个解法只能针对非负吧？前面那个hash的针对负数也可以？
至于楼上那个DP就完全没看懂了。。。
avatar
y*e
113 楼
hashMap 应该放sum，不是sum + target吧
public static boolean sumToTarget(int[] arr, int target){
int[] acc = new int[arr.length];
acc[0] = arr[0];
for(int i = 1; i < arr.length; i++){
acc[i] = acc[i - 1] + arr[i];
}

Map hashMap = new HashMap();
hashMap.put(0, -1);
for(int i = 0; i < acc.length; i++){
if(hashMap.containsKey(acc[i] - target)){
return true;
}
else{
hashMap.put(acc[i], i);
}
}
return false;
}

【在 g********n 的大作中提到】
: 我写了一下，可是结果总是不对
: public boolean consum(int[] a, int target){
:
: int[] sum = new int[a.length+1];
: sum[0] = 0;
: for(int i=1; i: sum[i] = a[i-1]+sum[i-1];
: }
: HashMap hm = new HashMap();
: for(int i=0; i
avatar
i*d
114 楼
hm.continsKey()里面的东西和hm.put()里面的东西应该符合下面等式
sum[i] - sum[j] = target //sum[j]是put进去的， sum[i]是后来判断contains的
你的相当于 sum[i] + target = sum[j] + target 所以不对
如果put了(sum[i]+target). 后面就要判断 hm.containsKey(sum[i])
或者可以
put(sum[i]), 后面判断hm.containsKey(sum[i]-target)
if(hm.containsKey(sum[i]+target)){
int j = hm.get(sum[i]+target);
if(jreturn true;
}

}else{
hm.put(sum[i]+target, i);

【在 g********n 的大作中提到】
: 我写了一下，可是结果总是不对
: public boolean consum(int[] a, int target){
:
: int[] sum = new int[a.length+1];
: sum[0] = 0;
: for(int i=1; i: sum[i] = a[i-1]+sum[i-1];
: }
: HashMap hm = new HashMap();
: for(int i=0; i
avatar
i*d
115 楼
你的代码里put hashmap时 i 作为value,后来没有用到，是不是用个hashset就可以了？

【在 y*****e 的大作中提到】
: hashMap 应该放sum，不是sum + target吧
: public static boolean sumToTarget(int[] arr, int target){
: int[] acc = new int[arr.length];
: acc[0] = arr[0];
: for(int i = 1; i < arr.length; i++){
: acc[i] = acc[i - 1] + arr[i];
: }
:
: Map hashMap = new HashMap();
: hashMap.put(0, -1);
avatar
y*e
116 楼
我当时放了i是因为自己写了几个test case，return的不是true or false, 而是
subarray的start和end index, 所以放了i好比较结果对不对。如果按原题只return
boolean的话，应该用hashset就可以。

了？

【在 i******d 的大作中提到】
: 你的代码里put hashmap时 i 作为value,后来没有用到，是不是用个hashset就可以了？
avatar
i*d
117 楼
我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
办法？

【在 y*****e 的大作中提到】
: 我当时放了i是因为自己写了几个test case，return的不是true or false, 而是
: subarray的start和end index, 所以放了i好比较结果对不对。如果按原题只return
: boolean的话，应该用hashset就可以。
:
: 了？
avatar
l*o
118 楼
哈希是不错的思路，不过这道题哈希就复杂化了吧
都是正数，那么左指针进则和减小（有负数则可能增大），右指针进则和增大（有负数
则可能减小），即全是正数和已排序的整数是等价的。
bool arrSum(vector &num, int sum){
int i=0,j=0,tmp=0;
while(jtmp +=num[j];
while(isum)
tmp -=num[i++];
if(tmp==sum)
return true;
j++;
}
return false;
}
avatar
l*o
119 楼
sum[i]重复有影响吗？
void arrSum(vector &num, int sum){
//vector num{1,1,1,1,1,1,1};
map mp;
vector acc(num.size());acc[0]=num[0];
for(int i=1;iacc[i]=acc[i-1]+num[i];

mp.insert(make_pair(0,-1));
for(int i=0;iif(mp.find(acc[i]-sum)==mp.end()) mp.insert(make_pair(acc[i],i));
else
cout<}
}
测试结果：
0 3
1 4
2 5
3 6

【在 i******d 的大作中提到】
: 我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
: 没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
: 办法？
avatar
l*o
120 楼
都是正数的情况下，sum[i]应该是线性增加的，如何重复？

【在 i******d 的大作中提到】
: 我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
: 没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
: 办法？
avatar
i*d
121 楼
你给的test case是原数组有重复，但是acc sum数组没有重复
考虑下面的例子：
num={5, 4, 2, -1, 3, 3, -9, 3}
acc={0, 5, 9, 11, 10, 13, 16, 7, 10}
acc出现了2个10，put hashmap的时候会有冲突，可能会丢失数据
我的实现跑上面的例子里面就漏了一组输出 (target=3应该有3组，只输出了2组，也可
能是我的实现有bug)
当然acc出现重复的条件是num里面有负数，或者0， 与原题不符

【在 l**o 的大作中提到】
: sum[i]重复有影响吗？
: void arrSum(vector &num, int sum){
: //vector num{1,1,1,1,1,1,1};
: map mp;
: vector acc(num.size());acc[0]=num[0];
: for(int i=1;i: acc[i]=acc[i-1]+num[i];
:
: mp.insert(make_pair(0,-1));
: for(int i=0;i
avatar
J*o
122 楼
这个题要马克
avatar
J*u
123 楼

all
No, it's still O(N). After you build the hash table with accumulated sum as
the key and index as the value, you iterate through the hashtable. You add
the target to the accumulated sum and get the expected sum. If you find the
expected sum in the hashtable, you know get one result. But you keep
iterating through the hash table. So it's O(N).

【在 g***3 的大作中提到】
: It is O(N) to find true or false, but it is still O(N*N) if want to find all
: possible solution, isn't it?
:
: case)
avatar
c*w
124 楼
lz说了所有都是正数.这样unsorted的可以用sliding window

【在 k****r 的大作中提到】
: 如果不是sorted，left右边滑动了，current sum要是又少了或是多了，还要左滑动回
: 来吗。。。。。
avatar
y*8
125 楼
O(n) solution for unsorted array.
这道题的正确序列是index 0-4和3-6
而hashtable存的
key value
0+2=2 , 0
-1+2=1 , 1
3+2=5 , 2
4+2=6 , 3
4+2=6 , 4
2+2=4 , 5
-1+2=1 , 6
6+2=8 , 7
key有两个1和两个6,但index对应貌似不对
请问怎么用hash table得到正确index，thanks
,
avatar
d*8
126 楼
正解, 怒顶!!

case)

【在 c*******g 的大作中提到】
: O(n) solution for unsorted array.
: An example
: arr=[-1 4 1 0 -2 -3 7],
: sum = 2
: step 1: accumulate the sums
: arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front
: step 2: traverse the acc with hash table
: the hash table will store the following values
: ht = [0+2, -1+2, 3+2, 4+2]
: It returns when finding an element of acc in the hash table (2 in this case)
avatar
f*t
127 楼
key = acc[index] + target
value = list of index
放到hashtable里
如果有多个index使得acc[index]相同，那么把这些index都加到list of index里。
找的时候得到key对应的list of index，然后一个个遍历过去那些index < j的index就
是符合条件的区间[index, j]

【在 y*********8 的大作中提到】
: O(n) solution for unsorted array.
: 这道题的正确序列是index 0-4和3-6
: 而hashtable存的
: key value
: 0+2=2 , 0
: -1+2=1 , 1
: 3+2=5 , 2
: 4+2=6 , 3
: 4+2=6 , 4
: 2+2=4 , 5
avatar
d*s
128 楼
palindrome string 是 valid palindrome 还是 palindrome partition啊？

【在 x***j 的大作中提到】
: 投了2个月简历，就一共电面了3家。。。长期求内推啊！！！
: 一个小时前的FB电面， 电面的是个老印，一共出了3个题。
: 1) 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
: which sums to total.
: 都是正数， 第一次没注意contiguous，给了个back tracking的解法。然后说是
: contiguous， 给了
: 个维护窗口的解法，不过犯了个小错误。时间过去了半小时。。。
: 2) palindrome String
: 边讲边写，写了一半3分钟时说我明白你的思路了。继续下一个题吧。
: 3) decode ways.
avatar
I*7
129 楼
方法确实赞。
avatar
t*5
130 楼
mark
avatar
k*f
131 楼
hashTable[2,4,3]
此时对照的返回的就是 对应的index就是 0，1,2,，与acc相等下标i为1，acc里面和它
相等的就是j为2,0的下标应为-1，不就是【1,2】了
这个人说的很清楚了。
发信人: zshrc (zshrc), 信区: JobHunting
标 题: Re: FB电面面经
发信站: BBS 未名空间站 (Sat Jan 3 17:13:30 2015, 美东)
楼上关于hashtable的key其实就是这个等式：
Sum(0,j)+target=sum(0,i)
Target=sum(0,i)-sum(0,j)

【在 j******r 的大作中提到】
: 有像我一样看了半天还是看不懂的吗？
: 给个testcase{3,-1,2} target 1，如何返回1，2？
: acc[0,3,2,4]，然后？
:
: case)
avatar
t*5
132 楼
mark一下
avatar
p*9
133 楼
mark
相关阅读
上市公司的stock option值钱吗Amazon onsite面经pre opt申请起来快吗？如果有两个degree，可以选其中一个申请opt么？large-scale, distributed system如何准备？请教去过bloomberg onsite的人amazon约好了电话面试但是没有发邮件怎么办？have I made a mistake? ask for comments请问今年12月毕业的话，现在要申请h1b吗amazon一道面试题刚onsite完, 贴面经, 一个中等的硬件上市公司--加了详细的inte很纠结，我适合裸奔吗？急！博士期间拿硕士学位找工作，education怎么写citi现在sponsor H1b么？H1b 问题谁知道麻州或附近搞图像处理或医学图像的公司？问道多线程的简单题目[discussion] how to approve that the given 9*9 is a sudoku请问一下hiring manager是什么职位，会问什么问题？请帮忙看看谁能解决这个单片机的问题
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。