2016/09/07 电面

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.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

“RC 10014” : “CAR”.

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

mren 发表于 2016-9-9 11:11
我觉得可以这样，建一个hash表，保存为形式，将字典中的每一个单词映射成一个整数，即a-z分别对于整数的0-2 ...

我**一只，以前地里也没见过这题，当时就能想起来啥就是啥了。
贴出题来，有空的看见的就练练手，万一谁碰到一样的呢，就算幸运了~~

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

我觉得这个题建 trie 会有问题。 假设有词典中有两个词"axx", "xxxx". 你的拍照是 "xx"。 这种情况下 你是不是找到的最短的是xxxx？
想了下, 还不如就和19楼说的那样遍历 dict， 根据车牌可能可以稍微做下优化。觉得车牌 应该是前面两个char， 后面最多2个char。 建一个map， key是26*26 的字幕组合，value是一个list， 根据词长排序。然后一个个查char 频统计是否ok。感觉这题的特征是牌照上的字母很少， 但是应该有更好的方法。

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[i])-'a'));
比较的时候cr对于的数字和car对于的数字相与等于cr对于的数字即可进行查当前key下的单词

How about PP 1234A? P should repeat in the word or not ?

请问这题你怎么做的呢？多谢！

zyoppy008 发表于 2016-9-9 10:28
How about PP 1234A? P should repeat in the word or not ?

“PP  1234O”   返回 pop 重复字母，个数也要一样   

william_gong 发表于 2016-9-9 10:42
请问这题你怎么做的呢？多谢！

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

周珈羽 发表于 2016-9-9 11:01
写了两个小函数，第一个提取原字符串中的字母 “RT 1234A”A --> “RTA”；
第二个check dictionary 里 ...

第二个函数是怎么写的呢？ sort 字典以后一个个比较吗？ 还是用trie来做？多谢！

william_gong 发表于 2016-9-9 11:02
第二个函数是怎么写的呢？ sort 字典以后一个个比较吗？ 还是用trie来做？多谢！

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

请问dictionary的size是多少？给的input是什么形式？需要自己建树么？

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

我觉得可以这样，建一个hash表，保存为[int, int]形式，将字典中的每一个单词映射成一个整数，即a-z分别对于整数的0-25位，具有相同映射的单词在hash表的同一个key下只保存其最短长度，然后再求出每一个车牌对应的字符串的整数映射，然后去和hash表的key做与操作，如果结果等于车牌的整数那就找到了结果

补充内容 (2016-9-9 11:14):
哦，忘了考虑重复字符，抱歉

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

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

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