一亩三分地论坛

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

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

[找工就业] google 电面面经

[复制链接] |试试Instant~ |关注本帖
lwbshr 发表于 2014-12-10 02:18:53 | 显示全部楼层 |阅读模式

2014(10-12月)-[13]CS本科+<3个月短暂实习/全职 - 猎头| 码农类全职@Google

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

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

x
google电面了我两次,本来是应该只有一次的,后面觉得犹豫又加了一次,还是跪了

第一次电面:
. from: 1point3acres.com/bbs 1. 两个数组分别代表两个整数,相加。lc原题。回答最优情况下的复杂度。
2. 迷宫寻宝。一个grid表示的地图,上面有宝物,有障碍,要求找出图上一个点到所有宝物的总距离最短。我用了bfs

第二次电面:.1point3acres缃
1. 在某个游戏中设计一个排名更新算法。排名是根据各玩家的分数决定的,从高到低。设计数据结构。实现两个函数:第一个:输入是玩家名,输出是玩家排名;第二个:输入是玩家名和玩家的新分数,要求更新排名。

2. 把一个整数组里所有零移到后面。


评分

2

查看全部评分

flyaway25 发表于 2014-12-10 02:47:46 | 显示全部楼层
lz你是今天面的二面还是今天通知了你二面的结果?
回复 支持 反对

使用道具 举报

 楼主| lwbshr 发表于 2014-12-10 07:42:29 | 显示全部楼层
flyaway25 发表于 2014-12-10 02:47
lz你是今天面的二面还是今天通知了你二面的结果?

前两天通知二面的结果
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2014-12-10 08:21:34 | 显示全部楼层
lz 第一面的bfs需要优化吗 感觉复杂度很高啊
回复 支持 反对

使用道具 举报

 楼主| lwbshr 发表于 2014-12-11 01:16:41 | 显示全部楼层
xdrealmadrid 发表于 2014-12-10 08:21
lz 第一面的bfs需要优化吗 感觉复杂度很高啊

有的,她后面提示说可以保存中间遍历的路径值,下次遍历就可以略过很多值了
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2014-12-11 01:40:36 | 显示全部楼层
lwbshr 发表于 2014-12-11 01:16
有的,她后面提示说可以保存中间遍历的路径值,下次遍历就可以略过很多值了
.鐣欏璁哄潧-涓浜-涓夊垎鍦
恩恩 理解lz的意思了 那这样time complexity是矩阵面积(m*n)咯?

. visit 1point3acres.com for more.补充内容 (2014-12-11 01:49):
不对 没考虑障碍,感觉还是对每个宝物进行bfs 然后复杂度是宝物数x*(m*n).
回复 支持 反对

使用道具 举报

 楼主| lwbshr 发表于 2014-12-11 01:47:58 | 显示全部楼层
xdrealmadrid 发表于 2014-12-11 01:40
恩恩 理解lz的意思了 那这样time complexity是矩阵面积(m*n)咯?

是总共要遍历m * n个点,但是每个点的遍历最坏也会到m * n
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2014-12-11 01:53:18 | 显示全部楼层
lwbshr 发表于 2014-12-11 01:47
是总共要遍历m * n个点,但是每个点的遍历最坏也会到m * n
. more info on 1point3acres.com
假设矩阵面积(m*n),我的想法是对每个宝物进行一次bfs, 每个cell记录离这个cell的距离,然后最后把每个cell里距离每个宝物的值sum一下,最后求里面最小的sum。复杂度是宝物数x*(m*n). 但实在想不到时间能如何优化。。。
回复 支持 反对

使用道具 举报

 楼主| lwbshr 发表于 2014-12-11 02:06:08 | 显示全部楼层
xdrealmadrid 发表于 2014-12-11 01:53
假设矩阵面积(m*n),我的想法是对每个宝物进行一次bfs, 每个cell记录离这个cell的距离,然后最后把每个c ...
. 1point3acres.com/bbs
你这个方法比我的好,应该是最优了
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2014-12-11 08:27:47 | 显示全部楼层
lz 关于游戏排名那道 如果有积分相同的情况 该怎么搞啊
回复 支持 反对

使用道具 举报

 楼主| lwbshr 发表于 2014-12-11 08:51:19 | 显示全部楼层
xdrealmadrid 发表于 2014-12-11 08:27
lz 关于游戏排名那道 如果有积分相同的情况 该怎么搞啊

噢,这个我也没考虑,他也没提示
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2014-12-11 10:40:06 | 显示全部楼层
lwbshr 发表于 2014-12-11 08:51
噢,这个我也没考虑,他也没提示

那你用啥数据结构的啊 感觉题目都好难啊
回复 支持 反对

使用道具 举报

 楼主| lwbshr 发表于 2014-12-11 12:12:40 | 显示全部楼层
xdrealmadrid 发表于 2014-12-11 10:40 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
那你用啥数据结构的啊 感觉题目都好难啊

对啊,我当时相当于是直接用了个arraylist加一个哈希表,update rank的复杂度还是O(n)。肯定不行,面完之后我想了好久,好像用树可以降到logn
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2014-12-11 12:46:06 | 显示全部楼层
恩恩 我看行 这电面时间短 要求太高了 lz加油哈
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 16:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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