一亩三分地论坛

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

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

Google 02/11 实习电面

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

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

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

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

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调用很多次,怎么做能更快

. visit 1point3acres.com for more.二面(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 按上述方法分类-google 1point3acres
此题楼猪做题地里看到过,遂说了两种方法让欧洲小哥挑. Waral 鍗氬鏈夋洿澶氭枃绔,
follow up: Edge case 是啥,complexity 算算. 1point3acres.com/bbs
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)的。

楼猪答  先来个naive的把,虽慢但work。 后来又补充说,可以在dfs的时候count 已经当前permutation数量,到了n 就停。. 鍥磋鎴戜滑@1point 3 acres
小哥答:还是要算很多,可不可以其他的一个不算?. 1point3acres.com/bbs
楼猪遂有点懵,喃喃自语,忽然窗外树缝中投下一束光,茅塞顿开。. visit 1point3acres.com for more.



评分

1

查看全部评分

houqingniao 发表于 2016-2-12 06:30:07 | 显示全部楼层
二面attemp1, 为啥需要hash啊?直接对比不行吗?
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-2-12 06:35:57 | 显示全部楼层
permutation 的array是sorted吗?
回复 支持 反对

使用道具 举报

 楼主| aidmony 发表于 2016-2-12 07:04:40 | 显示全部楼层
houqingniao 发表于 2016-2-12 06:35. more info on 1point3acres.com
permutation 的array是sorted吗?

你可以assume是sorted,不过也不需要这个assumption,permutation的顺训跟array里的element顺序一致
回复 支持 反对

使用道具 举报

 楼主| aidmony 发表于 2016-2-12 07:05:09 | 显示全部楼层
houqingniao 发表于 2016-2-12 06:30. From 1point 3acres bbs
二面attemp1, 为啥需要hash啊?直接对比不行吗?

也行啊,搞个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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 11:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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