没结婚也能买房啊!大波士顿地区买房小tips

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 3604|回复: 26
收起左侧

FB电面

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

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

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

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

x
刚刚结束的FB电面~
事实证明女人的第六感太强大了,果然跟Google考了同一题~话说这两家真的很喜欢dfs和bfs的问题
count number of island的变形~
给了一个Bitmap class,然后找connected component
需要记下每一个component size,最后return median
.鏈枃鍘熷垱鑷1point3acres璁哄潧
上来直接就是dfs了~
找到每个connected component的大小,然后sort,返回median
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
follow up问如果map很大怎么办~
dfs会导致stack上面有O(n)的function call
问能不能iteratively解决~
一下子没想出iterative怎么写~
直接改成了bfs和queue~
也可以解决stackoverflow的问题~

深入讨论了一下time complexity~
求好运~希望能够有next step~~

. from: 1point3acres.com/bbs

补充内容 (2015-8-29 06:22):. 1point3acres.com/bbs
等了一周终于等到了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!
. 鍥磋鎴戜滑@1point 3 acres
哈~谢谢,谢谢!!**还在努力中
回复 支持 反对

使用道具 举报

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);
        helper(map, visited, i + 1, j);-google 1point3acres
        helper(map, visited, i, j - 1);
        helper(map, visited, i, j + 1);
    }-google 1point3acres
}

public void helper(Bitmap map, boolean[][] visited, int i, int j) {-google 1point3acres
    if (i < 0 || i >= map.height() || j < 0 || j >= map.width() || !map.get(i, j) || visited[j]) {
        return;
    }
    count++;
    visited[j] = true;
    queue.add(i * map.width() + j); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}. Waral 鍗氬鏈夋洿澶氭枃绔,
这样不存在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):

是的~
我两种都写了~.鏈枃鍘熷垱鑷1point3acres璁哄潧
感觉就类似leetcode上面的surrounding region
如果用dfs会导致stackoverflow. Waral 鍗氬鏈夋洿澶氭枃绔,
非要用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.1point3acres缃
请问楼主投的是 new grads 吗?

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-4-22 03:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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