一亩三分地论坛

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

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

Snapchat 电面 11-30

[复制链接] |试试Instant~ |关注本帖
he2004365 发表于 2015-12-4 08:28:46 | 显示全部楼层 |阅读模式

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

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

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

x
分享个楼主惨痛的snapchat电面。OA就不说了,简单的数独问题, 做完当天下午约电面,电面是国人大叔。在面之前也是跟其他人一样,把地里的题都刷了一遍,什么bigInteger, DP, Zigzag print等等。 结果电面不是这些啊,并且楼主成功被自己蠢哭,第一题就没搞定。干货: 一个dictionary里面存String单词,有millions这么多,给一个char array, 让返回所有的单词,这些单词的所有字母必须在char array里面。比如:char array = {a,c,a,r,t}, dictionary={"a","aa","cat","cats","aaa","cc"}
那么你返回的list里面包含的单词应该是:a, aa, cat这类的。其实我并不知道为啥aa也算单词, 不包含的像cats, aaa, cc这样的。

思路:刚开始我说:将char array处理成map<character, Integer>这样形式,然后去扫dictionary里面单词,如果包含在map里面就加入list,不包含就不加。大叔说,可以,但是复杂度太高,有没有优化,想两三分钟,估计看我没动静,问我看看需不需要用什么data structure, 突然想到用trie, 就说了。 果然是用trie, 然后又让我说了下用trie怎么去遍历。
. From 1point 3acres bbs
悲剧就此时发生,楼主对trie里面的成员变量理解的不够深刻。想DFS去遍历,但是不会写呜呜呜呜呜~哎~都别问我为什么,因为不知道怎么写循环,而且那会没想清楚就开始写代码,写到一半发现,不会用trie里的成员变量呢,就慌了。一个小时硬是没做出来,我也是醉醉的。面试结束,自己静下心来,20分钟竟然写出来了,我擦擦擦擦擦擦。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 1point 3acres 璁哄潧
PS 老老实实练DFS,BFS去。如果给我面试的国人大叔也逛论坛,一定看到我这篇帖子,会被当时的我蠢哭了。move on了,以后不能这么蠢了~~~~
知道你们肯定要代码,已经写好了,在附件里面。递归的地方可以再优化,自己看看吧。

SnapChat.java.zip

853 Bytes, 阅读权限: 1, 下载次数: 99, 下载积分: 大米 -1 升

评分

3

查看全部评分

本帖被以下淘专辑推荐:

cszeus 发表于 2016-1-21 15:58:33 | 显示全部楼层
我有个想法,先统计char array里字母的频率,一个hashtable,26个key(只考虑小写的话),space O(1).对于每个单词,统计字母频率,又是一个hashtable,space O(1).之后只要保证单词的词频小于char array的词频就好了,最多比26次,a-z。建trie的话,空间多不说,建trie的过程反正要把每个单词每个字母遍历一遍,跟我统计字母频率的复杂度一样
回复 支持 2 反对 0

使用道具 举报

wangx3 发表于 2015-12-4 14:15:18 | 显示全部楼层
没看出来这个用Trie有什么好处啊?是把dict内的单词建Trie么,这不是也要遍历一边所有的单词?跟直接判断是不是所有字母都在char array里面有什么区别?还浪费space。 还不如说要找出char array所有的排列,然后在建好的Trie里找有没有合法的word,这样还说得通为什么要建Trie。虽然也没有提高效率,都是要把所有的单词过一遍。因为不过一遍所有的单词,怎么能确认每个单词是否合法?
回复 支持 1 反对 0

使用道具 举报

LYJALEX__ 发表于 2015-12-4 12:18:40 | 显示全部楼层
Trie 是遍历吗? 我感觉是搜索啊。
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-12-4 22:09:02 | 显示全部楼层
LYJALEX__ 发表于 2015-12-4 12:18
Trie 是遍历吗? 我感觉是搜索啊。

没啥区别把?因为要找到所有的单词,只能一个节点一个节点的遍历吧~
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-12-4 22:13:17 | 显示全部楼层
wangx3 发表于 2015-12-4 14:15
没看出来这个用Trie有什么好处啊?是把dict内的单词建Trie么,这不是也要遍历一边所有的单词?跟直接判断是 ...

对于时间,你想下对于单词cat和cats,如果你想直接在字典里找到这两个,cat的部分其实你是遍历了两次,但是在trie中cat只遍历一次。对于空间,也是一样的,这两单词需要七个byte来存,但是放trie里,只需要四个byte就好了。
对于millions级别的,这个优化已经很好了。
回复 支持 反对

使用道具 举报

sooorrr 发表于 2015-12-5 05:57:22 | 显示全部楼层
he2004365 发表于 2015-12-4 22:13
对于时间,你想下对于单词cat和cats,如果你想直接在字典里找到这两个,cat的部分其实你是遍历了两次,但 ...
. visit 1point3acres.com for more.
首先你建Trie的时候不久遍历一边了所有的单词了吗?你遍历一边建一个hash table有什么区别,我能想到的优化就是可以根据每个node的状态,提前结束判断?但是这增加了代码的复杂性,而且优化的也有想得很。
然后关于节省空间,建议lz看看这个帖子,对于Trie和hashtable的区别会有更好的理解。
http://stackoverflow.com/questio ... -a-trie-prefix-tree

感觉这个面试官先有了解法再来设计题目,而且设计的也不怎么高明。
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-12-5 07:07:13 | 显示全部楼层
sooorrr 发表于 2015-12-5 05:57
首先你建Trie的时候不久遍历一边了所有的单词了吗?你遍历一边建一个hash table有什么区别,我能想到的优 ...

