一亩三分地论坛

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

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

11/07 google onsite

[复制链接] |试试Instant~ |关注本帖
xuzs9298 发表于 2016-11-12 04:43:18 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 博士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
第一轮:给一个array, 返回下一个 比当前元素大的 离当前元素有多远: 比如 [10,8,6,8,8,11,9],返回[5,4,1,2,1,-1,-1] 第一个10, 下一个比10 大的是11, 距离为5。没有就为 -1. 先让写了naive的 o(n^2). 然后写了 o(n) stack 实现。第二轮: thesis
第三轮: external sort, 让 自定义 读写文件的api, 写了merge k sort list, 没写完, 白板写不下了。. 鍥磋鎴戜滑@1point 3 acres
第四轮: lc 417 没刷过。 给了个 dfs的解法,跟bfs相同 复杂度。. 鍥磋鎴戜滑@1point 3 acres
第五轮: lc 308 没刷过。先说了unmutable 的方法。然后给了个o(n)的amortized 方法。 然后给了个o(logn)update, o(n)query 的递归方法。 让写了简单的伪码, 没时间了。 面完以后发现稍微改下就是both o(logn ^2) 的方法。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


. 鍥磋鎴戜滑@1point 3 acres



评分

2

查看全部评分

本帖被以下淘专辑推荐:

robotwish 发表于 2016-11-12 07:36:29 | 显示全部楼层
楼主第一题,用stack是不是再建个类存一下每个数的index?
回复 支持 反对

使用道具 举报

 楼主| xuzs9298 发表于 2016-11-12 07:44:21 | 显示全部楼层
stack 直接 push index 就可以了
回复 支持 反对

使用道具 举报

 楼主| xuzs9298 发表于 2016-11-12 07:45:18 | 显示全部楼层
robotwish 发表于 2016-11-12 07:36
楼主第一题,用stack是不是再建个类存一下每个数的index?

stack 直接push index,
回复 支持 反对

使用道具 举报

类与对象tju 发表于 2016-11-12 09:19:47 | 显示全部楼层
xuzs9298 发表于 2016-11-12 07:44. From 1point 3acres bbs
stack 直接 push index 就可以了

请问楼主,是从后往前遍历,然后遇到比栈顶大的就push index,遇到小的,就一个个和stack里的比吗
回复 支持 反对

使用道具 举报

 楼主| xuzs9298 发表于 2016-11-13 05:16:49 | 显示全部楼层
类与对象tju 发表于 2016-11-12 09:19.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问楼主,是从后往前遍历,然后遇到比栈顶大的就push index,遇到小的,就一个个和stack里的比吗
. From 1point 3acres bbs
我是从左到右。 如果比栈顶小或等于就push index, 如果比栈顶大, 就一直pop()到小于等于栈顶为止。并且对于每个pop出来的index, 算出结果。
回复 支持 反对

使用道具 举报

jokebill 发表于 2016-11-14 04:49:44 | 显示全部楼层
lc 308那题,immutable的话,initialize O(n) 建Accumulation matrix, 然后query是O(1),S(r1, c1, r2, c2) = S(r2, c2) - S(r1-1, c2) - S(r2, c1-1) + S(r1-1, c1-1)

mutable看大家好像都用binary indexed tree,但是如果一直update A(0, 0)的话,update时间也是O(n)吧?我的想法是,对于update, 存一个update list,是每个update的坐标和变化量,这样变化量对所有坐标右或下的累加值都有效。query的时候考虑所有update,速度是O(k), k是update list的长度。当update list长度大于log(n)的时候重建累加数组,用时O(n), 这样query可以确保O(log(n)), update worst case O(n),但是可以确保worst case最多log(n)次update里才会出现一次
回复 支持 反对

使用道具 举报

pigeyes 发表于 2016-11-14 05:41:01 | 显示全部楼层
lz能简单说一下最后一题的解法吗?哩扣上的解法Binary index tree太没有通用性了 谢谢!. 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

 楼主| xuzs9298 发表于 2016-11-14 09:57:27 | 显示全部楼层
pigeyes 发表于 2016-11-14 05:41
lz能简单说一下最后一题的解法吗?哩扣上的解法Binary index tree太没有通用性了 谢谢!
. From 1point 3acres bbs
其实后来发现我给的解法 好像就是quad tree。
对于quad tree每一个region,存总的sum, 和所有row的 和 所有column 的sum。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
递归过程t(n) = t(n/2) +O(n) 因为只有一个quadrant 需要 recursive call, 其他的可以直接根据region 存的值算出来 所以是o(n)

如果把row的sum 和col的sum 的array 做成segment tree。
就变成t(n) = t(n/2) + O(log n) 就有 (log n ^2 )的solution 了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 11:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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