一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3361|回复: 32
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
magicalcan 发表于 2015-4-22 06:27:06 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Fail在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
早上电面,题不难,都写出来了,但还是挂了,稀里糊涂的,后来回想应该是一些follow up没答好的缘故。面试的是个美国人。具体如下:第一题:是否有连续的sub数组何为target。我的代码:
public boolean containsSum(List<Integer> list, int target){
    if(list==null) return false;. Waral 鍗氬鏈夋洿澶氭枃绔,
    HashSet<Integer> set = new HashSet<>();. 1point 3acres 璁哄潧
    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方。我没想出来,他说sum = sum+list.get(i);才发现input只说是list,我说如果是自己写的Linked list可能get就是n了(其实LINKEDLIST java api也是n)。
又说还有set.add(sum);我有点不明白,想了想说如果java api应该没问题,自己写的话如果initial size到了就必须重新分配一个大一点的空间把以前的copy过去,所以是n。
后来才知道,其实java api如果装满了的情况也一样是n。我估计就是因为这个挂了。.鐣欏璁哄潧-涓浜-涓夊垎鍦
这题如果for loop用:for(int n: list), 然后hashset用new HashSet(list.size())应该就行了。. From 1point 3acres bbs
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题,只剩大概15,6分钟. 输出一个树(不一定二叉)的每层node数,迅速写. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
public List<Integer> count(Node root){
    if(root==null) return null;
    Queue<Node> q = new LinkedList<>();
    List<Integer> ret = new ArrayList<>();
    q.offer(root);
    while(!q.isEmpty()){
        int curSize = q.size();
        ret.add(curSize);
        for(int i=0; i<curSize; i++){
            Node n = q.poll();
            for(Node child : n.children){
                q.offer(child);.鏈枃鍘熷垱鑷1point3acres璁哄潧
            }
        }
    }
    return ret;.鏈枃鍘熷垱鑷1point3acres璁哄潧
}

问时空复杂度,问写的这个叫什么approach,我说level order,问还叫什么我说breadth first。ok。这题应该没问题。


稀里糊涂挂了以后问hr有何feedback,只说加强cs fundamental。
. 1point3acres.com/bbs




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

补充内容 (2015-10-20 04:56):.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一题有个条件,数组里的数都是正数

评分

6

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
 楼主| magicalcan 发表于 2015-5-1 14:12:58 | 显示全部楼层
yiliaobailiao 发表于 2015-4-30 05:58
为什么我觉得楼主第一题只是考虑了从0开始的sub了呢?还是我理解错了。。。
. 1point 3acres 璁哄潧
如果sum-sum[j]=target, i>j, sum[j] (也就是target - sum) 已经在hashset里存过,那么j+1到 i 就是所求的sublist,当然set里要先加个0。j 可以是大于等于0的啊
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-5-1 14:13):
所有sum,都是sum
. visit 1point3acres.com for more.
补充内容 (2015-5-1 14:14):
晕,这个格式怎么搞的,我想说都是sum【 i 】
回复 支持 1 反对 0

使用道具 举报

yuxrose 发表于 2015-4-22 10:07:51 | 显示全部楼层
没太看明白这段:
后来问时空复杂度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:10:57 | 显示全部楼层
我觉得第一题唯一的问题就是有个bug似乎,如果target是0的情况下, 这两行肯定会return true的,
set.add(sum);. 1point 3acres 璁哄潧
        if(set.contains(sum-target)) return true;. more info on 1point3acres.com

回复 支持 反对

使用道具 举报

 楼主| magicalcan 发表于 2015-4-22 12:35:48 | 显示全部楼层
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.....考到这也是给跪了
回复 支持 反对

使用道具 举报

 楼主| magicalcan 发表于 2015-4-22 12:37:40 | 显示全部楼层
