一亩三分地论坛

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

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

GG的面试。。感觉GG了。。

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

2015(1-3月) 码农类 本科 全职@Google - 猎头 - Onsite |Other

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

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

x
上个月刚弄完on site 还没有消息 估计是废了
就做个好人吧
一天五轮 一轮一题 估计是我写字比较慢吧
1.给你一个set 和一个数字S 然后让你 从set里面找到三个数字之和小于等于S 求一共有几种可能
2. 你有一堆 job 每个job有起始和终止时间,用户,以及需要的内存。问你给你一个用户,求他在所有时间内所占用最多的内存是多少?比如他有两个job重叠各占了1G 那你就要说是2G了
3. 一个matrix 要完成update(x,y,value) 和 sum(x1,y1,x2,y2) 两个function 即 改一个值和求一个长方形区域内的总和. 鍥磋鎴戜滑@1point 3 acres
4. 一个a*b的matrix 一共N个格子 里面含有 1..N 各一个 让你找出最长的连续增长Path
5. 假设有N个球[1..N] 以及N+1个盒子[1..N+1] 然后让你把所有东西归位 即第N个盒子里放第N个求 最后一个盒子就当你的buffer。每一个action必须是把球从A拿到B,swap就算三个Action了(从A拿到空盒子,把B拿到A,把空盒子拿到B) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

4

查看全部评分

本帖被以下淘专辑推荐:

NdrZmansN 发表于 2015-2-7 06:15:24 | 显示全部楼层
请问第三题有什么follow up么?
谢谢,
回复 支持 反对

使用道具 举报

 楼主| tabrisjayson 发表于 2015-2-7 06:18:19 | 显示全部楼层
NdrZmansN 发表于 2015-2-7 06:15
请问第三题有什么follow up么?
谢谢,

第三题 就是有两套解法
一个是update O(1), sum O(n2)
一个是update O(n2), sum O(1)

然后他问我有没有折中的办法
就可以是 update 和sum 都是O(n)
回复 支持 反对

使用道具 举报

lklk1986fa 发表于 2015-2-7 06:28:36 | 显示全部楼层
bless楼主,第三题最优可以做到update lgn  sum lgn, 参考2d segment tree
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2015-2-7 06:36:43 | 显示全部楼层
好难,不愧是谷歌
回复 支持 反对

使用道具 举报

NdrZmansN 发表于 2015-2-7 07:10:21 | 显示全部楼层
tabrisjayson 发表于 2015-2-7 06:18
第三题 就是有两套解法. 鍥磋鎴戜滑@1point 3 acres
一个是update O(1), sum O(n2).鏈枃鍘熷垱鑷1point3acres璁哄潧
一个是update O(n2), sum O(1)

能不能再详细讲讲?
不太明白这几种解法.. visit 1point3acres.com for more.
谢谢,
回复 支持 反对

使用道具 举报

 楼主| tabrisjayson 发表于 2015-2-8 10:56:31 | 显示全部楼层
NdrZmansN 发表于 2015-2-7 07:10
能不能再详细讲讲?
不太明白这几种解法.. from: 1point3acres.com/bbs
谢谢,

确实挺tricky的
首先 update O(1), sum O(n2) 就是最基本的死算
你先想1维的  假设你有一个长度为N的 array, A, 让你算任意两点的求和怎么做
你可以另外造一个长度为N的array B,对于任意B = A[0]+A[1]+...+A,这样让你求x到y的和 你就可以B[y]-B[x]+A[x] 在O1内得到sum的结果。扩展到2维即可
回复 支持 反对

使用道具 举报

TsenAlex 发表于 2015-2-10 10:23:02 | 显示全部楼层
LZ 第四题什么意思能解释一下吗?
回复 支持 反对

使用道具 举报

 楼主| tabrisjayson 发表于 2015-2-11 00:40:27 | 显示全部楼层
TsenAlex 发表于 2015-2-10 10:23
LZ 第四题什么意思能解释一下吗?

1 2 9
3 4 8
5 6 7

在这个情况下 5->6->7->8->9 是最长的一条连续的(每个相差1) 增长的path
回复 支持 反对

使用道具 举报

zuying 发表于 2015-2-11 01:18:11 | 显示全部楼层
第四题有dp解法嘛?
回复 支持 反对

使用道具 举报

clockwise9 发表于 2015-2-11 04:10:01 | 显示全部楼层
今天我电面也面了第一题,先随便写了一个n^2 logn的,结果想用two pointers改成n^2的卡住了……
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-2-11 04:21:10 | 显示全部楼层
lklk1986fa 发表于 2015-2-7 06:28-google 1point3acres
bless楼主,第三题最优可以做到update lgn  sum lgn, 参考2d segment tree

2d 树状数组就行了。 sum O(1).
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-2-11 04:21:38 | 显示全部楼层
第四题又是滑雪题。
回复 支持 反对

使用道具 举报

lklk1986fa 发表于 2015-2-11 05:07:54 | 显示全部楼层
Linzertorte 发表于 2015-2-11 04:21
2d 树状数组就行了。 sum O(1).

求解释Binary indexed tree 如何达到O(1)的,网上查了查好像是log(n)啊,reference http://en.wikipedia.org/wiki/Fenwick_tree
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-2-11 05:45:01 | 显示全部楼层
lklk1986fa 发表于 2015-2-11 05:07
求解释Binary indexed tree 如何达到O(1)的,网上查了查好像是log(n)啊,reference http://en.wikipedia. ...

哦。对。我弄错了。
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-12 02:51:37 | 显示全部楼层

楼主,不应该是1,3,5,6,7,8,9这条path么。。。。
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-12 02:52:47 | 显示全部楼层
Linzertorte 发表于 2015-2-11 04:21
第四题又是滑雪题。

大牛。。。滑雪题??能多透露点么
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-2-12 02:53:56 | 显示全部楼层
yapingchen1990 发表于 2015-2-12 02:52
大牛。。。滑雪题??能多透露点么

http://poj.org/problem?id=1088
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-12 02:58:14 | 显示全部楼层
我问错了。。。其实我想问的是第五题。。抱歉
回复 支持 反对

使用道具 举报

echo33 发表于 2015-2-15 05:10:33 | 显示全部楼层
好喜欢考segment tree的样子...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 09:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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