一亩三分地论坛

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

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

FB电面

[复制链接] |试试Instant~ |关注本帖
laurie洁 发表于 2015-8-21 03:43:56 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚结束的FB电面~. from: 1point3acres.com/bbs
事实证明女人的第六感太强大了,果然跟Google考了同一题~话说这两家真的很喜欢dfs和bfs的问题
count number of island的变形~
给了一个Bitmap class,然后找connected component
需要记下每一个component size,最后return median

上来直接就是dfs了~
找到每个connected component的大小,然后sort,返回median

follow up问如果map很大怎么办~
dfs会导致stack上面有O(n)的function call
问能不能iteratively解决~
一下子没想出iterative怎么写~
直接改成了bfs和queue~
也可以解决stackoverflow的问题~

深入讨论了一下time complexity~
求好运~希望能够有next step~~
. From 1point 3acres bbs


补充内容 (2015-8-29 06:22):
等了一周终于等到了onsite通知~好开心~~

评分

5

查看全部评分

 楼主| laurie洁 发表于 2015-8-25 11:56:43 | 显示全部楼层
jiebour 发表于 2015-8-25 10:20
楼主,不是说FB不怎么招人了嘛。。。。

不知道呀~~还在忐忑的等待消息中~~
回复 支持 1 反对 0

使用道具 举报

sishuxuan 发表于 2015-8-21 04:10:10 | 显示全部楼层
LZ妹纸来发帖啦! 祝好运怒拿offer!
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-8-21 05:31:21 | 显示全部楼层
sishuxuan 发表于 2015-8-21 04:10.鐣欏璁哄潧-涓浜-涓夊垎鍦
LZ妹纸来发帖啦! 祝好运怒拿offer!
. from: 1point3acres.com/bbs
哈~谢谢,谢谢!!**还在努力中
回复 支持 反对

使用道具 举报

winter_lv 发表于 2015-8-21 05:58:30 | 显示全部楼层
祝好运!!  顺便问下BFS如何解决DFS的over flow?按说BFS要的stack比DFS更多不是?
回复 支持 反对

使用道具 举报

winter_lv 发表于 2015-8-21 05:59:55 | 显示全部楼层
因为queue存在堆空间吗?
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-8-21 06:04:54 | 显示全部楼层
laurie洁 发表于 2015-8-21 05:31
哈~谢谢,谢谢!!**还在努力中

请问一下,【1】 你提到的这个Bitmap class是不是本质上就还是0和1的二维matrix呢?【2】深入讨论了下time complexity, 楼主可以简单说说吗?主要是讨论啥?
回复 支持 反对

使用道具 举报

ccjobhunter2011 发表于 2015-8-21 06:11:59 | 显示全部楼层
楼主你bitmap 怎么遍历哇?他有给你接口吗?怎么遍历bitmap
比如
byte[0] = 第一row?
byte [1] = 第二row?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

或则是1D?
3= 0000 0011

你是用bit运算遍历的吗?
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2015-8-21 06:19:56 | 显示全部楼层
请lz能否把bitmap class说明一下
回复 支持 反对

使用道具 举报

w41q 发表于 2015-8-21 07:46:38 | 显示全部楼层
dfs用stack和2D visited数组就能解决吧?

补充内容 (2015-8-21 07:47):
感觉和用两个queue的bfs难度差不多。。
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-8-21 11:09:17 | 显示全部楼层
winter_lv 发表于 2015-8-21 05:58
祝好运!!  顺便问下BFS如何解决DFS的over flow?按说BFS要的stack比DFS更多不是?

啊,我的理解是bfs每次处理一个index的时候只有符合条件才会放入queue里面~
public void bfs(Bitmap map, boolean[][] visited, int i, int j) {
    helper(map, visited, i, j);
    while (!queue.isEmpty()) {
        int index = queue.poll();
        i = index / map.width();
        j = index % map.width();
        helper(map, visited, i - 1, j);. more info on 1point3acres.com
        helper(map, visited, i + 1, j);
        helper(map, visited, i, j - 1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        helper(map, visited, i, j + 1);
    }
}

public void helper(Bitmap map, boolean[][] visited, int i, int j) {
    if (i < 0 || i >= map.height() || j < 0 || j >= map.width() || !map.get(i, j) || visited[j]) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        return;
    }
    count++;
    visited[j] = true;
. 鍥磋鎴戜滑@1point 3 acres    queue.add(i * map.width() + j);
}
这样不存在stack上面有很多bfs call的情况~
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-8-21 11:10:55 | 显示全部楼层
水逼一枚 发表于 2015-8-21 06:04
请问一下,【1】 你提到的这个Bitmap class是不是本质上就还是0和1的二维matrix呢?【2】深入讨论了下tim ...

对的~其实就是一个boolean matrix,只不过他提供了接口去查每个index的值而已~
time complexity就是问了一下一般情况和最坏的情况下分别是怎样的~
发现其实主要是sort会占时间
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-8-21 11:11:34 | 显示全部楼层
ccjobhunter2011 发表于 2015-8-21 06:11
楼主你bitmap 怎么遍历哇?他有给你接口吗?怎么遍历bitmap. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
比如
byte[0] = 第一row?

bitmap是一个class
他给了getter function去查每个index的值
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-8-21 11:13:30 | 显示全部楼层
w41q 发表于 2015-8-21 07:46
dfs用stack和2D visited数组就能解决吧?

补充内容 (2015-8-21 07:47):

是的~. 鍥磋鎴戜滑@1point 3 acres
我两种都写了~
感觉就类似leetcode上面的surrounding region
如果用dfs会导致stackoverflow
非要用bfs和queue来保证stack上不会有太多function call
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-8-21 23:01:12 | 显示全部楼层
count number of island的变形~ 麻烦楼主详细说说呗?
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-8-22 01:34:47 | 显示全部楼层
hyliu0000 发表于 2015-8-21 23:01
count number of island的变形~ 麻烦楼主详细说说呗?

我后面给了解释呀
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-8-24 23:14:36 | 显示全部楼层
laurie洁 发表于 2015-8-22 01:34
我后面给了解释呀

sorry 理解错了   还以为考了两道题。。。
回复 支持 反对

使用道具 举报

chuxidemeng 发表于 2015-8-25 01:06:42 | 显示全部楼层
LZ能给个DFS的完整解法吗?
PS: LZ是内推多久HR联系安排面试的呀?~我也在大西雅图地区,希望能拿到这里的offer哇
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-25 01:07:27 | 显示全部楼层
有人会, iterative 吗
回复 支持 反对

使用道具 举报

jemi 发表于 2015-8-25 08:06:00 | 显示全部楼层
请问楼主投的是 new grads 吗?
回复 支持 反对

使用道具 举报

 楼主| laurie洁 发表于 2015-8-25 10:11:54 | 显示全部楼层
jemi 发表于 2015-8-25 08:06
请问楼主投的是 new grads 吗?

对的~~还没有消息~~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 23:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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