yuxrose 发表于 2015-4-22 10:10
我觉得第一题唯一的问题就是有个bug似乎,如果target是0的情况下, 这两行肯定会return true的,
set.add( ...
. visit 1point3acres.com for more.
有道理,这题有个条件是list里是正整数。所以最开始价格条件target小于等于0直接false就行了。不过面试官也没看出来这个
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-22 12:50:16 | 显示全部楼层
magicalcan 发表于 2015-4-22 12:35
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷LinkedList也是list interface里的。它的get(i)是n。但其实用iterator的方式就没事,用index i就不行了 ...

我觉得知识点考的太细了。。。有点挑刺的感觉。。。
祝福lz,这次肯定攒了不少人品。。。。
回复 支持 反对

使用道具 举报

liushen 发表于 2015-4-22 12:54:41 | 显示全部楼层
。。。。条件里面有list里面都是正整数啊。。。这个经典的min window题为啥没有准备好。。。
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2015-4-22 13:35:17 | 显示全部楼层
http://www.geeksforgeeks.org/find-subarray-with-given-sum/

楼主挂的原因我觉得应该是没有给出面试官想要的解法
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-22 13:57:29 | 显示全部楼层
zq13667243992 发表于 2015-4-22 13:35
http://www.geeksforgeeks.org/find-subarray-with-given-sum/

. From 1point 3acres bbs楼主挂的原因我觉得应该是没有给出面试官 ...
. 鍥磋鎴戜滑@1point 3 acres
你是说那个two pointer一起移动的解法吗?但关键是面试官并没有要求lz优化啊,他如果问,有没有in place的做法,lz也许也准备了这个solution啊,可是他一直纠结时间复杂度怎么优化,而不是空间复杂度,然后又挂lz,还是很可惜吧。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-4-22 21:19:18 | 显示全部楼层
fb最近还在面全职?LZ是experienced的engineer么?
回复 支持 反对

使用道具 举报

lyle100 发表于 2015-4-22 23:38:10 | 显示全部楼层
yuxrose 发表于 2015-4-22 13:57
你是说那个two pointer一起移动的解法吗?但关键是面试官并没有要求lz优化啊,他如果问,有没有in place ...

亲,那个不仅空间优化了,时间也从n*n优化到了n呀,你当时就应该果断抛出这个解法的。我觉得面试官没问你让你优化应该是他觉得你不知道更好的solution了
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-23 01:33:13 | 显示全部楼层
lyle100 发表于 2015-4-22 23:38
亲,那个不仅空间优化了,时间也从n*n优化到了n呀,你当时就应该果断抛出这个解法的。我觉得面试官没问你 ...

lz的solution时间也是n啊。
回复 支持 反对

使用道具 举报

lyle100 发表于 2015-4-23 02:33:38 | 显示全部楼层
yuxrose 发表于 2015-4-23 01:33
lz的solution时间也是n啊。

lz你的那个不是会在操作list的时候变成n*n么
回复 支持 反对

使用道具 举报

 楼主| magicalcan 发表于 2015-4-23 02:54:57 | 显示全部楼层
北航小涵 发表于 2015-4-22 21:19
fb最近还在面全职?LZ是experienced的engineer么?

毕业后一年多经验
回复 支持 反对

使用道具 举报

 楼主| magicalcan 发表于 2015-4-23 03:02:10 | 显示全部楼层
lyle100 发表于 2015-4-23 02:33. Waral 鍗氬鏈夋洿澶氭枃绔,
lz你的那个不是会在操作list的时候变成n*n么

是这样,题目里只说是list,没说是arraylist还是linkedlist,如果是array我写的就没事,但万一传过来的是linkedlist再get(i)就是n了。
另外set.add和arraylist.add面试官说不总是constant的,平时我总是默认了,因为平均是(1)
回复 支持 反对

使用道具 举报

 楼主| magicalcan 发表于 2015-4-23 03:06:05 | 显示全部楼层
lyle100 发表于 2015-4-22 23:38
亲,那个不仅空间优化了,时间也从n*n优化到了n呀,你当时就应该果断抛出这个解法的。我觉得面试官没问你 ...

恩,当时不知道为啥第一反应就是hashset,然后就写了。增减window的这个解法有点像minimum window substring的变异,当时没想到呢,可能还是做题感觉不到位
回复 支持 反对

使用道具 举报

lyle100 发表于 2015-4-23 04:51:25 | 显示全部楼层
magicalcan 发表于 2015-4-23 03:06
恩,当时不知道为啥第一反应就是hashset,然后就写了。增减window的这个解法有点像minimum window substr ...

patpat, 楼主加油!下次就有经验了!offer一定会来哒!
回复 支持 反对

使用道具 举报

emersonxsu 发表于 2015-4-27 10:28:47 | 显示全部楼层
第一题花了将近30分钟么? 感觉时间有些长了,然后没注意细节用了比较烂的linkedlist, 而且自己没主动说worst case可能会比较差, 也许就是这点觉得楼主不够好,然后第二题竟然不先说用的算法叫tree level traversal 或者BFS, 等到代码写完了,面试官主动问才回答,我觉得沟通上应该也有问题.
做题目不都是先理解题目,然后讲算法,面试官认可了再开始coding么,
回复 支持 反对

使用道具 举报

 楼主| magicalcan 发表于 2015-4-27 15:05:26 | 显示全部楼层
emersonxsu 发表于 2015-4-27 10:28
第一题花了将近30分钟么? 感觉时间有些长了,然后没注意细节用了比较烂的linkedlist, 而且自己没主动说worst ...

第一题code连想再写就10分钟左右吧,然后follow up大概3分钟。因为开始的时候聊了一阵behavior。最后他说还要留5分钟提问,所以他当时说第二题就10分钟了。时间应该不是大问题
交流确实下回应该加强。我老是看见那种简单题就想马上给写出来,哈哈
回复 支持 反对

使用道具 举报

jianixie 发表于 2015-4-30 05:12:58 | 显示全部楼层
hr下午就通知了?那么快?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 09:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表