一亩三分地论坛

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

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

fb 电面 求onsite

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

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

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

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

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

上来自我介绍,一句都没听清 然后让我自我介绍

花了10分钟吧

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

2.followup
要求island unique shape,不考虑旋转,答纪录一下bfs的路径,比如用字符串表示,然后用hashset判下重,然后code改出来. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
又问好像字符串的处理可能不是O(1),我说那可以用4进制数表示路径. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

最后5分钟 随便聊聊 小哥还黑了别家一下。。 说fb特别有impact。。不像XX

感觉写码什么思路还是很清楚的,就是真的听不清。。。 求onsite!!



补充内容 (2016-10-11 11:59):
刚收到onsite了~~

评分

1

查看全部评分

wopani007 发表于 2016-10-12 14:49:50 | 显示全部楼层
我觉得bfs没办法啊
举个例子
aaa
a  a
a  

aaa. Waral 鍗氬鏈夋洿澶氭枃绔,
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步。. from: 1point3acres.com/bbs

如果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
楼主能详细讲下follow up怎么做吗?感觉不简单呀
. more info on 1point3acres.com
就是纪录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
能说下什么意思吗?没太懂四进制怎么体现?

就是用四进制来记录路径啊
回复 支持 反对

使用道具 举报

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
楼主答的不错啊,而且换头像了。。
. From 1point 3acres bbs
额 没有换头像啊,,,您没认错人不。。
回复 支持 反对

使用道具 举报

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 ...
. 鍥磋鎴戜滑@1point 3 acres
面试官的意思是 c++的string的连接可能在底层不是O(1)的
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
四进制的话我只是提了个想法, 我觉得实际做的话可以key仍然用string,但是在计算path的时候用数字,如果考虑溢出的话可以分段来算,比如算到16位就先保存一下这样,最后把所有数字连起来。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
昨天下午电面,晚上收到onsite,因为手上有其他offer所以催了一下
回复 支持 反对

使用道具 举报

 楼主| chaozc 发表于 2016-10-12 00:52:02 | 显示全部楼层
minggr 发表于 2016-10-11 13:46. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
看看我的理解对不对:. Waral 鍗氬鏈夋洿澶氭枃绔,
四进制意思是用0,1,2,3表示上下左右四个方向,也就是用2 bits来记录每次走的方向 ...

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 08:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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