一亩三分地论坛

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

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

google面经 刚面完 感觉挂定了 求RP!

[复制链接] |试试Instant~ |关注本帖
Jessie33 发表于 2014-12-3 08:56:10 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Other

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

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

x
题目是这样的 实现一个class LicensePlateAnagramFinder, class的constructor接受一个字典 建立索引,然后实现一个方法,快速找到car plate里面的字母的anagram,如果没有就找最接近的那个。
. Waral 鍗氬鏈夋洿澶氭枃绔,
例子:车牌号例子:车牌号A6765C,首先找到字母A和C,然后和字典里面接近的词可以是ACE,ACT。。。 只要返回任意一个就行 ACCOUNT虽然含AC 但不是最短 CAT也可以 顺序不重要 字典的接口支持get查询和iterator

电面 面试官是老美 一开始口头问了一些很简单都答出来了...结果就说要给出个难的....没答出来,有大神知道的么... 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

3

查看全部评分

北美农民 发表于 2014-12-4 01:02:50 | 显示全部楼层
都anagram了,和trie有毛关系........还不如赤裸裸暴力呢
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2014-12-3 09:16:54 | 显示全部楼层
你说最接近的那个是什么意思
是A和C之间间隔的数字的个数接近, 还是什么
回复 支持 反对

使用道具 举报

houqingniao 发表于 2014-12-3 10:03:36 | 显示全部楼层
edit distance吧
回复 支持 反对

使用道具 举报

zude 发表于 2014-12-3 10:10:43 | 显示全部楼层
手工实现TRIE, 基本数据结构之一
回复 支持 反对

使用道具 举报

senarukana 发表于 2014-12-3 10:18:25 | 显示全部楼层
一开始把word建个trie之后。
然后对于每个query,生成它所有oneEditApart的词语。
然后把这个集合中每个词依次去trie上搜。
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-12-3 10:24:03 | 显示全部楼层
G家有够喜欢问trie
回复 支持 反对

使用道具 举报

neusharon 发表于 2014-12-3 10:43:38 | 显示全部楼层
senarukana 发表于 2014-12-3 10:18
一开始把word建个trie之后。
然后对于每个query,生成它所有oneEditApart的词语。
然后把这个集合中每个 ...

我怎么感觉这样反了,而且慢。。
直接对字典里的所有词做个trie, 然后对于plate里字母的所有anagram进行查询,预处理做的多一些但是查询快吧,求拍
回复 支持 反对

使用道具 举报

 楼主| Jessie33 发表于 2014-12-3 10:49:49 | 显示全部楼层
trie我还没看到....我去shi了。。。
回复 支持 反对

使用道具 举报

senarukana 发表于 2014-12-3 11:35:45 | 显示全部楼层
neusharon 发表于 2014-12-3 10:43
我怎么感觉这样反了,而且慢。。
直接对字典里的所有词做个trie, 然后对于plate里字母的所有anagram进 ...

取决于空间和时间的均衡,都可行。
回复 支持 反对

使用道具 举报

王可雪 发表于 2014-12-3 12:08:31 | 显示全部楼层
也許用re自動機可能更好。
回复 支持 反对

使用道具 举报

suonan 发表于 2014-12-3 12:16:21 | 显示全部楼层
王可雪 发表于 2014-12-3 12:08
也許用re自動機可能更好。

大牛展开讲讲?
回复 支持 反对

使用道具 举报

baojialiang 发表于 2014-12-3 12:38:22 | 显示全部楼层
neusharon 发表于 2014-12-3 10:43
我怎么感觉这样反了,而且慢。。
直接对字典里的所有词做个trie, 然后对于plate里字母的所有anagram进 ...

然后对于plate里字母的所有anagram进行查询, 这里指的是存一个hashtable, 然后对这个trie进行dfs,扫到这个hashtable没有字母需要匹配了,就回朔,是这样吗?
回复 支持 反对

使用道具 举报

neusharon 发表于 2014-12-4 00:59:01 | 显示全部楼层
baojialiang 发表于 2014-12-3 12:38
然后对于plate里字母的所有anagram进行查询, 这里指的是存一个hashtable, 然后对这个trie进行dfs,扫到 ...

dfs或bfs都可以吧,就是对树的遍历。感觉bfs会好一些。。
回复 支持 反对

使用道具 举报

yiyizhang809 发表于 2014-12-15 13:37:25 | 显示全部楼层
我和你面的同一个题
回复 支持 反对

使用道具 举报

漂洋过海 发表于 2014-12-16 01:06:43 | 显示全部楼层
还要看你的分析过程,不一定非要答上来的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 14:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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