一亩三分地论坛

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

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
huai10 发表于 2016-3-11 11:13:58 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
Range maximum query一开始扯了20分钟楼主做过得project,问了一下最challenging的part.
然后直接 就是range maximum query, 给一个array, 求[start,end]中的最大。
反正他就一直要求优化,写了三种方法(从最简单的开始)之后,楼主无能为力了,然后就谈谈time和space。
我看wiki有O(1)time, O(n)space的,但是表示不懂。
. From 1point 3acres bbs
-google 1point3acres

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
Fustang 发表于 2016-3-15 00:17:04 | 显示全部楼层
aneY1Aip 发表于 2016-3-14 17:33. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
O(1)时间的算法在哪里?

提前store query用数组/map的都是O(1)时间, 相应的space则有简单的O(n^2)和复杂一些的O(nlogn)。
segment tree 是O(logn) time + O(n) space. from: 1point3acres.com/bbs

难的是O(1) time + O(n) space. 好像得用上面有人说的RMQ->LCA->reduced RMQ, 没精力研究了。感兴趣可以看 https://courses.csail.mit.edu/6.851/spring12/lectures/L15.html
回复 支持 1 反对 0

使用道具 举报

Sendoh2015 发表于 2016-3-11 11:20:12 | 显示全部楼层
谢谢楼主的面经
回复 支持 反对

使用道具 举报

AIPointH 发表于 2016-3-11 11:46:12 | 显示全部楼层
O(1) 的话应该不包括预处理 把RMQ转成LCA再变成Restricted RMQ 可以实现
回复 支持 反对

使用道具 举报

say543 发表于 2016-3-11 15:53:00 | 显示全部楼层
是leetcode的range sum query吗?
回复 支持 反对

使用道具 举报

 楼主| huai10 发表于 2016-3-11 16:04:34 | 显示全部楼层
say543 发表于 2016-3-11 15:53
是leetcode的range sum query吗?
-google 1point3acres
类似,但求最值,和sum的性质不一样
回复 支持 反对

使用道具 举报

machen982003 发表于 2016-3-13 03:16:43 | 显示全部楼层
huai10 发表于 2016-3-11 16:04. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
类似,但求最值,和sum的性质不一样
.1point3acres缃
楼主优化之后的时间复杂度是多少呢?  
回复 支持 反对

使用道具 举报

say543 发表于 2016-3-13 14:48:12 | 显示全部楼层
除了brute force 和segment tree, LZ 有别的好办法吗?
回复 支持 反对

使用道具 举报

 楼主| huai10 发表于 2016-3-14 11:51:49 | 显示全部楼层
say543 发表于 2016-3-13 14:48
除了brute force 和segment tree, LZ 有别的好办法吗?

我一上来就说用naive, 然后又写了用2-D map 记, 最后用segment tree, 然后我又和他说如果我们在一个node里面记录最大到kth 最大的 index, 其实就是从1-D 到2-D的过程。
回复 支持 反对

使用道具 举报

 楼主| huai10 发表于 2016-3-14 11:53:05 | 显示全部楼层
machen982003 发表于 2016-3-13 03:16
楼主优化之后的时间复杂度是多少呢?

O(n) space, O(lgn)time吧
回复 支持 反对

使用道具 举报

aneY1Aip 发表于 2016-3-14 17:33:43 | 显示全部楼层
O(1)时间的算法在哪里?
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-6 04:06:15 | 显示全部楼层
都写出三种方法应该也可以过了吧 楼主有消息了吗?
回复 支持 反对

使用道具 举报

 楼主| huai10 发表于 2016-4-6 12:03:14 | 显示全部楼层
Alice0701 发表于 2016-4-6 04:06. 鍥磋鎴戜滑@1point 3 acres
都写出三种方法应该也可以过了吧 楼主有消息了吗?
.1point3acres缃
没有过,再接再厉了喽
回复 支持 反对

使用道具 举报

woshiee123 发表于 2016-4-7 09:37:54 | 显示全部楼层
请问下  这个array是不断变化的么  要不然就是简单的一个array里面找最大的了么 ?
回复 支持 反对

使用道具 举报

 楼主| huai10 发表于 2016-4-7 09:43:53 | 显示全部楼层
woshiee123 发表于 2016-4-7 09:37. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问下  这个array是不断变化的么  要不然就是简单的一个array里面找最大的了么 ?

不变的,给你一个range 里面找,需要注意细节以及trade off
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-26 01:46:07 | 显示全部楼层
写了三种方法都没过,这题到底想要哪种解法。。。
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-19 03:34:27 | 显示全部楼层
topcoder上有一个教程 有一种方法叫 Sparse Table 可以用O(1)的时间完成每次查询
. more info on 1point3acres.com
https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Range_Minimum_Query_(RMQ)

补充内容 (2016-6-19 03:56):
不过这个是space O(nlogn)的
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-19 04:01:05 | 显示全部楼层
Fustang 发表于 2016-3-15 00:17.鐣欏璁哄潧-涓浜-涓夊垎鍦
提前store query用数组/map的都是O(1)时间, 相应的space则有简单的O(n^2)和复杂一些的O(nlogn)。
segme ...

感谢分享!MIT这个高等数据结构 真是 相见恨晚啊!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 00:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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