一亩三分地论坛

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

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

热腾腾的Google面经

[复制链接] |试试Instant~ |关注本帖
hychin 发表于 2016-6-28 12:29:37 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Google - 内推 - HR筛选 |Other在职跳槽

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

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

x
去他大爷的保密协议,趁着记忆还在写一个回馈大家
面的什么team就不说了,免得被查出来


复习了这么久,看了大家的面经受益良多,就决定一定自己面完久上来发个面经。

第一轮 给一个巨大的二维平面,要求写两个函数,
第一个是add value(x, y, value) 加一个值到坐标x y 上,
第二个是get sum(x1, y1, x2, y2)  要求的是这两个点决定的一个四边形之内的所有值的和
特殊要求:因为是无限大的二维平面,所以不能用二维数组来存值,因为有内存的要求

第二轮 leetcode原题 unique abbreviation

第三轮 fizzbuzz 游戏 和 实现 itoa,还有一个虚函数的题. more info on 1point3acres.com

第四轮 设计一个内存分块管理的办法

第五轮  实现一个observer观察者模式, 还有C语言的基本知识. From 1point 3acres bbs

评分

3

查看全部评分

本帖被以下淘专辑推荐:

Chi2829 发表于 2016-6-29 05:37:13 | 显示全部楼层
请问楼主第一题用什么方法呢?我只能想到O(n)的方法了,n是有value的坐标的数目。谢谢!
回复 支持 反对

使用道具 举报

chenzhan171 发表于 2016-6-29 07:17:53 | 显示全部楼层
第一题用ArrayList + BIT ? 这样可以实现Add和get都是 O(logn)。
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-29 09:44:26 | 显示全部楼层
chenzhan171 发表于 2016-6-29 07:17
第一题用ArrayList + BIT ? 这样可以实现Add和get都是 O(logn)。

fenwick树有范围的吧....
第一题我觉得Segment Tree 2D吧...不过代码写的时候没fenwick好写.. 但理论上来说fenwick能做的 线段树都能
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-6-29 10:19:06 | 显示全部楼层
第一题可以用treemap
1) add(x, y, value)  --> treemap.put(x * col + y, value)
2)   get sum(x1, y1, x2, y2) --> treemap.subMap(x1 * col + y1, true, x2 * col + y2) 然后遍历submap累加下结果

add是logn,getSum应该是这个range里实际存储了多少个值*logn
觉得这个题和稀疏矩阵乘法有点类似,原则就是不储存空值. Waral 鍗氬鏈夋洿澶氭枃绔,
欢迎讨论~

补充内容 (2016-6-29 10:19):. more info on 1point3acres.com
treemap.subMap(x1 * col + y1, true, x2 * col + y2, true)打漏了一个参数
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-29 10:51:15 | 显示全部楼层
mengmeng88717 发表于 2016-6-29 10:19
第一题可以用treemap
1) add(x, y, value)  --> treemap.put(x * col + y, value). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2)   get sum(x1, y1 ...

请问, 不知道col的情况下...怎么做...第一题不是说没边界么..
回复 支持 反对

使用道具 举报

pustar 发表于 2016-6-29 10:52:46 | 显示全部楼层
第一题咋解啊?
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-6-29 11:24:33 | 显示全部楼层
readman 发表于 2016-6-29 10:51
请问, 不知道col的情况下...怎么做...第一题不是说没边界么..

我的理解是平面很大而有内存限制,请楼主澄清下知不知道col?
回复 支持 反对

使用道具 举报

 楼主| hychin 发表于 2016-6-29 11:48:25 | 显示全部楼层
mengmeng88717 发表于 2016-6-29 11:24
我的理解是平面很大而有内存限制,请楼主澄清下知不知道col?

不知道col的边界的,我画个原图给你看就明白了. 1point3acres.com/bbs

一个这样子的平面
------------------------------------------------------------》 unlimit bound
|
-google 1point3acres |
|
|
|
|
|
|. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
|
回复 支持 反对

使用道具 举报

 楼主| hychin 发表于 2016-6-29 11:50:10 | 显示全部楼层
mengmeng88717 发表于 2016-6-29 11:24
我的理解是平面很大而有内存限制,请楼主澄清下知不知道col?

不知道col的边界的,我画个原图给你看就明白了
.鏈枃鍘熷垱鑷1point3acres璁哄潧
一个这样子的平面
------------------------------------------------------------》 unlimit bound
|
|
|.鐣欏璁哄潧-涓浜-涓夊垎鍦
|
|
|
|
|
\|/
unlimit bound
回复 支持 反对

使用道具 举报

 楼主| hychin 发表于 2016-6-29 11:55:32 | 显示全部楼层
Chi2829 发表于 2016-6-29 05:37
请问楼主第一题用什么方法呢?我只能想到O(n)的方法了,n是有value的坐标的数目。谢谢!

我跟你解法一样,弄一个list串起来暴力解法,省内存,update快,但是每次求和很慢,需要一个点一个点check,最后说了一个每个列存一个list的解法,可能稍微改进了点速度,但是还不是他想要的解法 估计挂了
回复 支持 反对

使用道具 举报

 楼主| hychin 发表于 2016-6-29 11:58:47 | 显示全部楼层
我后来想了想,他可能是想要那个每一个列存一个set的那种解法,set里面自动按照x来排序,要求某个范围的话,直接找指定范围内的set然后做二分查找找出来边界,然后加起来的那种解法
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-6-29 11:59:12 | 显示全部楼层
hychin 发表于 2016-6-29 11:50
不知道col的边界的,我画个原图给你看就明白了

一个这样子的平面
. 1point3acres.com/bbs
TreeMap<Integer, TreeMap<Integer, Integer>>这样呢?
外层key是x,内层key是y
回复 支持 反对

使用道具 举报

 楼主| hychin 发表于 2016-6-29 12:20:51 | 显示全部楼层
mengmeng88717 发表于 2016-6-29 11:59
TreeMap这样呢?
外层key是x,内层key是y

我觉得差不多,这应该是他expected的解法

换成C++就是用
map<int, map<int, int>> 外层k是x,内层k是y,最里层是value 加的话直接index到那个entry加  求和的话两层循环外层从mp.lowerbound(x1) 遍历到mp.upperbound(x2), 内层 从mp.lowerbound(y1) 遍历到 mp.lowerbound(y2)累加起来,还是学艺不精啊。。以后有机会再战了
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-6-30 09:43:11 | 显示全部楼层
hychin 发表于 2016-6-29 12:20
我觉得差不多,这应该是他expected的解法
. from: 1point3acres.com/bbs
换成C++就是用

虚函数的题是什么意思?
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-6-30 09:48:42 | 显示全部楼层
hychin 发表于 2016-6-29 12:20
我觉得差不多,这应该是他expected的解法. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

换成C++就是用

. more info on 1point3acres.com楼主内存分块管理那个是怎么答的啊
回复 支持 反对

使用道具 举报

boerwa 发表于 2016-7-6 14:11:51 | 显示全部楼层
第一个国内lbs应用应该遇到很多,map套map应该可以搞定
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-6 15:47:23 | 显示全部楼层
第一题切成一个个小正方形行不行?按照方块建索引。每个方块内,除了存坐标,value外,还缓存一个这个方块内所有点的value之和。
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-6 15:54:39 | 显示全部楼层
哦,其实是稀疏矩阵,还是map好
http://stackoverflow.com/questions/4306/what-is-the-best-way-to-create-a-sparse-array-in-c
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 10:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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