一亩三分地论坛

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

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

Google Intern新鲜面经

[复制链接] |试试Instant~ |关注本帖
nemoleoliu 发表于 2015-12-9 09:16:40 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Pass其他

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

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

x
本人人生第一次电面 献给了狗哥。。。来此回报论坛
第一轮 白人小哥
1. input: 一个String的list , 规则是如果两个String 可以通过rotate n操作得到,那么就为一组,e.g. “abcd" 和“bcde”  "aabb" 和“eeff”  第一个pair是rotate了 1  第二个pair是rotate了4
要求输出分组结果 List<List<String>>  ps. 只有lowercase, 不用考虑duplicate.鐣欏璁哄潧-涓浜-涓夊垎鍦
2. 写两个function 分别对 List<String> 和 String 进行encode 和decode  

第二轮 白人小哥
1. 求两个sorted数组的intersection e.g. [1,2,3,4,5],[2,4,6] 结果是[2,4]
2. Maximum Subarray  leetcode原题

两轮小哥都很nice!
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
面完3个小时给的结果 告诉过了 进入match project阶段, 求各位叔叔大爷收留!. from: 1point3acres.com/bbs

评分

5

查看全部评分

xiaozhuxiaozhu 发表于 2015-12-9 12:08:23 | 显示全部楼层
第一题是,所有数组都以string的实行存在在以个list里面? 比如 [ “abcd","bacd","cccc","ddds"....]这样?
然后找出所有pair,满足上面的要求?每个词都rotate相同的次数,然后可以到另外以个词?

如果我理解对了,这题可以这么做么。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  走2个for loop遍历每以个词的pair组合,然后covert每个词tochararry, charAt[index1] - charAt[index2]。如果每个char相减的数相同,那么说明这个pair满足要求。
比如,
abcd, bcde.   'b'-'a' = 'c'-'b'='d-c' = 'e'-'d' = 1 所以,这个pair是对的。


.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-1-7 10:37):
这个不是optimal solution
回复 支持 1 反对 0

使用道具 举报

include110 发表于 2015-12-9 09:43:36 | 显示全部楼层
求问第一题的第一问是什么意思啊?"abcd" rotate 1 不是“bcda”吗?这题应该怎么解啊?谢谢
回复 支持 反对

使用道具 举报

 楼主| nemoleoliu 发表于 2015-12-9 09:46:26 | 显示全部楼层
include110 发表于 2015-12-9 09:43
求问第一题的第一问是什么意思啊?"abcd" rotate 1 不是“bcda”吗?这题应该怎么解啊?谢谢
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
rotate是每个character rotate一下 不是整体string rotate   a-b-c-d-e-f-g-h-...x-y-z 按照字母表顺序 rotate a rotate 1 就是b rotate 25 就是z rotate 26 就是a
hashmap key是每个单词转换成首字母为a的形式  value存list 然后把 所有value输出
回复 支持 反对

使用道具 举报

alphard 发表于 2015-12-9 09:50:06 | 显示全部楼层
QUQ蹭一下楼主的好运 我也面完三小时完全没动静 估计要被拒
回复 支持 反对

使用道具 举报

include110 发表于 2015-12-9 09:51:37 | 显示全部楼层
方法很不错,谢谢了,还有就是你是国内大学还是国外的?感觉地里很多都是说的国外的面试,不知道这些国内的是不是也有参考价值?
回复 支持 反对

使用道具 举报

include110 发表于 2015-12-9 09:52:25 | 显示全部楼层
alphard 发表于 2015-12-9 09:50
QUQ蹭一下楼主的好运 我也面完三小时完全没动静 估计要被拒
. 1point 3acres 璁哄潧
求发经验贴啊,好人一生平安~~~
回复 支持 反对

使用道具 举报

 楼主| nemoleoliu 发表于 2015-12-9 09:52:25 | 显示全部楼层
alphard 发表于 2015-12-9 09:50
QUQ蹭一下楼主的好运 我也面完三小时完全没动静 估计要被拒

淡定 我的这个hr比较敬业 有的hr比较懒 不会马上收集feedback 会拖一两天
回复 支持 反对

使用道具 举报

 楼主| nemoleoliu 发表于 2015-12-9 09:56:10 | 显示全部楼层
include110 发表于 2015-12-9 09:51
方法很不错,谢谢了,还有就是你是国内大学还是国外的?感觉地里很多都是说的国外的面试,不知道这些国内的 ...

