May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 650|回复: 7
收起左侧

Google 02/11 实习电面

[复制链接] |试试Instant~ |关注本帖
aidmony 发表于 2016-2-12 06:13:42 | 显示全部楼层 |阅读模式

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

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

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

x
本人没刷过leetcode。。。全靠地里面经挑着做做,在此奉上G家一二面经,求祝福求进pool


一面.鐣欏璁哄潧-涓浜-涓夊垎鍦
1. 写个function 判断一个数字string 翻转 180度是不是跟原来一样。 e.g. “108” ->"801": False, "205" ->不是数字stirng: False, “619” -> "619": True
2. 第一题的extension, 给input n, 写个function 返回所有长度为n 的 上述对称数字string
follow up:如果第二个function调用很多次,怎么做能更快

二面(attemp 1):
1. 给一个abbrevation 方法定义为: "abcdef" - > "a4f", "bdg" - > ''b1g"。 给一个word,一个array of words, 写一个function判断这个word的abbrevation是否和list 任一单词的abbrevation 一样。
楼猪看了题好开心,这个不是hash弄弄搞定吗。 然,interviwer说电话听出清,此次面试cannot continue due to technical difficulty,约改日再面。

二面(attemp 2):

1. 给一个encoding 方法定义: "abc" -> "bcd",  or "hij", or "zab"。就是把每个char shift任一distance的意思,然后这个shift mod 26 循环。 “abc” 和它的所有encoding 属于同一个group, “abd” 和它的所有encoding属于同一个group, et al. 给一个list of stirngs,将其中的string 按上述方法分类
此题楼猪做题地里看到过,遂说了两种方法让欧洲小哥挑
follow up: Edge case 是啥,complexity 算算
2. 给一个array of integers, e.g. [1,2,3]。 它的所有permutation可以sort为: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]。写一个function 返回input array 的 nth permutation。要求不compute任何其他permutation,就是不能算了所有permutation再返回第n个。如果input array 长度为k,naive 方法要O(k!), 小哥要O(k)的。.鏈枃鍘熷垱鑷1point3acres璁哄潧

楼猪答  先来个naive的把,虽慢但work。 后来又补充说,可以在dfs的时候count 已经当前permutation数量,到了n 就停。.鏈枃鍘熷垱鑷1point3acres璁哄潧
小哥答:还是要算很多,可不可以其他的一个不算?
楼猪遂有点懵,喃喃自语,忽然窗外树缝中投下一束光,茅塞顿开。



评分

1

查看全部评分

houqingniao 发表于 2016-2-12 06:30:07 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
二面attemp1, 为啥需要hash啊?直接对比不行吗?
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-2-12 06:35:57 | 显示全部楼层
关注一亩三分地微博:
Warald
permutation 的array是sorted吗?
回复 支持 反对

使用道具 举报

 楼主| aidmony 发表于 2016-2-12 07:04:40 | 显示全部楼层
houqingniao 发表于 2016-2-12 06:35
permutation 的array是sorted吗?
. 1point3acres.com/bbs
你可以assume是sorted,不过也不需要这个assumption,permutation的顺训跟array里的element顺序一致
回复 支持 反对

使用道具 举报

 楼主| aidmony 发表于 2016-2-12 07:05:09 | 显示全部楼层
houqingniao 发表于 2016-2-12 06:30
二面attemp1, 为啥需要hash啊?直接对比不行吗?
. more info on 1point3acres.com
也行啊,搞个hash,多次调用快点
回复 支持 反对

使用道具 举报

Firechaser 发表于 2016-2-12 09:42:59 | 显示全部楼层
除了最后一题都是lc原题,最后一题是用排列组合先算一下?
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-12 09:44:11 | 显示全部楼层
Firechaser 发表于 2016-2-12 09:42
除了最后一题都是lc原题,最后一题是用排列组合先算一下?

最后一题也是lc原题lc 60
回复 支持 反对

使用道具 举报

Firechaser 发表于 2016-2-12 09:49:32 | 显示全部楼层
johnjavabean 发表于 2016-2-12 09:44
最后一题也是lc原题lc 60

哦哦,刷题不精
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-28 20:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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