fb电面，题写对，follow up没答好，挂得好可惜

早上电面，题不难，都写出来了，但还是挂了，稀里糊涂的，后来回想应该是一些follow up没答好的缘故。面试的是个美国人。具体如下：第一题：是否有连续的sub数组何为target。我的代码：
public boolean containsSum(List<Integer> list, int target){
    if(list==null) return false;
    HashSet<Integer> set = new HashSet<>();
    int sum = 0;
    for(int i=0; i<list.length(); i++){
        sum = sum+list.get(i);
        set.add(sum);
        if(set.contains(sum-target)) return true;
    }
    return false;
}
后来问时空复杂度n，n。又问哪句会造成算法是n方。我没想出来，他说

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
return ret;
}
问时空复杂度，问写的这个叫什么approach，我说level order，问还叫什么我说breadth first。ok。这题应该没问题。


稀里糊涂挂了以后问hr有何feedback，只说加强cs fundamental。





补充内容 (2015-4-22 11:58):
其实第一题有个bug，面试官当时也没发现，就是应该先set.add(0);

补充内容 (2015-10-20 04:56):
第一题有个条件，数组里的数都是正数

yiliaobailiao 发表于 2015-4-30 05:58
为什么我觉得楼主第一题只是考虑了从0开始的sub了呢？还是我理解错了。。。

如果sum[i]-sum[j]=target, i>j, sum[j] (也就是target - sum[i]) 已经在hashset里存过，那么j+1到 i 就是所求的sublist，当然set里要先加个0。j 可以是大于等于0的啊

补充内容 (2015-5-1 14:13):
所有sum，都是sum[i]

补充内容 (2015-5-1 14:14):
晕，这个格式怎么搞的，我想说都是sum【 i 】

没太看明白这段：
后来问时空复杂度n，n。又问哪句会造成算法是n方。我没想出来，他说sum = sum+list.get(i);才发现input只说是list，我说如果是自己写的Linked list可能get就是n了（其实LINKEDLIST java api也是n）。
又说还有set.add(sum);我有点不明白，想了想说如果java api应该没问题，自己写的话如果initial size到了就必须重新分配一个大一点的空间把以前的copy过去，所以是n。

---arraylist.get(i) 是O(1)吧, linkedlist不能写作list啊，这行怎么会是O(n)?
set的add operation也是O（1）啊。。。这和是不是自己写的有什么关系？

yuxrose 发表于 2015-4-22 10:07
没太看明白这段：
后来问时空复杂度n，n。又问哪句会造成算法是n方。我没想出来，他说sum = sum+list.get( ...

LinkedList也是list interface里的。它的get（i）是n。但其实用iterator的方式就没事，用index i就不行了。
set.add和arraylist.add不是每次都是（1），是平均的。因为他们有一个initial size超了就重新分配个更大的空间，然后把之前的复制过去。面试官还说了what if it is full.....考到这也是给跪了

我觉得第一题唯一的问题就是有个bug似乎，如果target是0的情况下， 这两行肯定会return true的，
set.add(sum);
        if(set.contains(sum-target)) return true;

yuxrose 发表于 2015-4-22 10:10
我觉得第一题唯一的问题就是有个bug似乎，如果target是0的情况下， 这两行肯定会return true的，
set.add( ...

有道理，这题有个条件是list里是正整数。所以最开始价格条件target小于等于0直接false就行了。不过面试官也没看出来这个

magicalcan 发表于 2015-4-22 12:35
LinkedList也是list interface里的。它的get（i）是n。但其实用iterator的方式就没事，用index i就不行了 ...

我觉得知识点考的太细了。。。有点挑刺的感觉。。。
祝福lz，这次肯定攒了不少人品。。。。

。。。。条件里面有list里面都是正整数啊。。。这个经典的min window题为啥没有准备好。。。

http://www.geeksforgeeks.org/find-subarray-with-given-sum/

楼主挂的原因我觉得应该是没有给出面试官想要的解法

zq13667243992 发表于 2015-4-22 13:35
http://www.geeksforgeeks.org/find-subarray-with-given-sum/

楼主挂的原因我觉得应该是没有给出面试官 ...

你是说那个two pointer一起移动的解法吗？但关键是面试官并没有要求lz优化啊，他如果问，有没有in place的做法，lz也许也准备了这个solution啊，可是他一直纠结时间复杂度怎么优化，而不是空间复杂度，然后又挂lz，还是很可惜吧。。

fb最近还在面全职？LZ是experienced的engineer么？