一亩三分地论坛

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

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

Google onsite

[复制链接] |试试Instant~ |关注本帖
michellnum001 发表于 2016-2-14 06:09:09 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
刚面完google onsite
第一轮,实现iterator,给一个函数a返回boolean, iterator的next函数返回下一个满足函数a的元素。之后问了简历上的一个project,他让我在白板上写写划划给他讲
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二轮,是有一个stock feed会返回股票时间戳和股票价格,然后因为会有错误,相同时间戳会返回多个股票价格(以最后一次接受的股票价格代表那个时间戳的价格),实现 得到股票价格的最大值和最小值还有股票价格的最新值,我用的hashmap和priorityqueue。follow up是如果stock feed出错率很低,如何改进。第二题是一个数组先递增后递减问如何得到peek number,用binary search实现

第三轮实现big Integer的add function,我只是用了一个很简单的char型数组实现的,不过楼主写的代码太长了,bug也有点多,写的也不公整,面完整体觉得这轮面的最不好,面试官其实挺开朗挺好的,一直让我跟他说我的思路,但我能感觉到他觉得我跟他的交流比较少

第四轮是有一堆query<ID, start_time, end_time>,  按照start_time 排序,输出是<id, start/end, time>按照time排序,我最开始说全排,面试官说没有那么多的内存,后来我就改进了一下但还是用了priorityqueue实现,问了时间复杂度,然后问我如果是multithread,每个thread处理的query是不overlap的,问时间复杂度是多少,我最开始没理解,最后也答错了. more info on 1point3acres.com

面试的题目都不难,都有思路,但楼主基本每轮都有bug,特别是第三轮,有些bug是在面试官提示下才改过来的。楼主希望来offer,但感觉会挂掉。准备的时候看了地里面很多面经,很有帮助,希望地里的朋友看到我的面经也能有收获

评分

5

查看全部评分

本帖被以下淘专辑推荐:

jmnjmnjmn 发表于 2016-2-14 06:36:43 | 显示全部楼层
michellnum001 发表于 2016-2-14 06:25
没有需要在某个时间窗内,就是所有的最大值和最小值,我就是用maxheap和minheap做的,我还用了hashmap,因 ...

明白了,不过heap的update好像是O(N),是不是用TreeMap更快一点呢,还有那个follow up出错少的优化是什么思路啊
回复 支持 0 反对 1

使用道具 举报

jmnjmnjmn 发表于 2016-2-14 06:22:27 | 显示全部楼层
股票那题算最大最小值时候是要求某个时间窗口之内吗 比如从当前时刻往前N分钟的max min? 是不是maxheap 跟 minheap分别存max跟min呢,超时或者更新某个时间戳价格的时候update heap?
回复 支持 反对

使用道具 举报

 楼主| michellnum001 发表于 2016-2-14 06:25:37 | 显示全部楼层
没有需要在某个时间窗内,就是所有的最大值和最小值,我就是用maxheap和minheap做的,我还用了hashmap,因为还要返回最新的股票价格
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-14 06:53:15 | 显示全部楼层
第一题就是不断next(),然后满足的就停? 这么简单面了45Min?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-14 06:55:40 | 显示全部楼层
michellnum001 发表于 2016-2-14 06:25
没有需要在某个时间窗内,就是所有的最大值和最小值,我就是用maxheap和minheap做的,我还用了hashmap,因 ...

这些股票价格全都是指一家的股票吗?那hashmap就是一个< timestamp, Double>? 请问怎么返回最新的价格呢?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-14 06:57:11 | 显示全部楼层
请问第四轮”输出是<id, start/end, time>按照time排序“这个time是怎么来的呢?
回复 支持 反对

使用道具 举报

 楼主| michellnum001 发表于 2016-2-14 07:17:42 | 显示全部楼层
bobzhang2004 发表于 2016-2-14 06:57
请问第四轮”输出是按照time排序“这个time是怎么来的呢?
-google 1point3acres
就是query的time啊
回复 支持 反对

使用道具 举报

 楼主| michellnum001 发表于 2016-2-14 07:18:09 | 显示全部楼层
bobzhang2004 发表于 2016-2-14 06:55
这些股票价格全都是指一家的股票吗?那hashmap就是一个< timestamp, Double>? 请问怎么返回最新的价格呢 ...

就是找最大的timestamp就好了
回复 支持 反对

使用道具 举报

 楼主| michellnum001 发表于 2016-2-14 07:18:56 | 显示全部楼层
bobzhang2004 发表于 2016-2-14 06:53. From 1point 3acres bbs
第一题就是不断next(),然后满足的就停? 这么简单面了45Min?

你可以写写试试,是挺简单的,后面问了一个project
回复 支持 反对

使用道具 举报

yjfox 发表于 2016-2-14 08:19:23 | 显示全部楼层
bobzhang2004 发表于 2016-2-14 06:53
第一题就是不断next(),然后满足的就停? 这么简单面了45Min?

iterator of iterator 变种
没有很难但也没有easy,你说的不断next()听起来有问题. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

简单问一个,java的iterator的next() call一次就过去了,怎么返回满足条件的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

panlong222 发表于 2016-2-14 11:03:59 | 显示全部楼层
楼主 第四轮 multithread的复杂度 正确答案是神马?
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-14 11:09:16 | 显示全部楼层
lz, 第四轮可以给些输入输出的例子吗?. 鍥磋鎴戜滑@1point 3 acres

输出是按照起始时间还是终止时间, 同一个id可以有多个entries吗?
回复 支持 反对

使用道具 举报

comicrudy 发表于 2016-2-14 12:19:19 | 显示全部楼层
第四轮问的应该是外排和k路归并吧?
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-2-14 12:35:15 | 显示全部楼层
第三轮是不是就是leetcode的add two numbers?
回复 支持 反对

使用道具 举报

 楼主| michellnum001 发表于 2016-2-14 13:46:32 | 显示全部楼层
qiuxuxing007 发表于 2016-2-14 12:35
第三轮是不是就是leetcode的add two numbers?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我差不多就是这么写的
回复 支持 反对

使用道具 举报

 楼主| michellnum001 发表于 2016-2-14 13:47:00 | 显示全部楼层
comicrudy 发表于 2016-2-14 12:19
第四轮问的应该是外排和k路归并吧?
. Waral 鍗氬鏈夋洿澶氭枃绔,
你是说多线程那部分吗
回复 支持 反对

使用道具 举报

panlong222 发表于 2016-2-15 00:18:46 | 显示全部楼层
michellnum001 发表于 2016-2-14 13:47
你是说多线程那部分吗

楼主求这个的正确答案是啥?
回复 支持 反对

使用道具 举报

loveonts 发表于 2016-2-15 00:37:17 | 显示全部楼层
offer有没有不好说 但估计residency机会很大
回复 支持 反对

使用道具 举报

loveonts 发表于 2016-2-15 00:59:54 | 显示全部楼层
jmnjmnjmn 发表于 2016-2-14 06:22
股票那题算最大最小值时候是要求某个时间窗口之内吗 比如从当前时刻往前N分钟的max min? 是不是maxheap 跟 ...

很想知道 怎么update一个heap 貌似heap只能访问最值
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 19:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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