我有点不太明白,你建hashtable有什么用?要是table里还是存完整单词的话,那跟直接遍历dictionary有什么区别?至于这道题是不是面试官自己设计的,还真不知道,反正他是把我往trie上去引的。不过确实用trie需要用到DFS之类的递归做法, 增加的程序复杂度。


回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-12-5 07:14:38 | 显示全部楼层
sooorrr 发表于 2015-12-5 05:57. visit 1point3acres.com for more.
首先你建Trie的时候不久遍历一边了所有的单词了吗?你遍历一边建一个hash table有什么区别,我能想到的优 ...

你给的链接我也看了,底下有人也提到了,hashtable不一定空间上就优于trie,还是要看题目的需要。要是有面试官问我的这样的问题的话,我感觉我会回答,看输入的dictionary是不是变化的,要是变化的可能用trie比较合适,因为hashtable还涉及到一个rehash的事情。
回复 支持 反对

使用道具 举报

sooorrr 发表于 2015-12-5 10:10:29 | 显示全部楼层
he2004365 发表于 2015-12-5 07:14
你给的链接我也看了,底下有人也提到了,hashtable不一定空间上就优于trie,还是要看题目的需要。要是有 ...

我是提醒你一下不要天然的认为Trie空间复杂度很好,Tire很多overhead的data导致他的空间耗费很高。至于提到hashtable,我的问题,是我把自己绕进去了,这根本不要什么hashtable啊,之间遍历一边,找出所有的解不就行了?你最初的方法不一定就比面试官的要求的方法差, 我觉得面试官就是非要套一个看上去高大上的方法。这种面试很无奈。

补充内容 (2015-12-5 10:11):
之间->直接
回复 支持 反对

使用道具 举报

sooorrr 发表于 2015-12-5 10:16:41 | 显示全部楼层
he2004365 发表于 2015-12-5 07:14
你给的链接我也看了,底下有人也提到了,hashtable不一定空间上就优于trie,还是要看题目的需要。要是有 ...

我看你的code要把所有单词插入到Trie中,然后再遍历Trie的所有点,你不觉得后面一步有点多余?还浪费一个Trie的空间?
回复 支持 反对

使用道具 举报

sooorrr 发表于 2015-12-5 10:17:47 | 显示全部楼层
sooorrr 发表于 2015-12-5 10:16
我看你的code要把所有单词插入到Trie中,然后再遍历Trie的所有点,你不觉得后面一步有点多余?还浪费一个 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
反正我是一点没看出Trie相对直接遍历,比较的优势来。。
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-12-5 12:34:17 | 显示全部楼层
sooorrr 发表于 2015-12-5 10:17.鏈枃鍘熷垱鑷1point3acres璁哄潧
反正我是一点没看出Trie相对直接遍历,比较的优势来。。

确实,面试官也没跟我讨论过为什么这道题trie用起来会比直接遍历好。自己理解的就是,trie树我只需要建立一遍就好,如果写出来的这个函数,要被其他工程师多次调用。我可以直接trie上遍历,这样能比每次都遍历一遍dictionary要好吧。目前水平,只能理解到这里了。
回复 支持 反对

使用道具 举报

sooorrr 发表于 2015-12-5 13:19:45 | 显示全部楼层
he2004365 发表于 2015-12-5 12:34
确实,面试官也没跟我讨论过为什么这道题trie用起来会比直接遍历好。自己理解的就是,trie树我只需要建立 ...

多次调用倒是有好处,不过真是多次调用需要预处理的话,那就不是用原始字符串建Trie,而是应该用每个单词的signature建Trie,这个signature就是每个单词按字母出现的次数产生的hashkey,比如apple->aelpp,这样每次查询的速度会提高的更多,并且节省的空间可能更大。
反正这题感觉很怪,面试官的问题吧。
回复 支持 反对

使用道具 举报

sooorrr 发表于 2015-12-5 13:20:32 | 显示全部楼层
sooorrr 发表于 2015-12-5 13:19
多次调用倒是有好处,不过真是多次调用需要预处理的话,那就不是用原始字符串建Trie,而是应该用每个单词 ...

速度会提高的更多 -> 速度可能会提高的更多
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-12-5 13:33:25 | 显示全部楼层
LZ是内推的吗还是网投?
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-12-5 23:37:38 | 显示全部楼层
eko910817 发表于 2015-12-5 13:33.鏈枃鍘熷垱鑷1point3acres璁哄潧
LZ是内推的吗还是网投?

linkedin上找的内推~
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-12-6 05:34:07 | 显示全部楼层
he2004365 发表于 2015-12-5 07:37.鐣欏璁哄潧-涓浜-涓夊垎鍦
linkedin上找的内推~

找HR吗还是找内推?
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-1-21 14:04:33 | 显示全部楼层
he2004365 发表于 2015-12-5 12:34
确实,面试官也没跟我讨论过为什么这道题trie用起来会比直接遍历好。自己理解的就是,trie树我只需要建立 ...
. from: 1point3acres.com/bbs
假设字典长度n,char array长度m,字典中每个单词长度为L,那么用楼楼之前的方法,时间复杂度是O(nL),空间复杂度O(m),但是如果用trie,首选建立trie会耗费时间O(nL),然后遍历一边会耗时O(v),这里v是trie总节点数,v非常大,总的空间复杂度是O(v),所以肯定是楼楼先前的方法好的多。
. 1point3acres.com/bbs
correct me if I‘m wrong
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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