额 我也是国外,国内的google 听说相当难0.0 ACM级别吧
回复 支持 反对

使用道具 举报

gisonrg 发表于 2015-12-9 10:01:26 | 显示全部楼层
哈哈恭喜!楼主第一个人的题和我的第二个小哥出的题一模一样的,估计是同一个人吧。。。
然而为什么我都一个星期了还没结果TAT
沾点楼主好运求进pool。。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2015-12-9 11:12:17 | 显示全部楼层
nemoleoliu 发表于 2015-12-9 09:46
rotate是每个character rotate一下 不是整体string rotate   a-b-c-d-e-f-g-h-...x-y-z 按照字母表顺序 r ...

是不是可以这样做 ?: 每次判断 if str1-'a'==str2-'a'-n , n is rotation number
回复 支持 反对

使用道具 举报

wtcupup 发表于 2015-12-9 11:12:24 | 显示全部楼层
nemoleoliu 发表于 2015-12-9 09:46
rotate是每个character rotate一下 不是整体string rotate   a-b-c-d-e-f-g-h-...x-y-z 按照字母表顺序 r ...

是不是可以这样做 ?: 每次判断 if str1-'a'==str2-'a'-n , n is rotation number

补充内容 (2015-12-9 11:13):
str1.charAt(i)-'a'==str2.charAt(i)-'a'-n
回复 支持 反对

使用道具 举报

gisonrg 发表于 2015-12-9 11:21:27 | 显示全部楼层
wtcupup 发表于 2015-12-9 11:12. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
是不是可以这样做 ?: 每次判断 if str1-'a'==str2-'a'-n , n is rotation number. more info on 1point3acres.com

补充内容 (2015-12-9 1 ...
. 1point 3acres 璁哄潧
n是unknown的,你不知道每个string是从base case rotate了几次
回复 支持 反对

使用道具 举报

 楼主| nemoleoliu 发表于 2015-12-9 11:50:09 | 显示全部楼层
最简单的方法就是 将每个string 都做一下旋转操作 使得第一个字母是a
回复 支持 反对

使用道具 举报

 楼主| nemoleoliu 发表于 2015-12-9 11:51:32 | 显示全部楼层
gisonrg 发表于 2015-12-9 10:01
哈哈恭喜!楼主第一个人的题和我的第二个小哥出的题一模一样的,估计是同一个人吧。。。
然而为什么我都一 ...

ez  我同学也是等了一个星期才出的结果 他也过了
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-9 12:09:25 | 显示全部楼层
第2轮的第1题是卖萌么。还是有什么特殊的follow-up?. 1point3acres.com/bbs

补充内容 (2015-12-9 12:10):
有空间和时间复杂度的特殊要求么?
回复 支持 反对

使用道具 举报

 楼主| nemoleoliu 发表于 2015-12-9 13:26:32 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-9 12:09
第2轮的第1题是卖萌么。还是有什么特殊的follow-up?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2015-12-9 12:10):

O(m+n) no additional memory
回复 支持 反对

使用道具 举报

gisonrg 发表于 2015-12-9 13:26:53 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-9 12:08. visit 1point3acres.com for more.
第一题是,所有数组都以string的实行存在在以个list里面? 比如 [ “abcd","bacd","cccc","ddds"....]这 ...

我和你的思路差不多,找出char之间的distance, 但是用不着两个for loop
比如abcd,不管怎么rotate,char之间的distance总是['b'-'a','c'-'b','d'-'c'] = [1,1,1],把这个distance弄成一个string,比如abcd就成了“111”, cab 就成了"-21"(如果是single char肯定都是同一组),用一个hashmap把有着相同distance的string都放在一起就好了
不过题主的全部转成’a'开头是个很好的点子呀!当时我咋没想到,还是先给的brute force再被小哥提示一下才想到这么做的
总之这题的思路就是pre-process一下把所有的string都map去它的group,就可以用O(n)的时间解出来了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-9 13:32:05 | 显示全部楼层
nemoleoliu 发表于 2015-12-9 13:26
O(m+n) no additional memory

那就是用merge sorted array那种,比较每个index上面的数,根据大,小,等于三种情况增加index么
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-9 13:41:37 | 显示全部楼层
gisonrg 发表于 2015-12-9 13:26
. 1point 3acres 璁哄潧我和你的思路差不多,找出char之间的distance, 但是用不着两个for loop
比如abcd,不管怎么rotate,char ...

我以为pair是指必须2个2个放在一起。
翻转a确实是很好的方法。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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