一亩三分地论坛

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

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

AIRBNB skype 面经

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

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

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

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

x

题目: boogle game直接找到所以单词可能出现的位置,然后dfs
感觉这样的代码比较短。。45min勉强敲的出来。。
小哥竟然没开视频。。都懒得看我一眼。。

祝愿大家感恩节快乐,offer多多!
希望自己能够一切顺利起来

本帖被以下淘专辑推荐:

josephdesire 发表于 2016-11-25 05:17:04 | 显示全部楼层
要去onsite了? 加油加油~
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-26 05:13:05 | 显示全部楼层
请问是boggle game I 还是 II呀? 具体要求是啥
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-26 05:40:58 | 显示全部楼层
小A要当码农 发表于 2016-11-25 13:13
请问是boggle game I 还是 II呀? 具体要求是啥
. visit 1point3acres.com for more.
boggle game这都出来两个版本了啊?小A这么严谨讲讲要求都是什么呗?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-26 06:14:38 | 显示全部楼层
gy21 发表于 2016-11-26 05:40
boggle game这都出来两个版本了啊?小A这么严谨讲讲要求都是什么呗?

好像一个要求连续, 一个不要求呗。 不要求那个更难。。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-11-26 06:29:57 | 显示全部楼层
楼主能详细说下吗? 谢了
回复 支持 反对

使用道具 举报

 楼主| SiyaoZhu 发表于 2016-11-26 08:37:49 | 显示全部楼层
额 没有说过什么连续的事情啊。。.1point3acres缃
我记得 就是找board中找不能重复位置的最大单词数量。。找单词的时候还定义了一个曼哈顿距离。。就是用来表示不能斜着走的
题目一共就是这3句话。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
另外board里面的字母都是大写
回复 支持 反对

使用道具 举报

 楼主| SiyaoZhu 发表于 2016-11-26 08:38:26 | 显示全部楼层
小A要当码农 发表于 2016-11-26 06:14
好像一个要求连续, 一个不要求呗。 不要求那个更难。。

请问啥叫要求连续呀?什么是连续的呀?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-27 01:54:39 | 显示全部楼层
SiyaoZhu 发表于 2016-11-26 08:38
请问啥叫要求连续呀?什么是连续的呀?

就是找的单词需要首位相接么?
回复 支持 反对

使用道具 举报

ilovexiao77 发表于 2016-11-27 14:46:08 | 显示全部楼层
请问能不能给一下代码,我只会写word search ii, 字母可以重复用,但是如果不能重复用好像很难,求指点
回复 支持 反对

使用道具 举报

gy21 发表于 2016-12-2 02:37:57 | 显示全部楼层
lz这轮skype过了吗?
回复 支持 反对

使用道具 举报

goodluck888 发表于 2016-12-2 04:42:12 | 显示全部楼层
lz只有一轮skype面试吗?
回复 支持 反对

使用道具 举报

han4011 发表于 2016-12-8 01:05:36 | 显示全部楼层
SiyaoZhu 发表于 2016-11-26 08:37
额 没有说过什么连续的事情啊。。. 鍥磋鎴戜滑@1point 3 acres
我记得 就是找board中找不能重复位置的最大单词数量。。找单词的时候还 ...

楼主 能说下 boggle game的 思路吗
回复 支持 反对

使用道具 举报

 楼主| SiyaoZhu 发表于 2016-12-8 10:40:43 | 显示全部楼层
han4011 发表于 2016-12-8 01:05
楼主 能说下 boggle game的 思路吗
. visit 1point3acres.com for more.
我就是用了word break II 的代码 先找到了单词出现的所有位置 然后再来一个dfs来找到不重叠的最大情况

补充内容 (2016-12-8 10:41):
word search II。。错了。。
回复 支持 反对

使用道具 举报

XCQ 发表于 2016-12-8 17:17:16 | 显示全部楼层
SiyaoZhu 发表于 2016-12-8 10:40
我就是用了word break II 的代码 先找到了单词出现的所有位置 然后再来一个dfs来找到不重叠的最大情况

...

楼主你的"再来1个DFS”是地里那个dfs2()的解法吗 我在想能不能把每个word 都算出一个conflict count,一开始所有word都在result里 然后从count高的开始remove,直到所有word都没有conflict
是个greedy但感觉似乎是对的
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| SiyaoZhu 发表于 2016-12-9 01:51:23 | 显示全部楼层
XCQ 发表于 2016-12-8 17:17
楼主你的"再来1个DFS”是地里那个dfs2()的解法吗 我在想能不能把每个word 都算出一个conflict count,一 ...

不是啊。。我是最最暴力的。。找出所有单词的位置,用一个map表示 然后dfs这个map找出不重复的最大
回复 支持 反对

使用道具 举报

XCQ 发表于 2016-12-9 03:17:39 | 显示全部楼层
SiyaoZhu 发表于 2016-12-9 01:51
不是啊。。我是最最暴力的。。找出所有单词的位置,用一个map表示 然后dfs这个map找出不重复的最大

所以你的map就是word->list of letter indice,然后dfs用一个set of indice来判断重复?这个确实work 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

那你觉得我的方法会不会有什么问题
回复 支持 反对

使用道具 举报

XCQ 发表于 2016-12-9 04:06:18 | 显示全部楼层
SiyaoZhu 发表于 2016-12-9 01:51. Waral 鍗氬鏈夋洿澶氭枃绔,
不是啊。。我是最最暴力的。。找出所有单词的位置,用一个map表示 然后dfs这个map找出不重复的最大

用map要是单词重复出现会有问题吧
回复 支持 反对

使用道具 举报

 楼主| SiyaoZhu 发表于 2016-12-10 00:01:08 | 显示全部楼层
XCQ 发表于 2016-12-9 04:06
用map要是单词重复出现会有问题吧

最终结果可以有重复单词的 只要不overlap
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-23 23:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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