一亩三分地论坛

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

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

Google Intern 电面 10/3

[复制链接] |试试Instant~ |关注本帖
r39xu 发表于 2016-10-4 08:57:05 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
今下午刚刚面完Google Winter Intern 的电面, 两轮phone, 面试官是两个印度人求点人品,顺便希望能进host match!


直接说题吧!

第一轮:
1. 给一个array, 找出这个array 的local minimum。 Local minimum的定义是小于左边并且小于右边。
2. 给一个tree, 求所有root to leaf 组成数字的和。 比如
     3
   /   \
  3    1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
/  \  
1  2        就是 331 + 332 + 31
. Waral 鍗氬鏈夋洿澶氭枃绔,

3. 给一个string, 求一个permutation让没有两个相邻的char相等. 比如 abba -> abab

第二轮:

1. 给一个tree, 一滴水从root到leaf, 每段edge都有一个时间, 是水滴穿过的时间。求问多久整个tree都会变湿。
2. Given a large file (larger than computer memory), file contains many integers.所有integer都是(0-10k). Get the smallest k integers. 要求O(n)





评分

3

查看全部评分

本帖被以下淘专辑推荐:

jy_121 发表于 2016-10-4 09:51:12 | 显示全部楼层
问下楼主第二轮第二题怎么答的,谢谢。
回复 支持 1 反对 0

使用道具 举报

mdzzxswl 发表于 2016-10-4 09:05:34 | 显示全部楼层
一滴水那个没看懂啊啊啊啊
回复 支持 反对

使用道具 举报

 楼主| r39xu 发表于 2016-10-4 09:29:52 | 显示全部楼层
mdzzxswl 发表于 2016-10-4 09:05
一滴水那个没看懂啊啊啊啊
.1point3acres缃
其实就是想成一个weighted tree, 然后求weight最大的root->leaf 的path~
回复 支持 反对

使用道具 举报

mdzzxswl 发表于 2016-10-4 09:43:11 | 显示全部楼层
r39xu 发表于 2016-10-4 09:29
其实就是想成一个weighted tree, 然后求weight最大的root->leaf 的path~

这样!还有 为什么lz是winter的呀是自己选的吗~
回复 支持 反对

使用道具 举报

 楼主| r39xu 发表于 2016-10-4 10:10:46 | 显示全部楼层
jy_121 发表于 2016-10-4 09:51
问下楼主第二轮第二题怎么答的,谢谢。

我开始想把large file分割成一个一个subfile 后来面试官hint下想到可以用Bucketsort的方法, 建立一个10k size的bucket 然后面试官说好 给你一个hasNext() 和 next()的函数来traverse这个file 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

中间有些小bug没有想到。。毕竟好久没练bucket sort了 也不知道这样做是不是对的

做个参考吧
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-10-4 10:21:02 | 显示全部楼层
r39xu 发表于 2016-10-4 10:10
我开始想把large file分割成一个一个subfile 后来面试官hint下想到可以用Bucketsort的方法, 建立一个10k  ...

多谢回复,没有注意取值范围,这样应该是可以的
回复 支持 反对

使用道具 举报

deadline1314 发表于 2016-10-4 10:25:50 | 显示全部楼层
请问楼主投了多久来的interview啊
回复 支持 反对

使用道具 举报

Romeobaby 发表于 2016-10-4 10:47:15 | 显示全部楼层
第二轮 第二题 可以用 size 为 k 的min heap 吗?
回复 支持 反对

使用道具 举报

 楼主| r39xu 发表于 2016-10-4 11:07:48 | 显示全部楼层
Romeobaby 发表于 2016-10-4 10:47
第二轮 第二题 可以用 size 为 k 的min heap 吗?

当时也有提到min heap, 不过好像不符合O(n)的要求
回复 支持 反对

使用道具 举报

 楼主| r39xu 发表于 2016-10-4 11:08:55 | 显示全部楼层
deadline1314 发表于 2016-10-4 10:25
请问楼主投了多久来的interview啊

前后大概两周,9月初内推得,然后中旬得到的面试。
回复 支持 反对

使用道具 举报

 楼主| r39xu 发表于 2016-10-4 11:09:29 | 显示全部楼层
mdzzxswl 发表于 2016-10-4 09:43
这样!还有 为什么lz是winter的呀是自己选的吗~

其实我是学校必须要求winter coop才找的~
回复 支持 反对

使用道具 举报

Romeobaby 发表于 2016-10-4 11:09:40 | 显示全部楼层
r39xu 发表于 2016-10-4 11:07
当时也有提到min heap, 不过好像不符合O(n)的要求

哦对的, 我看漏了。-google 1point3acres
那确实就是桶排序,把数字塞到对应的桶里,从最小的开始找够k个。. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

iejr 发表于 2016-10-4 11:26:24 | 显示全部楼层
第二轮第二题,不知道我有没有理解正确,所有的整数取值范围在[0,10000]的话,我觉得可以用counting sort来做,内存可以放下这么多,是线性时间和空间复杂度;
. 1point 3acres 璁哄潧
第一轮最后那题没想明白怎么做?有可能一个串是"aaaaaaa"吗这样怎么排都不行
回复 支持 反对

使用道具 举报

 楼主| r39xu 发表于 2016-10-4 12:54:07 | 显示全部楼层
iejr 发表于 2016-10-4 11:26
第二轮第二题,不知道我有没有理解正确,所有的整数取值范围在[0,10000]的话,我觉得可以用counting sort来 ...

第二轮第二题应该就是你说的那样去做
. visit 1point3acres.com for more.
另外string permutaiton那个题应该是假设有valid解的
回复 支持 反对

使用道具 举报

362802781 发表于 2016-10-18 03:10:39 | 显示全部楼层
请问楼主,这些题都是要把code写下来的还是只是口头说说呀。 面试官会不会告诉这些code过没过test...
回复 支持 反对

使用道具 举报

木易wen 发表于 2016-10-19 05:11:38 | 显示全部楼层
第二问既然数字最大只有10k,O(n),就通排序?
回复 支持 反对

使用道具 举报

 楼主| r39xu 发表于 2016-10-20 02:48:54 | 显示全部楼层
362802781 发表于 2016-10-18 03:10
请问楼主,这些题都是要把code写下来的还是只是口头说说呀。 面试官会不会告诉这些code过没过test...

google doc写下来。如果有bug他会说的
回复 支持 反对

使用道具 举报

 楼主| r39xu 发表于 2016-10-20 02:49:06 | 显示全部楼层
木易wen 发表于 2016-10-19 05:11
第二问既然数字最大只有10k,O(n),就通排序?

应该是的,但是我挂了GG
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-31 09:34:04 | 显示全部楼层
r39xu 发表于 2016-10-20 02:49
应该是的,但是我挂了GG

. Waral 鍗氬鏈夋洿澶氭枃绔,个人觉得第二轮第二题既然说到内存放不下了,面试官是想听你说external sort吧?另外minHeap也是O(N)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 12:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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