10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3712|回复: 17
收起左侧

Dropbox Intern 面经

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

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

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

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

x
刚结束的二面,上来不BB,直接做题。. from: 1point3acres.com/bbs

还是经典phone number combinations那题,面试官一开始就问我有没有做过这题。。。我当然没做过。。。(逃

先分析了一下,把combinations写了,面试官说不错,写了两个test cases, 然后写search。一开始给的条件是电话号码长度是7,直接分情况在dictionary里search就行了。

followup: 电话长度不为7, 想了一下,用DFS秒了, 其实就是word break. 然后分析各个函数的复杂度。
. visit 1point3acres.com for more.
followup: 优化search函数(非complexity级别)。我在函数开始添加了一个从后向前的搜索,避免了不必要的递归。面试官说不错,还有没有什么优化办法。

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

评分

4

查看全部评分

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然后字母组合那个吗
. from: 1point3acres.com/bbs
显示组合,这部分和leetcode一样。后面不一样。
回复 支持 反对

使用道具 举报

 楼主| yhfyhf 发表于 2016-2-18 01:49:13 | 显示全部楼层
carthus 发表于 2016-2-17 10:56-google 1point3acres
楼主可以描述一下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
请问楼主是内推还是网申的啊?

帖子里已经有注明,网申的。
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| yhfyhf 发表于 2016-2-18 02:17:02 | 显示全部楼层
mchzh 发表于 2016-2-17 13:08. 鍥磋鎴戜滑@1point 3 acres
这题也是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什么?

dictionary里就是一些字符串。。。phone number能组成一些combinations,然后在dictionary里找出combinations
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-3-19 03:23:11 | 显示全部楼层
yhfyhf 发表于 2016-2-18 06:27. 1point3acres.com/bbs
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就行
回复 支持 反对

使用道具 举报

frk 发表于 2017-1-5 03:33:34 | 显示全部楼层
请教一下楼主,
1. dictionary里面是不是从开始到follow up一直都是3位,4位,7位的词组呢
2. follow-up 的话 电话号码就不是7位了, match的话就是word break去dictionary里面找match的

谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-21 00:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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