一亩三分地论坛

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

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

热乎乎的Google店面3-17

[复制链接] |试试Instant~ |关注本帖
timtam85 发表于 2015-3-18 12:47:11 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Other

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

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

x
今天刚面的,发出来供大家参考一下,也为自己攒一下人品。

过程是先聊了一下我现在做的项目,然后讨论了一下项目里做过的优化,感觉面试官应该不是很care这个,只是例行问下。然后就上coding题了,题目之前看过类似的,就是给一个license plate,比如“AB12SF”,然后给一个dictionary,返回最短的含有全部字母的string,字母出现的顺序无所谓,比如字典里有“BACSDF”就算是hit。然后follow up是如果这个程序要被调用100次的话可以怎么优化。

我的解法是先把输入clean up,只留下字母,然后暴力解法。优化可以把字典按长度排序,第一个hit就是target。-google 1point3acres

面完这题之后面试官问我有什么问题,这时候只剩两三分钟了,然后我就问了个问题,然后他就讲开了,于是我们又聊了15分钟,感觉面试官很nice。

最后希望自己能拿到onsite,也希望大家都有好的offer。另外,我积分很低,版里好多帖子都要很高的积分才能看,希望大家能给我加加大米

评分

5

查看全部评分

cjlm007 发表于 2015-3-18 13:03:43 | 显示全部楼层
这题出镜率太高了
回复 支持 反对

使用道具 举报

williamshyy 发表于 2015-3-18 13:34:30 | 显示全部楼层
解法是不是: 建立一个bit串 把pattern每一位对应位置的bit置为1,然后dictionary对应的bit串每一位同样置位一次,然后两个bit串按位与一次。。。和pattern串相同的就留下,换下一个词
或者解法是不是:建立一个enum 把pattern里面每个字符对应一个质数,其他的字符对应成这些质数之后最小的质数,然后对pattern做乘法,留下乘积,然后留下为原pattern乘积倍数的词?
求标准答案. 鍥磋鎴戜滑@1point 3 acres
下周这时候面,已经要疯了
回复 支持 反对

使用道具 举报

莫小乐 发表于 2015-3-19 00:42:20 | 显示全部楼层
williamshyy 发表于 2015-3-18 13:34
解法是不是: 建立一个bit串 把pattern每一位对应位置的bit置为1,然后dictionary对应的bit串每一位同样置 ...

可以其他字符对应1?还有可能溢出吧?
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-3-19 00:47:31 | 显示全部楼层
williamshyy 发表于 2015-3-18 13:34
解法是不是: 建立一个bit串 把pattern每一位对应位置的bit置为1,然后dictionary对应的bit串每一位同样置 ...

能再详细说一下bit串的解法么,这样从pattern到dict里的每一个string都是一个256bits的bit串么?
回复 支持 反对

使用道具 举报

williamshyy 发表于 2015-3-19 02:24:49 | 显示全部楼层
EchoO 发表于 2015-3-19 00:47. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
能再详细说一下bit串的解法么,这样从pattern到dict里的每一个string都是一个256bits的bit串么?
. 1point3acres.com/bbs
是的,对应char的256个码...
回复 支持 反对

使用道具 举报

williamshyy 发表于 2015-3-19 02:25:34 | 显示全部楼层
莫小乐 发表于 2015-3-19 00:42
可以其他字符对应1?还有可能溢出吧?
. From 1point 3acres bbs
dict 里面每个字符都可以在256bit的bit串里找到自己的位置,然后置位1就可以了。。。
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-3-19 02:51:06 | 显示全部楼层
williamshyy 发表于 2015-3-19 02:24
. Waral 鍗氬鏈夋洿澶氭枃绔,是的,对应char的256个码...

但是因为要对dict所有string都扫一遍,其实复杂度和直接比较也没差
回复 支持 反对

使用道具 举报

莫小乐 发表于 2015-3-19 03:11:59 | 显示全部楼层
williamshyy 发表于 2015-3-19 02:25
dict 里面每个字符都可以在256bit的bit串里找到自己的位置,然后置位1就可以了。。。
. visit 1point3acres.com for more.
我是说你的解法2.。
回复 支持 反对

使用道具 举报

williamshyy 发表于 2015-3-19 03:27:26 | 显示全部楼层
莫小乐 发表于 2015-3-19 03:11
我是说你的解法2.。

解法2要跟面试官确认不考虑溢出的assumption
回复 支持 反对

使用道具 举报

williamshyy 发表于 2015-3-19 03:28:19 | 显示全部楼层
EchoO 发表于 2015-3-19 02:51
但是因为要对dict所有string都扫一遍,其实复杂度和直接比较也没差

不扫一遍怎么获取dict里面的string的信息呢?
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-3-27 08:06:23 | 显示全部楼层
williamshyy 发表于 2015-3-19 03:28
不扫一遍怎么获取dict里面的string的信息呢?
. visit 1point3acres.com for more.
那如果车牌有重复的char 呢  比如有两个A, 但是dict里面只有一个A呢
回复 支持 反对

使用道具 举报

williamshyy 发表于 2015-3-28 13:17:25 | 显示全部楼层
woshiee123 发表于 2015-3-27 08:06
那如果车牌有重复的char 呢  比如有两个A, 但是dict里面只有一个A呢

如果有重复的char那么bit串就变成int[256]了,或者用解法2,质数表求积
回复 支持 反对

使用道具 举报

ManitobaFarmer 发表于 2015-3-31 02:24:18 | 显示全部楼层
LZ 拿到 Onsite 了吗?
回复 支持 反对

使用道具 举报

 楼主| timtam85 发表于 2015-3-31 12:04:44 | 显示全部楼层
ManitobaFarmer 发表于 2015-3-31 02:24
LZ 拿到 Onsite 了吗?

恩,拿到了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 19:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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