一亩三分地论坛

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

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

2016/09/07 电面

[复制链接] |试试Instant~ |关注本帖
周珈羽 发表于 2016-9-9 05:59:08 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
2016 / 09 / 07 电面    Google Doc 打出来的题目

We look at cars license plates and try to find a word from the dictionary that includes all the letters from the license plate.
The shorter the word, the better.
The license plates start with two or three letters, then they are followed by 5 characters, from which at most 2 are letters, the rest are digits.

Your goal is to write code that will find the shortest words for 100 license plates. You are given a dictionary.

E.g. for the license plate “RT 123SO” the shortest word would be “SORT”, for “RC 10014” : “CAR”.

Follow up : 根据自己写的代码,问了问复杂度,然后优化

zyoppy008 发表于 2016-9-9 10:28:51 | 显示全部楼层
How about PP 1234A? P should repeat in the word or not ?
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 10:42:38 | 显示全部楼层
请问这题你怎么做的呢?多谢!
回复 支持 反对

使用道具 举报

 楼主| 周珈羽 发表于 2016-9-9 10:58:57 | 显示全部楼层
zyoppy008 发表于 2016-9-9 10:28
How about PP 1234A? P should repeat in the word or not ?

“PP  1234O”   返回 pop 重复字母,个数也要一样   
回复 支持 反对

使用道具 举报

 楼主| 周珈羽 发表于 2016-9-9 11:01:14 | 显示全部楼层
william_gong 发表于 2016-9-9 10:42. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
请问这题你怎么做的呢?多谢!

写了两个小函数,第一个提取原字符串中的字母 “RT 1234A”A --> “RTA”;
第二个check dictionary 里那些单词包含 "RTA",找到最短的返回
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 11:02:24 | 显示全部楼层
周珈羽 发表于 2016-9-9 11:01
写了两个小函数,第一个提取原字符串中的字母 “RT 1234A”A --> “RTA”;
第二个check dictionary 里 ...

第二个函数是怎么写的呢? sort 字典以后一个个比较吗? 还是用trie来做?多谢!
回复 支持 反对

使用道具 举报

 楼主| 周珈羽 发表于 2016-9-9 11:09:00 | 显示全部楼层
william_gong 发表于 2016-9-9 11:02. from: 1point3acres.com/bbs
第二个函数是怎么写的呢? sort 字典以后一个个比较吗? 还是用trie来做?多谢!

我开始写了个类似 Anagram,他还挺满意。
然后问我能不能提高效率,之后就没写代码了,就说了说提高效率的想法。
回复 支持 反对

使用道具 举报

shuiguo 发表于 2016-9-9 11:11:06 | 显示全部楼层
请问dictionary的size是多少?给的input是什么形式?需要自己建树么?.1point3acres缃

想了想感觉保证最短还挺难
回复 支持 反对

使用道具 举报

mren 发表于 2016-9-9 11:11:19 | 显示全部楼层
我觉得可以这样,建一个hash表,保存为[int, int]形式,将字典中的每一个单词映射成一个整数,即a-z分别对于整数的0-25位,具有相同映射的单词在hash表的同一个key下只保存其最短长度,然后再求出每一个车牌对应的字符串的整数映射,然后去和hash表的key做与操作,如果结果等于车牌的整数那就找到了结果
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-9-9 11:14):
哦,忘了考虑重复字符,抱歉.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-9-9 11:17):
不过改进一下应该可以,就是value保存单词,然后如果如果相与之后与车牌照相等就再一个个对比里面的单词
回复 支持 反对

使用道具 举报

shuiguo 发表于 2016-9-9 11:24:23 | 显示全部楼层
mren 发表于 2016-9-8 22:11
我觉得可以这样,建一个hash表,保存为形式,将字典中的每一个单词映射成一个整数,即a-z分别对于整数的0-2 ...

请问如何转化为int并且保证car和rac是同一个key?而且还可能车牌是cr,对应的词是car,这种情况怎么办?
回复 支持 反对

使用道具 举报

 楼主| 周珈羽 发表于 2016-9-9 11:26:59 | 显示全部楼层
mren 发表于 2016-9-9 11:11
我觉得可以这样,建一个hash表,保存为形式,将字典中的每一个单词映射成一个整数,即a-z分别对于整数的0-2 ...

我**一只,以前地里也没见过这题,当时就能想起来啥就是啥了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
贴出题来,有空的看见的就练练手,万一谁碰到一样的呢,就算幸运了~~

PS : 我好像说了个 Cache 的想法,他觉得挺好的。因为开始都是两个或三个字母,所以用来当 key. from: 1point3acres.com/bbs
比如 key (RT)  value (RAT, CURT, CART...)
这样每次查找的范围就小了。
不过我没写代码
回复 支持 反对

使用道具 举报

 楼主| 周珈羽 发表于 2016-9-9 11:28:30 | 显示全部楼层
shuiguo 发表于 2016-9-9 11:11
请问dictionary的size是多少?给的input是什么形式?需要自己建树么?

想了想感觉保证最短还挺难

这个我也可崩溃了,他没说 dictionary 什么结构,我问他,他说我自己选。。
我开始用 String[] 效率不好,后来优化的时候,可以改成 hashmap
回复 支持 反对

使用道具 举报

mren 发表于 2016-9-9 11:33:06 | 显示全部楼层
shuiguo 发表于 2016-9-9 11:24
请问如何转化为int并且保证car和rac是同一个key?而且还可能车牌是cr,对应的词是car,这种情况怎么办?

转化是这样的
int key = 0;
for(int i = 0; i < str.size(); i++). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    key |= (1<<(lowercase(str)-'a'));
比较的时候cr对于的数字和car对于的数字相与等于cr对于的数字即可进行查当前key下的单词
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 21:54:22 | 显示全部楼层
mren 发表于 2016-9-9 11:33
转化是这样的. 1point3acres.com/bbs
int key = 0;
for(int i = 0; i < str.size(); i++)

这个无法应对多个相同字母的情况吧
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-9-10 00:26:31 | 显示全部楼层
感觉是需要件trie的
回复 支持 反对

使用道具 举报

lyoaix 发表于 2016-9-10 01:32:32 | 显示全部楼层
houqingniao 发表于 2016-9-10 00:26
感觉是需要件trie的
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我的第一反应也是建trie 然后就可以直接找了
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-21 03:49:55 | 显示全部楼层
提取出字母,做char频统计,然后遍历dictionary,每个word做char频统计,输出包含所有车牌里的字母的最短的那个单词. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

yhl 发表于 2016-9-24 10:31:50 | 显示全部楼层
第二題用 edit distance 可以嗎?

补充内容 (2016-9-24 10:32):. visit 1point3acres.com for more.
說錯,不是第二題...我是指第二個函數...
回复 支持 反对

使用道具 举报

pinkdatura 发表于 2016-9-24 13:11:44 | 显示全部楼层
如果建立trie时候,是不是也需要把dictionary里word先sort好再插入trie树,遇到一个新的车牌,提取字母,然后sort后,在trie里查找?遇到重复字母,好像有点麻烦。
回复 支持 反对

使用道具 举报

morrisc1102 发表于 2016-9-25 08:48:32 | 显示全部楼层
pinkdatura 发表于 2016-9-24 13:11
如果建立trie时候,是不是也需要把dictionary里word先sort好再插入trie树,遇到一个新的车牌,提取字母,然 ...

如果要把word sort后再放入trie, 那return前要回复原本在dictionary的order.
一开始建一个sort -> unsort 的HashMap..
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 19:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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