一亩三分地论坛

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

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

2.18 Google实习 on campus recruitment 跪经

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

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 校园招聘会 |Failfresh grad应届毕业生

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

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

x
18号在学校面的,一共两轮技术面,每轮45分钟,今天下午收到电话说没有后续了,打击太大对着电话说不出话来。。

第一轮是个白人小哥,上来旁敲侧击问了一些和项目相关的问题。coding题是一个数列表示的森林,对每个元素只知道它的父结点的index,要求删除指定的结点,同时cascade删除所有它的子结点。follow up问算法复杂度。然后就让我问和谷歌相关的问题了。

第二轮是个印度小哥,本科ucb研究生佐治亚理工。互相自我介绍完开始Coding。一条0到100的直线上掉正方形盒子下来,盒子只要能重叠久能累加,不考虑物理重心。写两个函数,一个掉盒子函数,一个返回直线指定整数点处的高度。follow up延伸0到100范围到任意范围,不限制整数可以要求小数之类的。

. Waral 鍗氬鏈夋洿澶氭枃绔,来攒个人品聊以慰籍。. 1point 3acres 璁哄潧

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-2-24 06:06):
森林的根结点的父结点index就是自己的index

评分

3

查看全部评分

dondon91 发表于 2016-2-24 12:28:38 | 显示全部楼层
安抚LZ一下~ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问第一题森体,lz的复杂度是多少? 我觉得brute force的话应该是O(n^2)吧,可不可以将数组转换成有向图,然后用DFS/BFS删除所有的字节点,再换成数组,这样会不会是O(n)复杂度呢?
回复 支持 反对

使用道具 举报

dondon91 发表于 2016-2-24 12:38:32 | 显示全部楼层
又来问第二题了LZ, 感觉是OOP问题吧。 盒子大小是固定的吗? 投的时候正方形中心一定在直线上吗?投放的时候一定是边平行于直线吗?
如果是完全随机投放,感觉细节太多了啊。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-24 14:03:07 | 显示全部楼层
dondon91 发表于 2016-2-24 12:28
安抚LZ一下~
请问第一题森体,lz的复杂度是多少? 我觉得brute force的话应该是O(n^2)吧,可不可以将数组 ...

不会。你用数组构造邻接表就已经n^2复杂度了
回复 支持 反对

使用道具 举报

dondon91 发表于 2016-2-24 14:16:46 | 显示全部楼层
johnjavabean 发表于 2016-2-24 00:03. from: 1point3acres.com/bbs
不会。你用数组构造邻接表就已经n^2复杂度了
. From 1point 3acres bbs
不对吧,每个节点只能有一个父节点,所以结构有点类似于多叉树,总共就只有n边,构建图复杂度是O(n)。
回复 支持 反对

使用道具 举报

laiguojiuhao 发表于 2016-2-24 14:43:24 | 显示全部楼层
第一个题用类似union-find的操作呢?把要删除的节点设为根节点,然后复制一遍数组,但是这轮复制的时候同时做path compression,就能够找到是否rooted在要删除的节点上了,这样应该是O(nlogn)吧
回复 支持 反对

使用道具 举报

 楼主| prasca 发表于 2016-2-24 20:21:20 | 显示全部楼层
dondon91 发表于 2016-2-24 14:16
不对吧,每个节点只能有一个父节点,所以结构有点类似于多叉树,总共就只有n边,构建图复杂度是O(n)。

第一题面试官帮我简化了,给定的参数是原森林数组和需要删除的同size布尔数组,loop过一遍每个元素,如果需要删除,就再一个loop找父结点是这个元素的进行删除,递归地删,复杂度n方

第二题平行掉,掉的参数规定为盒子左边界掉落点和盒子边长(正方形,边长等于高度)。
回复 支持 反对

使用道具 举报

18658109706 发表于 2016-2-25 00:09:58 | 显示全部楼层
掉盒子的函数有什么具体要求?还是随机掉?.1point3acres缃
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-5 12:29:42 | 显示全部楼层
第一题是要先加一个从父亲节点到子节点的树,然后再删除吗? 第二题应该是每次给盒子两端的端点,左边+1, 右边减1,然后每次扫一下点吧
回复 支持 反对

使用道具 举报

 楼主| prasca 发表于 2016-3-6 00:01:12 | 显示全部楼层
bobzhang2004 发表于 2016-3-5 12:29
第一题是要先加一个从父亲节点到子节点的树,然后再删除吗? 第二题应该是每次给盒子两端的端点,左边+1,  ...
. 鍥磋鎴戜滑@1point 3 acres
第一题直接scan整个数组判断parent_index是不是所要求删除的,然后递归调用delete函数删除这个节点。.1point3acres缃
第二题左边不用加一,右边界要减,相当于[left_index, right_index)区间改高度

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-6 00:34:50 | 显示全部楼层
prasca 发表于 2016-3-6 00:01
第一题直接scan整个数组判断parent_index是不是所要求删除的,然后递归调用delete函数删除这个节点。
第 ...

左边不加一的话,怎么知道有一个方块掉在那里呢?还有就是每次得到高度都得从左向右扫一遍吧,但这样的话需要将这【0, 100】看成有限的点吧
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-1 01:01:05 | 显示全部楼层
盒子这个没看懂是怎么累加的...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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