一亩三分地论坛

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

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

Dropbox Intern 面经

[复制链接] |试试Instant~ |关注本帖
yhfyhf 发表于 2016-1-20 03:23:17 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Dropbox - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚结束的二面,上来不BB,直接做题。
. from: 1point3acres.com/bbs
还是经典phone number combinations那题,面试官一开始就问我有没有做过这题。。。我当然没做过。。。(逃
. 鍥磋鎴戜滑@1point 3 acres
先分析了一下,把combinations写了,面试官说不错,写了两个test cases, 然后写search。一开始给的条件是电话号码长度是7,直接分情况在dictionary里search就行了。

followup: 电话长度不为7, 想了一下,用DFS秒了, 其实就是word break. 然后分析各个函数的复杂度。

followup: 优化search函数(非complexity级别)。我在函数开始添加了一个从后向前的搜索,避免了不必要的递归。面试官说不错,还有没有什么优化办法。

followup: 面试官:考虑一下号码长度很长,但不至于stack overflow的情况,比方说["AAAAAAAAAAAAAA", "BAAAAAAAAAAAAA"]。我:用Trie Tree? 解释了一下,顿时觉得自己傻了,trie的速度比dict慢多了啊。。他又没问dict太大怎么办。。。面试官:考虑一下cache。我:那用个dict把每个结果存起来。写了一下,面试官说不错。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
最后问了两三个问题,结束。
.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

3

查看全部评分

leixiang5 发表于 2016-1-20 10:49:50 | 显示全部楼层
onsite 了吧。恭喜
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-2-9 18:21:12 | 显示全部楼层
请问什么是phone combination啊?是leetcode那个phone number然后字母组合那个吗
回复 支持 反对

使用道具 举报

carthus 发表于 2016-2-17 23:56:25 | 显示全部楼层
楼主可以描述一下phone combinations这个题目吗?
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-2-18 01:49:00 | 显示全部楼层
ninacc 发表于 2016-2-9 05:21
请问什么是phone combination啊?是leetcode那个phone number然后字母组合那个吗

显示组合,这部分和leetcode一样。后面不一样。
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-2-18 01:49:13 | 显示全部楼层
carthus 发表于 2016-2-17 10:56
楼主可以描述一下phone combinations这个题目吗?

你可以搜一下面经,论坛里很多。
回复 支持 反对

使用道具 举报

3QZZY 发表于 2016-2-18 01:58:40 | 显示全部楼层
yhfyhf 发表于 2016-2-18 01:49 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你可以搜一下面经,论坛里很多。

请问楼主是内推还是网申的啊?
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-2-18 01:59:17 | 显示全部楼层
3QZZY 发表于 2016-2-17 12:58. 鍥磋鎴戜滑@1point 3 acres
请问楼主是内推还是网申的啊?
. 1point3acres.com/bbs
帖子里已经有注明,网申的。
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-2-18 02:08:29 | 显示全部楼层
这题也是leetcode上的?
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-2-18 02:17:02 | 显示全部楼层
mchzh 发表于 2016-2-17 13:08
这题也是leetcode上的?

不是。combinations那部分是leetcode上的。
回复 支持 反对

使用道具 举报

ankaiyue 发表于 2016-2-18 05:20:50 | 显示全部楼层
楼主好人,能把search部分的问题描述说得更明白些吗?dictionary里都是什么?让search什么?
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-2-18 06:27:13 | 显示全部楼层
ankaiyue 发表于 2016-2-17 16:20
楼主好人,能把search部分的问题描述说得更明白些吗?dictionary里都是什么?让search什么?
. more info on 1point3acres.com
dictionary里就是一些字符串。。。phone number能组成一些combinations,然后在dictionary里找出combinations
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-3-19 03:23:11 | 显示全部楼层
yhfyhf 发表于 2016-2-18 06:27
dictionary里就是一些字符串。。。phone number能组成一些combinations,然后在dictionary里找出combinat ...

lz请问你说的“一开始给的条件是电话号码长度是7,直接分情况在dictionary里search就行了”,是不是面试官规定了字典里单词的最小长度是3?另外长度不为7的话,得先找出所有可能的单词组合,然后对于每个组合再在dict里搜索?谢谢
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-3-19 09:26:43 | 显示全部楼层
gjxwin 发表于 2016-3-18 14:23
lz请问你说的“一开始给的条件是电话号码长度是7,直接分情况在dictionary里search就行了”,是不是面试 ...

completely right
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-3-19 09:38:51 | 显示全部楼层
.鐣欏璁哄潧-涓浜-涓夊垎鍦
另外求问lz最后一个followup cache一下是啥意思呢?没看懂,谢谢!
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-2 08:30:59 | 显示全部楼层
用TIRE当然不是说你已经凑好一个单词了,再去TRIE里搜索了,是带着TRIE NODE往下搜,遇到TRIE NODE CHILDREN里完全没有的,直接跳过,可以避免很多无意义的DFS,如果带着TRIE NODE往里搜,那么判断是不是单词也就O(1),因为就CHECK一下那个ISWORD的BOOLEAN就行
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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