推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6472|回复: 34
收起左侧

fb 电面 求onsite

[复制链接] |试试Instant~ |关注本帖
chaozc 发表于 2016-10-11 03:04:56 | 显示全部楼层 |阅读模式

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

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

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

x
欧洲小哥 声音是富有磁性的烟嗓 全程听不清 各种猜

上来自我介绍,一句都没听清 然后让我自我介绍
. from: 1point3acres.com/bbs
花了10分钟吧

1. num of island
很快写完bfs 有个别小bug经提醒改出来了 然后问问复杂度 O(nm) 此时剩23min

2.followup
要求island unique shape,不考虑旋转,答纪录一下bfs的路径,比如用字符串表示,然后用hashset判下重,然后code改出来
又问好像字符串的处理可能不是O(1),我说那可以用4进制数表示路径. 1point3acres.com/bbs

最后5分钟 随便聊聊 小哥还黑了别家一下。。 说fb特别有impact。。不像XX
. 鍥磋鎴戜滑@1point 3 acres
感觉写码什么思路还是很清楚的,就是真的听不清。。。 求onsite!!



补充内容 (2016-10-11 11:59):. 1point 3acres 璁哄潧
刚收到onsite了~~

评分

1

查看全部评分

wopani007 发表于 2016-10-12 14:49:50 | 显示全部楼层
我觉得bfs没办法啊
-google 1point3acres举个例子. 鍥磋鎴戜滑@1point 3 acres
aaa 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
a  a
a  

. 1point 3acres 璁哄潧aaa
a  a
    a

如果bfs是先右边再下边的话,这个结果难道不是一样的吗都是右右下下下
回复 支持 3 反对 0

使用道具 举报

minggr 发表于 2016-10-11 13:46:24 | 显示全部楼层
tanpf5 发表于 2016-10-11 10:47
四进制这个想法不错啊

看看我的理解对不对:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
四进制意思是用0,1,2,3表示上下左右四个方向,也就是用2 bits来记录每次走的方向。
对一个32bit的unsigned int, 最多只能记录16步。

如果island的点超过16个,那就overflow了,
比如,可能把由18个点组成的island和由2个点组成的island判断成是一样的
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-10-11 03:38:06 | 显示全部楼层
你的意思是如果两个islands的BFS路径相同,那么它们的形状也相同?
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-11 03:46:57 | 显示全部楼层
楼主能详细讲下follow up怎么做吗?感觉不简单呀
回复 支持 反对

使用道具 举报

nplay 发表于 2016-10-11 03:57:10 | 显示全部楼层

楼主能详细讲下follow up怎么做吗?怎么判断shape?多谢
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2016-10-11 07:52:42 | 显示全部楼层
wtcupup 发表于 2016-10-11 03:38
你的意思是如果两个islands的BFS路径相同,那么它们的形状也相同?

对就是bfs路径相同 形状也相同啊
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2016-10-11 07:53:35 | 显示全部楼层
iPhD 发表于 2016-10-11 03:46. From 1point 3acres bbs
楼主能详细讲下follow up怎么做吗?感觉不简单呀

就是纪录bfs的路径 两个island得到的路径相同, 则shape一样
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2016-10-11 07:54:29 | 显示全部楼层
nplay 发表于 2016-10-11 03:57
楼主能详细讲下follow up怎么做吗?怎么判断shape?多谢

就是纪录bfs的路径 两个island得到的路径相同, 则shape一样
回复 支持 反对

使用道具 举报

celtspirit 发表于 2016-10-11 09:56:51 | 显示全部楼层
请问路径相同是如何记录的啊,坐标一定会变得,所以是以第一个visit得点为起始,记录x,y的增减么?
回复 支持 反对

使用道具 举报

tanpf5 发表于 2016-10-11 10:47:12 | 显示全部楼层
四进制这个想法不错啊
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-11 11:12:14 | 显示全部楼层
tanpf5 发表于 2016-10-11 10:47
四进制这个想法不错啊

能说下什么意思吗?没太懂四进制怎么体现?
回复 支持 反对

使用道具 举报

aifer 发表于 2016-10-11 11:43:27 | 显示全部楼层
我怎么觉得DFS的unique shape也可以啊,楼主请讲一下为何不行?
回复 支持 反对

使用道具 举报

tanpf5 发表于 2016-10-11 11:53:13 | 显示全部楼层
iPhD 发表于 2016-10-11 11:12
能说下什么意思吗?没太懂四进制怎么体现?
. From 1point 3acres bbs
就是用四进制来记录路径啊
回复 支持 反对

使用道具 举报

marthew777 发表于 2016-10-11 11:56:29 | 显示全部楼层
楼主答的不错啊,而且换头像了。。
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2016-10-11 11:58:29 | 显示全部楼层
celtspirit 发表于 2016-10-11 09:56
请问路径相同是如何记录的啊,坐标一定会变得,所以是以第一个visit得点为起始,记录x,y的增减么?

纪录每一步是向哪个方向走的
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2016-10-11 11:59:19 | 显示全部楼层
marthew777 发表于 2016-10-11 11:56
楼主答的不错啊,而且换头像了。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
额 没有换头像啊,,,您没认错人不。。
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-10-11 14:34:27 | 显示全部楼层
chaozc 发表于 2016-10-11 11:58
纪录每一步是向哪个方向走的

想请教一下楼主是怎样用一个4进制数纪录走过的path的?感激不尽
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-12 00:04:05 | 显示全部楼层
谢谢分享~ 不过我有一个疑问 如果上下左右四个方向各用一个char来表示 组成的string就是路径 放入hashtable比较 这样为何处理可能不是O(1)?  考虑collison?.. 但是这应该也不是算法考虑的复杂度嘛~~ 如果用四进制数的话  需不需要考虑溢出呢?~  还有一个问题哦~ 请问你什么时候电面的呢?~ 到收到onsite等了多久?~ 感谢你!!
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2016-10-12 00:51:21 | 显示全部楼层
何打发123 发表于 2016-10-12 00:04
谢谢分享~ 不过我有一个疑问 如果上下左右四个方向各用一个char来表示 组成的string就是路径 放入hashtable ...

面试官的意思是 c++的string的连接可能在底层不是O(1)的

四进制的话我只是提了个想法, 我觉得实际做的话可以key仍然用string,但是在计算path的时候用数字,如果考虑溢出的话可以分段来算,比如算到16位就先保存一下这样,最后把所有数字连起来。. 1point3acres.com/bbs

昨天下午电面,晚上收到onsite,因为手上有其他offer所以催了一下
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2016-10-12 00:52:02 | 显示全部楼层
minggr 发表于 2016-10-11 13:46
看看我的理解对不对:
四进制意思是用0,1,2,3表示上下左右四个方向,也就是用2 bits来记录每次走的方向 ...

对的
麻烦看19楼的回复~
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-22 07:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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