我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 4761|回复: 26
收起左侧

2016/09/07 电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
周珈羽 发表于 2016-9-9 05:59:08 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

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 : 根据自己写的代码,问了问复杂度,然后优化


上一篇:Yelp OA
下一篇:Linkedin 电面 9/8

本帖被以下淘专辑推荐:

  • · Google|主题: 459, 订阅: 123
我的人缘0
zyoppy008 发表于 2016-9-9 10:28:51 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
How about PP 1234A? P should repeat in the word or not ?
回复 支持 反对

使用道具 举报

我的人缘0
william_gong 发表于 2016-9-9 10:42:38 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
请问这题你怎么做的呢?多谢!
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 周珈羽 发表于 2016-9-9 10:58:57 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
zyoppy008 发表于 2016-9-9 10:28
How about PP 1234A? P should repeat in the word or not ?

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

使用道具 举报

我的人缘0
 楼主| 周珈羽 发表于 2016-9-9 11:01:14 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
william_gong 发表于 2016-9-9 10:42
请问这题你怎么做的呢?多谢!

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

使用道具 举报

我的人缘0
william_gong 发表于 2016-9-9 11:02:24 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
周珈羽 发表于 2016-9-9 11:01
写了两个小函数,第一个提取原字符串中的字母 “RT 1234A”A --> “RTA”;
第二个check dictionary 里 ...

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

使用道具 举报

我的人缘0
 楼主| 周珈羽 发表于 2016-9-9 11:09:00 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
william_gong 发表于 2016-9-9 11:02
第二个函数是怎么写的呢? sort 字典以后一个个比较吗? 还是用trie来做?多谢!

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

使用道具 举报

我的人缘0
shuiguo 发表于 2016-9-9 11:11:06 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
请问dictionary的size是多少?给的input是什么形式?需要自己建树么?

想了想感觉保证最短还挺难
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
mren 发表于 2016-9-9 11:11:19 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
我觉得可以这样,建一个hash表,保存为[int, int]形式,将字典中的每一个单词映射成一个整数,即a-z分别对于整数的0-25位,具有相同映射的单词在hash表的同一个key下只保存其最短长度,然后再求出每一个车牌对应的字符串的整数映射,然后去和hash表的key做与操作,如果结果等于车牌的整数那就找到了结果

补充内容 (2016-9-9 11:14):
哦,忘了考虑重复字符,抱歉. 1point 3acres 论坛

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

使用道具 举报

我的人缘0
shuiguo 发表于 2016-9-9 11:24:23 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
mren 发表于 2016-9-8 22:11
我觉得可以这样,建一个hash表,保存为形式,将字典中的每一个单词映射成一个整数,即a-z分别对于整数的0-2 ...
. more info on 1point3acres
请问如何转化为int并且保证car和rac是同一个key?而且还可能车牌是cr,对应的词是car,这种情况怎么办?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 周珈羽 发表于 2016-9-9 11:26:59 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
mren 发表于 2016-9-9 11:11. 一亩-三分-地,独家发布
我觉得可以这样,建一个hash表,保存为形式,将字典中的每一个单词映射成一个整数,即a-z分别对于整数的0-2 ...

. 围观我们@1point 3 acres我**一只,以前地里也没见过这题,当时就能想起来啥就是啥了。
贴出题来,有空的看见的就练练手,万一谁碰到一样的呢,就算幸运了~~

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

使用道具 举报

我的人缘0
 楼主| 周珈羽 发表于 2016-9-9 11:28:30 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
shuiguo 发表于 2016-9-9 11:11. 牛人云集,一亩三分地
请问dictionary的size是多少?给的input是什么形式?需要自己建树么?

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

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

使用道具 举报

我的人缘0
mren 发表于 2016-9-9 11:33:06 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
shuiguo 发表于 2016-9-9 11:24
请问如何转化为int并且保证car和rac是同一个key?而且还可能车牌是cr,对应的词是car,这种情况怎么办?

转化是这样的
int key = 0;. from: 1point3acres
for(int i = 0; i < str.size(); i++)
    key |= (1<<(lowercase(str)-'a'));
比较的时候cr对于的数字和car对于的数字相与等于cr对于的数字即可进行查当前key下的单词
回复 支持 反对

使用道具 举报

我的人缘0
william_gong 发表于 2016-9-9 21:54:22 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
mren 发表于 2016-9-9 11:33
转化是这样的
int key = 0;-google 1point3acres
for(int i = 0; i < str.size(); i++)
. visit 1point3acres for more.
这个无法应对多个相同字母的情况吧
回复 支持 反对

使用道具 举报

我的人缘0
houqingniao 发表于 2016-9-10 00:26:31 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
感觉是需要件trie的
回复 支持 反对

使用道具 举报

我的人缘0
lyoaix 发表于 2016-9-10 01:32:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
houqingniao 发表于 2016-9-10 00:26. 一亩-三分-地,独家发布
感觉是需要件trie的
.本文原创自1point3acres论坛
我的第一反应也是建trie 然后就可以直接找了
回复 支持 反对

使用道具 举报

我的人缘0
pawprinter 发表于 2016-9-21 03:49:55 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
提取出字母,做char频统计,然后遍历dictionary,每个word做char频统计,输出包含所有车牌里的字母的最短的那个单词
回复 支持 反对

使用道具 举报

我的人缘0
yhl 发表于 2016-9-24 10:31:50 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第二題用 edit distance 可以嗎?

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

使用道具 举报

我的人缘0
pinkdatura 发表于 2016-9-24 13:11:44 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
如果建立trie时候,是不是也需要把dictionary里word先sort好再插入trie树,遇到一个新的车牌,提取字母,然后sort后,在trie里查找?遇到重复字母,好像有点麻烦。
回复 支持 反对

使用道具 举报

我的人缘0
morrisc1102 发表于 2016-9-25 08:48:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
pinkdatura 发表于 2016-9-24 13:11
如果建立trie时候,是不是也需要把dictionary里word先sort好再插入trie树,遇到一个新的车牌,提取字母,然 ...

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-28 07:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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