x***j
发帖数: 75 | 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分钟刚写完就说我明白你的思路了，好了。
目测得跪。。。求祈福哦。。。。 |
p**p
发帖数: 742 | 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.
|
u****x
发帖数: 97 | 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).
: 难道你的方法能比这个更优化吗？
|
u****x
发帖数: 97 | 4 不知输入是否sorted?
【在 u****x 的大作中提到】
: 第一题
: 用一个滑动窗口 left=right=0
: 根据窗口内sum大小决定动left还是right
: 复杂度N
|
k****r
发帖数: 807 | 5 array 是sorted的？
【在 p**p 的大作中提到】
: 第一题，为什么搞得这么复杂呢？
: 不就是求所有（element i, element j）之间的和，然后检查是不是等于target吗？用
: 一个数组存 accumulative sum. 得到任意 i, j 之间的和只需要 constant time。
: total runtime: O(n^2).
: 难道你的方法能比这个更优化吗？
|
x***j
发帖数: 75 | 6 不是sorted
sorted和unsorted 都可以用窗口吧？ |
k****r
发帖数: 807 | 7 如果不是sorted，left右边滑动了，current sum要是又少了或是多了，还要左滑动回
来吗。。。。。 |
u****x
发帖数: 97 | 8 嗯 但需不需要考虑负数或0呢
比如
-1, 1, -1, 1, ..., -1, 1
target是0
那有O(N^2)种sequence吧
难道只要求求有还是没有？
【在 x***j 的大作中提到】
: 不是sorted
: sorted和unsorted 都可以用窗口吧？
|
g***3
发帖数: 2304 | |
h**********9
发帖数: 43 | 10 话说今天不是他家office不上班吗？楼主怎么面的？ |
|
|
c*******g
发帖数: 332 | 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) |
x***j
发帖数: 75 | 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)
|
x***j
发帖数: 75 | 13 应该上吧，我反正接到电话了。
【在 h**********9 的大作中提到】
: 话说今天不是他家office不上班吗？楼主怎么面的？
|
l*****a
发帖数: 14598 | 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)
|
c*******g
发帖数: 332 | 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)
|
s***5
发帖数: 2136 | 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)
|
f******n
发帖数: 198 | 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?
|
g***3
发帖数: 2304 | 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)
|
z***m
发帖数: 1602 | 19 面自己人就接着用这题，面其他人，比如南亚的，就换题吧
【在 f******n 的大作中提到】
: 解释的好仔细啊，我同事要被迫换题了 :)
:
: ,
|
s********l
发帖数: 998 | 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)
|
|
|
b******g
发帖数: 3616 | 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)
|
u****x
发帖数: 97 | 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)
|
l*****a
发帖数: 14598 | 23
这两道题有关系吗？
【在 u****x 的大作中提到】
: 对了！一看hashtable反应过来
: 这是leetcode最近加的那道题 求连续乘积最大值的简化版
: 唉 看来吃透leetcode 不容易啊
:
: case)
|
b******g
发帖数: 3616 | 24 好像和连续乘积那题完全两回事吧。。。那题不是min/max大法来做么。。。。
【在 u****x 的大作中提到】
: 对了！一看hashtable反应过来
: 这是leetcode最近加的那道题 求连续乘积最大值的简化版
: 唉 看来吃透leetcode 不容易啊
:
: case)
|
u****x
发帖数: 97 | 25 哈 那可能就是我做那道题没用常用解 我自己鼓捣的算法
也是用total处以前半段 推出后半段的乘积
这里是用一段的和减去target 去hashtable匹配是不是有子段等于 total-target
【在 l*****a 的大作中提到】
:
: 这两道题有关系吗？
|
h****e
发帖数: 2125 | 26 又出极品了是吧，你干嘛非要告诉你同事？？
【在 f******n 的大作中提到】
: 解释的好仔细啊，我同事要被迫换题了 :)
:
: ,
|
E****Q
发帖数: 2 | |
h*********o
发帖数: 230 | 28 这个可以~·
【在 E****Q 的大作中提到】
: 如果正数array的话，可以用移动窗口的吧
|
c**q
发帖数: 94 | |
l**********1
发帖数: 415 | 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(sum
h++;
sum+=array[h];
}
else{
sum-=array[l];
if(l
l++;
else{
h++;
l++;
}
}
}
return false;
} |
|
|
g***s
发帖数: 3811 | 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];
: }
|
B******l
发帖数: 262 | 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?
|
g********n
发帖数: 447 | 33 我写了一下，可是结果总是不对
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
if(hm.containsKey(sum[i]+target)){
int j = hm.get(sum[i]+target);
if(j
return 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?
|
g********n
发帖数: 447 | 34 我也觉得应该加check,不然是-2
【在 B******l 的大作中提到】
: also need to check i < j?
:
: ,
|
s******6
发帖数: 57 | |
x***j
发帖数: 75 | 36 没有，应该挂了
【在 s******6 的大作中提到】
: lz收到通知没
|
h***e
发帖数: 123 | 37 Non-negative, 移动窗口, 请指教
public static boolean sumExist(int[] array, int target){
int left = 0,right = 0;
int n = array.length;
int sum = 0;
while(right
sum += array[right];
if(sum==target){
return true;
}else if(sum
right++;
}else{
while(left<=right&&sum>target){
sum -= array[left++];
if(sum==target) return true;
}
right++;
}
}
return false;
} |
s******6
发帖数: 57 | 38 哎 我25号面试的，也没有通知。。同学安慰我可能是感恩节请假的人比较多有延迟。
。希望如此。。bless
【在 x***j 的大作中提到】
: 没有，应该挂了
|
x***j
发帖数: 75 | 39 bless,
不管怎样，move on 吧！
【在 s******6 的大作中提到】
: 哎 我25号面试的，也没有通知。。同学安慰我可能是感恩节请假的人比较多有延迟。
: 。希望如此。。bless
|
m******j
发帖数: 2 | 40 如果都是正数的话，unsorted array应该也可以用窗口？ |
|
|
s*********p
发帖数: 130 | |
j******r
发帖数: 98 | 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)
|
w****a
发帖数: 710 | |
z***c
发帖数: 78 | 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)
|
a*****2
发帖数: 96 | 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) |
y*****i
发帖数: 141 | 46 g4g那个解法只能针对非负吧？前面那个hash的针对负数也可以？
至于楼上那个DP就完全没看懂了。。。 |
y*****e
发帖数: 712 | 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
|
i******d
发帖数: 61 | 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(j
return 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
|
i******d
发帖数: 61 | 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);
|
y*****e
发帖数: 712 | 50 我当时放了i是因为自己写了几个test case，return的不是true or false, 而是
subarray的start和end index, 所以放了i好比较结果对不对。如果按原题只return
boolean的话，应该用hashset就可以。
了？
【在 i******d 的大作中提到】
: 你的代码里put hashmap时 i 作为value,后来没有用到，是不是用个hashset就可以了？
|
|
|
i******d
发帖数: 61 | 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就可以。
:
: 了？
|
l**o
发帖数: 25 | 52 哈希是不错的思路，不过这道题哈希就复杂化了吧
都是正数，那么左指针进则和减小（有负数则可能增大），右指针进则和增大（有负数
则可能减小），即全是正数和已排序的整数是等价的。
bool arrSum(vector &num, int sum){
int i=0,j=0,tmp=0;
while(j
tmp +=num[j];
while(isum)
tmp -=num[i++];
if(tmp==sum)
return true;
j++;
}
return false;
} |
l**o
发帖数: 25 | 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;i
acc[i]=acc[i-1]+num[i];
mp.insert(make_pair(0,-1));
for(int i=0;i
if(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的信息。不知道有什么好
: 办法？
|
l**o
发帖数: 25 | 54 都是正数的情况下，sum[i]应该是线性增加的，如何重复？
【在 i******d 的大作中提到】
: 我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
: 没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
: 办法？
|
i******d
发帖数: 61 | 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
|
J*******o
发帖数: 741 | |
J******u
发帖数: 42 | 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)
|
c******w
发帖数: 1108 | 58 lz说了所有都是正数.这样unsorted的可以用sliding window
【在 k****r 的大作中提到】
: 如果不是sorted，left右边滑动了，current sum要是又少了或是多了，还要左滑动回
: 来吗。。。。。
|
y*********8
发帖数: 387 | 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
, |
d*******8
发帖数: 23 | 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)
|
|
|
f*****t
发帖数: 34 | 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
|
d*********s
发帖数: 9 | 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.
|
I*********7
发帖数: 125 | |
t******5
发帖数: 30 | |
k****f
发帖数: 19 | 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)
|
t******5
发帖数: 30 | |
x***j
发帖数: 75 | 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分钟刚写完就说我明白你的思路了，好了。
目测得跪。。。求祈福哦。。。。 |
p**p
发帖数: 742 | 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.
|
u****x
发帖数: 97 | 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).
: 难道你的方法能比这个更优化吗？
|
u****x
发帖数: 97 | 70 不知输入是否sorted?
【在 u****x 的大作中提到】
: 第一题
: 用一个滑动窗口 left=right=0
: 根据窗口内sum大小决定动left还是right
: 复杂度N
|
|
|
k****r
发帖数: 807 | 71 array 是sorted的？
【在 p**p 的大作中提到】
: 第一题，为什么搞得这么复杂呢？
: 不就是求所有（element i, element j）之间的和，然后检查是不是等于target吗？用
: 一个数组存 accumulative sum. 得到任意 i, j 之间的和只需要 constant time。
: total runtime: O(n^2).
: 难道你的方法能比这个更优化吗？
|
x***j
发帖数: 75 | 72 不是sorted
sorted和unsorted 都可以用窗口吧？ |
k****r
发帖数: 807 | 73 如果不是sorted，left右边滑动了，current sum要是又少了或是多了，还要左滑动回
来吗。。。。。 |
u****x
发帖数: 97 | 74 嗯 但需不需要考虑负数或0呢
比如
-1, 1, -1, 1, ..., -1, 1
target是0
那有O(N^2)种sequence吧
难道只要求求有还是没有？
【在 x***j 的大作中提到】
: 不是sorted
: sorted和unsorted 都可以用窗口吧？
|
g***3
发帖数: 2304 | |
h**********9
发帖数: 43 | 76 话说今天不是他家office不上班吗？楼主怎么面的？ |
c*******g
发帖数: 332 | 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) |
x***j
发帖数: 75 | 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)
|
x***j
发帖数: 75 | 79 应该上吧，我反正接到电话了。
【在 h**********9 的大作中提到】
: 话说今天不是他家office不上班吗？楼主怎么面的？
|
l*****a
发帖数: 14598 | 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)
|
|
|
c*******g
发帖数: 332 | 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)
|
s***5
发帖数: 2136 | 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)
|
f******n
发帖数: 198 | 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?
|
g***3
发帖数: 2304 | 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)
|
z***m
发帖数: 1602 | 85 面自己人就接着用这题，面其他人，比如南亚的，就换题吧
【在 f******n 的大作中提到】
: 解释的好仔细啊，我同事要被迫换题了 :)
:
: ,
|
s********l
发帖数: 998 | 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)
|
b******g
发帖数: 3616 | 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)
|
u****x
发帖数: 97 | 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)
|
l*****a
发帖数: 14598 | 89
这两道题有关系吗？
【在 u****x 的大作中提到】
: 对了！一看hashtable反应过来
: 这是leetcode最近加的那道题 求连续乘积最大值的简化版
: 唉 看来吃透leetcode 不容易啊
:
: case)
|
b******g
发帖数: 3616 | 90 好像和连续乘积那题完全两回事吧。。。那题不是min/max大法来做么。。。。
【在 u****x 的大作中提到】
: 对了！一看hashtable反应过来
: 这是leetcode最近加的那道题 求连续乘积最大值的简化版
: 唉 看来吃透leetcode 不容易啊
:
: case)
|
|
|
u****x
发帖数: 97 | 91 哈 那可能就是我做那道题没用常用解 我自己鼓捣的算法
也是用total处以前半段 推出后半段的乘积
这里是用一段的和减去target 去hashtable匹配是不是有子段等于 total-target
【在 l*****a 的大作中提到】
:
: 这两道题有关系吗？
|
h****e
发帖数: 2125 | 92 又出极品了是吧，你干嘛非要告诉你同事？？
【在 f******n 的大作中提到】
: 解释的好仔细啊，我同事要被迫换题了 :)
:
: ,
|
E****Q
发帖数: 2 | |
h*********o
发帖数: 230 | 94 这个可以~·
【在 E****Q 的大作中提到】
: 如果正数array的话，可以用移动窗口的吧
|
c**q
发帖数: 94 | |
l**********1
发帖数: 415 | 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(sum
h++;
sum+=array[h];
}
else{
sum-=array[l];
if(l
l++;
else{
h++;
l++;
}
}
}
return false;
} |
g***s
发帖数: 3811 | 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];
: }
|
B******l
发帖数: 262 | 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?
|
g********n
发帖数: 447 | 99 我写了一下，可是结果总是不对
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
if(hm.containsKey(sum[i]+target)){
int j = hm.get(sum[i]+target);
if(j
return 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?
|
g********n
发帖数: 447 | 100 我也觉得应该加check,不然是-2
【在 B******l 的大作中提到】
: also need to check i < j?
:
: ,
|
|
|
s******6
发帖数: 57 | |
x***j
发帖数: 75 | 102 没有，应该挂了
【在 s******6 的大作中提到】
: lz收到通知没
|
h***e
发帖数: 123 | 103 Non-negative, 移动窗口, 请指教
public static boolean sumExist(int[] array, int target){
int left = 0,right = 0;
int n = array.length;
int sum = 0;
while(right
sum += array[right];
if(sum==target){
return true;
}else if(sum
right++;
}else{
while(left<=right&&sum>target){
sum -= array[left++];
if(sum==target) return true;
}
right++;
}
}
return false;
} |
s******6
发帖数: 57 | 104 哎 我25号面试的，也没有通知。。同学安慰我可能是感恩节请假的人比较多有延迟。
。希望如此。。bless
【在 x***j 的大作中提到】
: 没有，应该挂了
|
x***j
发帖数: 75 | 105 bless,
不管怎样，move on 吧！
【在 s******6 的大作中提到】
: 哎 我25号面试的，也没有通知。。同学安慰我可能是感恩节请假的人比较多有延迟。
: 。希望如此。。bless
|
m******j
发帖数: 2 | 106 如果都是正数的话，unsorted array应该也可以用窗口？ |
s*********p
发帖数: 130 | |
j******r
发帖数: 98 | 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)
|
w****a
发帖数: 710 | |
z***c
发帖数: 78 | 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)
|
|
|
a*****2
发帖数: 96 | 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) |
y*****i
发帖数: 141 | 112 g4g那个解法只能针对非负吧？前面那个hash的针对负数也可以？
至于楼上那个DP就完全没看懂了。。。 |
y*****e
发帖数: 712 | 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
|
i******d
发帖数: 61 | 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(j
return 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
|
i******d
发帖数: 61 | 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);
|
y*****e
发帖数: 712 | 116 我当时放了i是因为自己写了几个test case，return的不是true or false, 而是
subarray的start和end index, 所以放了i好比较结果对不对。如果按原题只return
boolean的话，应该用hashset就可以。
了？
【在 i******d 的大作中提到】
: 你的代码里put hashmap时 i 作为value,后来没有用到，是不是用个hashset就可以了？
|
i******d
发帖数: 61 | 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就可以。
:
: 了？
|
l**o
发帖数: 25 | 118 哈希是不错的思路，不过这道题哈希就复杂化了吧
都是正数，那么左指针进则和减小（有负数则可能增大），右指针进则和增大（有负数
则可能减小），即全是正数和已排序的整数是等价的。
bool arrSum(vector &num, int sum){
int i=0,j=0,tmp=0;
while(j
tmp +=num[j];
while(isum)
tmp -=num[i++];
if(tmp==sum)
return true;
j++;
}
return false;
} |
l**o
发帖数: 25 | 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;i
acc[i]=acc[i-1]+num[i];
mp.insert(make_pair(0,-1));
for(int i=0;i
if(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的信息。不知道有什么好
: 办法？
|
l**o
发帖数: 25 | 120 都是正数的情况下，sum[i]应该是线性增加的，如何重复？
【在 i******d 的大作中提到】
: 我也写了一下想return所有符合条件的subarray的start和end index,发现用hashmap也
: 没法return全，因为有可能sum[i]会重复，这样会丢掉一些i的信息。不知道有什么好
: 办法？
|
|
|
i******d
发帖数: 61 | 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
|
J*******o
发帖数: 741 | |
J******u
发帖数: 42 | 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)
|
c******w
发帖数: 1108 | 124 lz说了所有都是正数.这样unsorted的可以用sliding window
【在 k****r 的大作中提到】
: 如果不是sorted，left右边滑动了，current sum要是又少了或是多了，还要左滑动回
: 来吗。。。。。
|
y*********8
发帖数: 387 | 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
, |
d*******8
发帖数: 23 | 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)
|
f*****t
发帖数: 34 | 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
|
d*********s
发帖数: 9 | 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.
|
I*********7
发帖数: 125 | |
t******5
发帖数: 30 | |
|
|
k****f
发帖数: 19 | 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)
|
t******5
发帖数: 30 | |
p*****9
发帖数: 273 | |
