一亩三分地论坛

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

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

11/09 Google Onsite

[复制链接] |试试Instant~ |关注本帖
Nero_hu 发表于 2015-11-20 05:14:06 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

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

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

x
多半黑了,发一个面经造福社会.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1. Flip game (allPossible moves, canWin)
2. Find Camel:
. 鍥磋鎴戜滑@1point 3 acres   Input: "FooBar", "FoBa", "FooBarFoo". 鍥磋鎴戜滑@1point 3 acres
   Pattern : "FBF"
   Output " "FooBarFoo"
3. Run length string encoding.鐣欏璁哄潧-涓浜-涓夊垎鍦
4. Array of String Serialization, and deserialization
5. Top K int in a large stream (This can be done in O(n))




补充内容 (2015-11-20 08:17):
第五题O(N)解法: 2K windows, Quick Select, throw K away.

本帖被以下淘专辑推荐:

queeniejing 发表于 2015-11-20 06:45:19 | 显示全部楼层
谢谢LZ 请问下第五题 O(n) 是怎么做啊
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-20 06:52:46 | 显示全部楼层
同问第五题O(N)解法
回复 支持 反对

使用道具 举报

@南岸的风 发表于 2015-11-20 06:56:29 | 显示全部楼层
楼主没有hr收到消息嘛
回复 支持 反对

使用道具 举报

 楼主| Nero_hu 发表于 2015-11-20 08:14:20 | 显示全部楼层
@南岸的风 发表于 2015-11-20 06:56. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主没有hr收到消息嘛

没有...问了下说这周进HC,感觉GG了
回复 支持 反对

使用道具 举报

 楼主| Nero_hu 发表于 2015-11-20 08:15:29 | 显示全部楼层
第五题O(N)解法: 2K windows, Quick Select, throw K away.
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-20 08:27:45 | 显示全部楼层
楼主能稍微详细讲下O(N)怎么实现的么?
是在这个2k window里用quick select么?这个不是O(k)么?
回复 支持 反对

使用道具 举报

RagingSword 发表于 2015-11-20 08:39:04 | 显示全部楼层
stonezms 发表于 2015-11-20 08:27
楼主能稍微详细讲下O(N)怎么实现的么?. visit 1point3acres.com for more.
是在这个2k window里用quick select么?这个不是O(k)么?

有N/K 个batches, 所以是O(K * N / K) = O(K). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2015-11-20 08:39):
打错了.1point3acres缃
O(K * N / K) = O(N)
. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

 楼主| Nero_hu 发表于 2015-11-20 09:11:24 | 显示全部楼层
RagingSword 发表于 2015-11-20 08:39. From 1point 3acres bbs
有N/K 个batches, 所以是O(K * N / K) = O(K)

补充内容 (2015-11-20 08:39):

正解.....
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-11-20 09:30:58 来自手机 | 显示全部楼层
第五题2k window不行吧,如果去后面k个全部小于前面k个,岂不是都会被去除,然后前面的k个会被移走?
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-20 09:34:33 | 显示全部楼层
RagingSword 发表于 2015-11-20 08:39
有N/K 个batches, 所以是O(K * N / K) = O(K)

补充内容 (2015-11-20 08:39):

谢谢,虽然还是不太懂 额. from: 1point3acres.com/bbs
stream里面每一个新数到了以后,怎么决定去哪一个batch呢?然后每个batch里面怎么用quick select啊?
回复 支持 反对

使用道具 举报

RagingSword 发表于 2015-11-20 09:47:40 | 显示全部楼层
stonezms 发表于 2015-11-20 09:34
谢谢,虽然还是不太懂 额
stream里面每一个新数到了以后,怎么决定去哪一个batch呢?然后每个batch里面 ...

不是一个一个进来,而是一个batch一个batch进来,每个batch的size就是k
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-20 09:52:45 | 显示全部楼层
RagingSword 发表于 2015-11-20 09:47
不是一个一个进来,而是一个batch一个batch进来,每个batch的size就是k

了解,谢了!
回复 支持 反对

使用道具 举报

 楼主| Nero_hu 发表于 2015-11-20 09:52:45 | 显示全部楼层
bobzhang2004 发表于 2015-11-20 09:30
第五题2k window不行吧,如果去后面k个全部小于前面k个,岂不是都会被去除,然后前面的k个会被移走?

你每次select第(total - k)个元素,前面的都remove就好了.
对total = 2K的情况 就是第K个
少于2K就remove前面那些留下K个就好了.
回复 支持 反对

使用道具 举报

yanguango 发表于 2015-11-20 09:58:11 | 显示全部楼层
Nero_hu 发表于 2015-11-20 09:52
你每次select第(total - k)个元素,前面的都remove就好了.
对total = 2K的情况 就是第K个
少于2K就remov ...

是不是 quickselect 的时候需要找出这2k 个数的中位数作为 pivot 来做
回复 支持 反对

使用道具 举报

lightmark 发表于 2015-11-20 10:01:28 | 显示全部楼层
第五题真是有水平。。。
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-11-30 11:49:17 | 显示全部楼层
感觉是维护一个2K length 的空间,保证前K个,然后每次从stream 进来k个,2k个数做一次quickselect,然后把后面那k扔掉。。。
回复 支持 反对

使用道具 举报

姐姐不吃糖 发表于 2015-11-30 12:04:11 | 显示全部楼层
第五题为什么minheap不行?
回复 支持 反对

使用道具 举报

姐姐不吃糖 发表于 2015-11-30 12:12:45 | 显示全部楼层
第三题是什么意思?LZ能再解释一下么?
回复 支持 反对

使用道具 举报

 楼主| Nero_hu 发表于 2015-11-30 23:41:31 | 显示全部楼层
姐姐不吃糖 发表于 2015-11-30 12:12
第三题是什么意思?LZ能再解释一下么?

就是经典的那道压缩string.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 23:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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