一亩三分地论坛

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

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

12.7 Google intern 第一轮电面

[复制链接] |试试Instant~ |关注本帖
printf_ll 发表于 2015-12-8 05:48:57 | 显示全部楼层 |阅读模式

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

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

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

x
第一轮,碰上个三哥,勉强还听得清
可能是做得太差了,只做了一题
题目:give a tournment tree, the parent is the smallest of its children, the number of children is 0 or 2, find the second smallest one
e.g:
               2 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
         2            3
     2     4       3    5
so the second smallest one is 3
一上来就想用priorityqueue来实现,不断被他提示不用全部遍历
几经指点下,用了递归,每次比较该结点的较大子结点和已有的secMin的大小(若比secMin小,则更新secMin),同时递归较小子结点( 较大子结点不需要再进入寻找,因为不可能存在更小的数)
follow up: the number of children is larger than 2
把寻找min和secMin结点的方式改为了遍历
. more info on 1point3acres.com
第二轮,
第一题是leetcode原题,Closest Binary Search Tree Value,输入只考虑整数,不考虑double
第二题,提到了serizaliation/deserizaliation,让我设计树的数据结构(general tree, not binary tree),写了一个value, 一个arraylist<Tree> children. From 1point 3acres bbs
接下来是几分钟的沉默,在最后又问我,在client和server之间要考虑什么,并如何实现serizaliation,输出是outputstream,此时已经听不大懂他在讲什么了==、而且时间快到了,便匆忙写了outputstream.write(XXX),因为这一块没有了解过

求人品

评分

2

查看全部评分

ohyline 发表于 2015-12-8 18:14:00 | 显示全部楼层
祝楼主好运啊~ 遇到新题如此沉稳 一定没有问题的 坐等好消息!
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-12-9 04:35:20 | 显示全部楼层
请问 tournment tree,这题是永远只求second smallest吗还是求kth smallest,应该还是要左右子树都遍历的吧。想请楼主再稍作解释
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2015-12-9 05:08:54 | 显示全部楼层
aiweiwei 发表于 2015-12-9 04:35
请问 tournment tree,这题是永远只求second smallest吗还是求kth smallest,应该还是要左右子树都遍历的吧 ...

面试的时候只要求second,没有kth的要求,所以不用遍历全部的子树
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-12-9 10:37:26 | 显示全部楼层
printf_ll 发表于 2015-12-9 05:08. Waral 鍗氬鏈夋洿澶氭枃绔,
面试的时候只要求second,没有kth的要求,所以不用遍历全部的子树

那不就是第二层里面大的那个就好了
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-9 11:04:34 | 显示全部楼层
为什么我的面试两轮都是一题,,而且面试官并没有出第二题的意思。。。。
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2015-12-9 11:06:31 | 显示全部楼层
aiweiwei 发表于 2015-12-9 10:37
那不就是第二层里面大的那个就好了

我一开始也是这么想的,但是立马就想到了反例:
              2
      2               4
  2       3      4       5
就是只能肯定在大的那一分支是肯定不用再遍历的,但是小的分支需要一直遍历到底
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2015-12-9 11:07:02 | 显示全部楼层
小A要当码农 发表于 2015-12-9 11:04
为什么我的面试两轮都是一题,,而且面试官并没有出第二题的意思。。。。

也有可能是他们就只准备了一题?(′・_・`)我不太清楚诶
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-9 11:17:08 | 显示全部楼层
lz是收到内推确认以后,多久被通知电面的。
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2015-12-9 11:18:07 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-9 11:17
lz是收到内推确认以后,多久被通知电面的。

很快吧,两三天内就确定下了日期了
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-9 11:19:43 | 显示全部楼层
printf_ll 发表于 2015-12-9 11:18
很快吧,两三天内就确定下了日期了
. Waral 鍗氬鏈夋洿澶氭枃绔,
我今天收到内推确认,如果很长时间不联系我,就是简历被据了吧?
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2015-12-9 11:23:35 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-9 11:19
我今天收到内推确认,如果很长时间不联系我,就是简历被据了吧?

应该是这样的
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-9 11:29:14 | 显示全部楼层
printf_ll 发表于 2015-12-9 11:23. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
应该是这样的

我以为google内推都会拿到面试呢
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2015-12-9 11:43:44 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-9 11:29
我以为google内推都会拿到面试呢
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这也是我猜的。。。不肯定的哈
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-12-10 23:33:31 | 显示全部楼层
printf_ll 发表于 2015-12-9 11:06
我一开始也是这么想的,但是立马就想到了反例:
              2
      2               4

ok 清楚了,多谢楼主解释,祝福楼主拿offer~~~!!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 10:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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