求问有什么站立式办公桌推荐?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4738|回复: 21
收起左侧

热腾腾的Google面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
hychin 发表于 2016-6-28 12:29:37 | 显示全部楼层 |阅读模式
  此人我要顶:
 
78% (14) 【我投】
  此人我要踩:
 
22% (5) 【我投】

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

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

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

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


复习了这么久,看了大家的面经受益良多,就决定一定自己面完久上来发个面经。
. 留学申请论坛-一亩三分地
第一轮 给一个巨大的二维平面,要求写两个函数,
第一个是add value(x, y, value) 加一个值到坐标x y 上,
第二个是get sum(x1, y1, x2, y2)  要求的是这两个点决定的一个四边形之内的所有值的和-google 1point3acres
特殊要求:因为是无限大的二维平面,所以不能用二维数组来存值,因为有内存的要求
来源一亩.三分地论坛.
第二轮 leetcode原题 unique abbreviation. visit 1point3acres for more.

第三轮 fizzbuzz 游戏 和 实现 itoa,还有一个虚函数的题

第四轮 设计一个内存分块管理的办法. From 1point 3acres bbs

第五轮  实现一个observer观察者模式, 还有C语言的基本知识

评分

参与人数 4大米 +44 收起 理由
leetcod_ + 3 很有用的信息!
zzwcsong + 30
vancexu + 10 感谢分享!
YJM1024 + 1 感谢分享!

查看全部评分


上一篇:求一个Hulu的60分钟OA面经
下一篇:有人收到 Vancouver Interview Event 的吗?

本帖被以下淘专辑推荐:

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

使用道具 举报

我的人缘0
chenzhan171 发表于 2016-6-29 07:17:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题用ArrayList + BIT ? 这样可以实现Add和get都是 O(logn)。
回复 支持 反对

使用道具 举报

我的人缘0
readman 发表于 2016-6-29 09:44:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
chenzhan171 发表于 2016-6-29 07:17
第一题用ArrayList + BIT ? 这样可以实现Add和get都是 O(logn)。

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

使用道具 举报

我的人缘0
mengmeng88717 发表于 2016-6-29 10:19:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题可以用treemap .本文原创自1point3acres论坛
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
觉得这个题和稀疏矩阵乘法有点类似,原则就是不储存空值
欢迎讨论~

补充内容 (2016-6-29 10:19):.本文原创自1point3acres论坛
treemap.subMap(x1 * col + y1, true, x2 * col + y2, true)打漏了一个参数
回复 支持 反对

使用道具 举报

我的人缘0
readman 发表于 2016-6-29 10:51:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
mengmeng88717 发表于 2016-6-29 10:19. more info on 1point3acres
第一题可以用treemap
1) add(x, y, value)  --> treemap.put(x * col + y, value). Waral 博客有更多文章,
2)   get sum(x1, y1 ...

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

使用道具 举报

我的人缘0
pustar 发表于 2016-6-29 10:52:46 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题咋解啊?
回复 支持 反对

使用道具 举报

我的人缘0
mengmeng88717 发表于 2016-6-29 11:24:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
readman 发表于 2016-6-29 10:51
请问, 不知道col的情况下...怎么做...第一题不是说没边界么..

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

使用道具 举报

我的人缘0
 楼主| hychin 发表于 2016-6-29 11:48:25 | 显示全部楼层
  此人我要顶:
 
78% (14) 【我投】
  此人我要踩:
 
22% (5) 【我投】
mengmeng88717 发表于 2016-6-29 11:24
我的理解是平面很大而有内存限制,请楼主澄清下知不知道col?

不知道col的边界的,我画个原图给你看就明白了

一个这样子的平面
------------------------------------------------------------》 unlimit bound
|
|
|
|
|
|. more info on 1point3acres
|
|
|
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| hychin 发表于 2016-6-29 11:50:10 | 显示全部楼层
  此人我要顶:
 
78% (14) 【我投】
  此人我要踩:
 
22% (5) 【我投】
mengmeng88717 发表于 2016-6-29 11:24
我的理解是平面很大而有内存限制,请楼主澄清下知不知道col?

不知道col的边界的,我画个原图给你看就明白了

一个这样子的平面
------------------------------------------------------------》 unlimit bound
|
|
|
|
|
|
|
|
\|/.留学论坛-一亩-三分地
unlimit bound
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| hychin 发表于 2016-6-29 11:55:32 | 显示全部楼层
  此人我要顶:
 
78% (14) 【我投】
  此人我要踩:
 
22% (5) 【我投】
Chi2829 发表于 2016-6-29 05:37
请问楼主第一题用什么方法呢?我只能想到O(n)的方法了,n是有value的坐标的数目。谢谢!

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

使用道具 举报

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

使用道具 举报

我的人缘0
mengmeng88717 发表于 2016-6-29 11:59:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hychin 发表于 2016-6-29 11:50
不知道col的边界的,我画个原图给你看就明白了

一个这样子的平面

TreeMap<Integer, TreeMap<Integer, Integer>>这样呢?
外层key是x,内层key是y
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| hychin 发表于 2016-6-29 12:20:51 | 显示全部楼层
  此人我要顶:
 
78% (14) 【我投】
  此人我要踩:
 
22% (5) 【我投】
mengmeng88717 发表于 2016-6-29 11:59
TreeMap这样呢?. 1point3acres
外层key是x,内层key是y
.本文原创自1point3acres论坛
我觉得差不多,这应该是他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)累加起来,还是学艺不精啊。。以后有机会再战了
回复 支持 反对

使用道具 举报

我的人缘0
mengmeng88717 发表于 2016-6-30 09:43:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hychin 发表于 2016-6-29 12:20
我觉得差不多,这应该是他expected的解法

换成C++就是用

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

使用道具 举报

我的人缘0
mengmeng88717 发表于 2016-6-30 09:48:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hychin 发表于 2016-6-29 12:20. 一亩-三分-地,独家发布
我觉得差不多,这应该是他expected的解法

换成C++就是用

楼主内存分块管理那个是怎么答的啊
回复 支持 反对

使用道具 举报

我的人缘0
boerwa 发表于 2016-7-6 14:11:51 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一个国内lbs应用应该遇到很多,map套map应该可以搞定
回复 支持 反对

使用道具 举报

我的人缘0
adrian_yang84 发表于 2016-7-6 15:47:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题切成一个个小正方形行不行?按照方块建索引。每个方块内,除了存坐标,value外,还缓存一个这个方块内所有点的value之和。
回复 支持 反对

使用道具 举报

我的人缘0
adrian_yang84 发表于 2016-7-6 15:54:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
哦,其实是稀疏矩阵,还是map好
http://stackoverflow.com/questions/4306/what-is-the-best-way-to-create-a-sparse-array-in-c
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-18 12:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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