一亩三分地论坛

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

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

西雅图 狗狗 onsite

[复制链接] |试试Instant~ |关注本帖
febman 发表于 2016-5-2 02:56:40 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
回报地里:西雅图 狗狗 onsite 五轮:1. research 讨论, 然后游戏设计,在一个矩阵里放各种形状的水管,然后要求从走下角流入的水最后能流出右上角,如果水流入任何空的小方块(该方块没有水管,相当于漏了),或者不能流出右上角,则失败,返回boolean, 是否能成功。想法是用一个水管就用一个map<流入口位置,流出口位置>, 每一个小方块都是一个map,然后就开始模拟水流,如果到了右上角就成功。
2. 一个array,先存有even的number, 然后存有odd 的number, 如果找到第一个odd 的number:binary search; 然后如果不知道这个array 的长度,但是如果访问boundary 外的位置,会给一个提醒(就是表明以及出界了),如何找到第一个odd number, 还是binary search, 只是一开始随便设一个Integer.MAX_VALUE, 然后两倍两倍的扩展到第一个界外元素,在开始binary search
3. 吃饭,同校的美国人
4. zigzag iterator, 然后是一个关网上买东西推荐,pair<商品1, 商品2>, 当用户购买新的组合,update, 然后给找出前k个最火的组合:minheap;然后如果数据太大怎么办:把mapreduce 讲一下
5. longest increasing path in tree, follow up: 如何返回那个最长的path:global max 和 globa path,找到长的就更新.鏈枃鍘熷垱鑷1point3acres璁哄潧
6. moving window average 和 mixing window median:minheap和maxheap. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

求offer!

评分

2

查看全部评分

edcent 发表于 2016-5-2 03:47:30 | 显示全部楼层
楼主第六轮的题能具体讲一下嘛?谢谢!
回复 支持 反对

使用道具 举报

 楼主| febman 发表于 2016-5-2 04:01:26 | 显示全部楼层
moving window average: 就是leetcode 的原题
然后moving window median, 就是之前用两个heap 找data stream 的median 问题,一个maxheap, 一个minheap,刚好把数据分成大,小两组,然后median就是两heap中其中一个pop,或者sum/2
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-5-2 04:19:01 | 显示全部楼层
google 在西雅图有办公室吗?
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-5-2 04:19:57 | 显示全部楼层
3. 吃饭,同校的美国人 吃饭 是面试考察范围内吗?
回复 支持 反对

使用道具 举报

 楼主| febman 发表于 2016-5-2 04:22:53 | 显示全部楼层
对的,西雅图也有狗狗campus, 吃饭就是随便聊聊,理论上不计入任何考核
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-5-2 05:32:44 | 显示全部楼层
关于第四轮第二题 我想问一下 update的时间复杂度是多少呀 我之前一直想在这个问题 但是是没有很好的结果 如果用heap 删掉一个元素 然后再填入  时间复杂度O(n).如果知道是哪个元素 可以做到log n 的更新 但是僬侥直接做heap了
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-5-2 07:29:22 | 显示全部楼层
febman 发表于 2016-5-2 04:01
moving window average: 就是leetcode 的原题. more info on 1point3acres.com
然后moving window median, 就是之前用两个heap 找data str ...

那你是怎么从heap中删除已经跑出window的元素的?
回复 支持 反对

使用道具 举报

tbu 发表于 2016-5-2 07:49:10 | 显示全部楼层
求问狗狗西雅图的食堂也是免费的吗?
咦,好像关注的点不太一样。。。。
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-2 10:55:09 | 显示全部楼层
麻烦楼主说说第四题具体怎么回事可以吗?
pair<商品1, 商品2>, 当用户购买新的组合,update
具体在做什么

谢谢楼主!
回复 支持 反对

使用道具 举报

 楼主| febman 发表于 2016-5-3 09:01:49 | 显示全部楼层
陈润鹏 发表于 2016-5-2 05:32
关于第四轮第二题 我想问一下 update的时间复杂度是多少呀 我之前一直想在这个问题 但是是没有很好的结果  ...

我就用了java自带的heap.remove 的函数,然后他问什么复杂度,我说logN吧,worstcase N. 后来觉得是不是用map<Integer, Heapnode>把heap的api增加一个remove的O(1) 的操作,不过应该不是他想要的吧。
回复 支持 反对

使用道具 举报

 楼主| febman 发表于 2016-5-3 09:02:17 | 显示全部楼层
duduhaha 发表于 2016-5-2 07:29
那你是怎么从heap中删除已经跑出window的元素的?

我是直接用java里面的heap.remove(Object c)
回复 支持 反对

使用道具 举报

 楼主| febman 发表于 2016-5-3 09:02:46 | 显示全部楼层
tbu 发表于 2016-5-2 07:49.1point3acres缃
求问狗狗西雅图的食堂也是免费的吗?
咦,好像关注的点不太一样。。。。

应该是吧,反正我没付钱,哈哈
回复 支持 反对

使用道具 举报

 楼主| febman 发表于 2016-5-3 09:04:29 | 显示全部楼层
tcomein2009 发表于 2016-5-2 10:55
麻烦楼主说说第四题具体怎么回事可以吗?
pair, 当用户购买新的组合,update. 1point3acres.com/bbs
具体在做什么

就是如果你买了A,又买了B, 那么就是《A,B》这个pair在系统里的count+1, 意思大概就是这个组合变得更流行了,然后重新update 前K个最流行的组合
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-5-3 10:39:14 | 显示全部楼层
febman 发表于 2016-5-3 09:01
我就用了java自带的heap.remove 的函数,然后他问什么复杂度,我说logN吧,worstcase N. 后来觉得是不是 ...

自带的是n,如果是要优化remove的话 就要自己写heap了 很麻烦……也只能优化到logn
回复 支持 反对

使用道具 举报

menderr 发表于 2016-5-3 23:00:53 | 显示全部楼层
问下楼主是new graduate吗?还是工作经验转? google seattle office  具体做那几块呢? 因为我家在西雅图,如果想留在这的话,投简历的时候跟recruiter说,专门面西雅图?
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-5-3 23:28:26 | 显示全部楼层
menderr 发表于 2016-5-3 23:00. Waral 鍗氬鏈夋洿澶氭枃绔,
问下楼主是new graduate吗?还是工作经验转? google seattle office  具体做那几块呢? 因为我家在西雅图 ...

会让你填表的
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-5-8 06:39:18 | 显示全部楼层
感觉第六题的median如何用了heap自带的remove,还不如用最原始的方法求中位数了。。不知道楼主怎么看
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 23:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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