一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2675|回复: 18
收起左侧

10/14 Google onsite 面经

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

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other

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

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

x
onsite 4轮, 在google总部mountain view 面的
一轮:
tourament question:  input is players like(A,B,C,D), print total rounds[[(A, B), (C, D)], [(A, C), (B, D)], [(A, D), (B, C)]]
recursion 做的
二轮:
tic-tac-toe: 给一个board,以current state判断是o 赢, x 赢, 还是没人赢。follow up每次只能取一行的信息,每次只能存储O(2N+K)的数据
简单的dp
三轮:
1. color schema:"#c1a2b3”类型的css coloe schema,要求转化成类似"#ccaabb"这样三组相同字母的pattern, “#cba” 可以代表“#ccbbaa”,最后输出颜色最相近三个字母的color schema
2. 给三个API, Register(phone #), GetUnused(), isUnused(phone #), 设计一个数据结构可以有效率的调用三个API。Register先check sUnused(phone #),看phone num在不在used num里面,如果在,调用GetUnused(),将生成的num放进used num的结构里;如果不在,直接放进used num里. from: 1point3acres.com/bbs
四轮:
1. 给个board,有且仅有一片连续的1,其他位置是0,找一个最小的box(rectangular)将1全部装进去。用BFS解决
2. 给一个list和k(number)。找一个区域k,使得这个区域里k的最大值和最小值的差值最大,返回这个值。用heap或priority queue做dp。

积分~~~~

评分

12

查看全部评分

本帖被以下淘专辑推荐:

ffcc 发表于 2014-10-18 00:52:59 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
感谢分享,bless
回复 支持 反对

使用道具 举报

renwo 发表于 2014-10-18 02:02:22 | 显示全部楼层
关注一亩三分地微博:
Warald
Bless, 有结果了吗
回复 支持 反对

使用道具 举报

 楼主| CrackerCracked 发表于 2014-10-18 02:06:14 | 显示全部楼层
ffcc 发表于 2014-10-18 00:53. From 1point 3acres bbs
感谢分享,bless

亲,14号面的~当然没有啦
回复 支持 反对

使用道具 举报

traceroute_su 发表于 2014-10-18 03:56:12 来自手机 | 显示全部楼层
嘿嘿 lz 我都感觉遇到的面试官都是一个 额 目测lz offer快得手了 强大bless!
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

xiaozhubudao 发表于 2014-10-18 05:49:42 | 显示全部楼层
lz面的是new grad吗?谢谢分享
回复 支持 反对

使用道具 举报

kuyen 发表于 2014-10-18 12:07:19 | 显示全部楼层
楼主四轮那个k是什么意思?
回复 支持 反对

使用道具 举报

whodewho 发表于 2014-10-18 17:21:54 | 显示全部楼层
bless, hi, 谢谢!四轮第一个:这个rectangular不一定是要“垂直摆放”的是吗,可能是斜的喽,请问下BFS的起点是哪儿? 四轮第二个:k是个滑动的窗口长度是吗,能给下dp的公式吗,谢谢?
回复 支持 反对

使用道具 举报

iorisli 发表于 2014-10-20 11:11:52 | 显示全部楼层
同求四轮第二题的解法~~~!!!
回复 支持 反对

使用道具 举报

zhangshiying 发表于 2014-10-20 13:20:52 | 显示全部楼层
可以再详细解释一下三轮第一题吗?没太理解。谢谢!
回复 支持 反对

使用道具 举报

还来得及吗 发表于 2014-10-21 11:38:49 | 显示全部楼层
LZ第四轮第二题可以用Deque吧?复杂度O(N)比heap好点
回复 支持 反对

使用道具 举报

kuyen 发表于 2014-10-21 12:50:23 | 显示全部楼层
还来得及吗 发表于 2014-10-21 11:38. 1point3acres.com/bbs
LZ第四轮第二题可以用Deque吧?复杂度O(N)比heap好点

我觉得楼主的方法可能已经是最好的了。你用deque的话,如果pop掉当前范围唯一的最小数的话,你怎么确定下一个最小数?
回复 支持 反对

使用道具 举报

还来得及吗 发表于 2014-10-21 23:38:43 | 显示全部楼层
kuyen 发表于 2014-10-21 12:50
我觉得楼主的方法可能已经是最好的了。你用deque的话,如果pop掉当前范围唯一的最小数的话,你怎么确定下 ...

我想的用是两个deque,一个存最大,一个存最小,每次求diff然后和max比较,应该是O(N)吧?
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2014-10-21 23:50:25 | 显示全部楼层
还来得及吗 发表于 2014-10-21 23:38
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷我想的用是两个deque,一个存最大,一个存最小,每次求diff然后和max比较,应该是O(N)吧?

赞,这确实是O(N)的方法. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
维护2个单调队列,每次尝试更新头尾,取出两个队列的头,相减后与max比较即可。
回复 支持 反对

使用道具 举报

可乐杀手 发表于 2014-10-22 00:57:46 | 显示全部楼层
第一题是什么思路啊
回复 支持 反对

使用道具 举报

kuyen 发表于 2014-10-22 01:22:08 | 显示全部楼层
还来得及吗 发表于 2014-10-21 23:38.1point3acres缃
我想的用是两个deque,一个存最大,一个存最小,每次求diff然后和max比较,应该是O(N)吧?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
可以说的再具体点吗?我在想这个方法可以处理重复数字吗?
回复 支持 反对

使用道具 举报

还来得及吗 发表于 2014-10-22 08:01:15 | 显示全部楼层
kuyen 发表于 2014-10-22 01:22
可以说的再具体点吗?我在想这个方法可以处理重复数字吗?

http://leetcode.com/2011/01/sliding-window-maximum.html
重复是可以的吧。。感觉这个问题就是sliding window max的变型,不过是用两个分别记录最大最小。
回复 支持 反对

使用道具 举报

kuyen 发表于 2014-10-22 14:31:20 | 显示全部楼层
还来得及吗 发表于 2014-10-22 08:01. 1point 3acres 璁哄潧
http://leetcode.com/2011/01/sliding-window-maximum.html
重复是可以的吧。。感觉这个问题就是sliding ...
. From 1point 3acres bbs
谢谢啊。解释的很清楚
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-4-23 23:46:13 | 显示全部楼层
第二轮的题目是什么意思 没太懂。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-26 00:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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