西雅图 狗狗 onsite

回报地里：西雅图 狗狗 onsite 五轮：1. research 讨论， 然后游戏设计，在一个矩阵里放各种形状的水管，然后要求从走下角流入的水最后能流出右上角，如果水流入任何空的小方块（该方块没有水管，相当于漏了），或者不能流出右上角，则失败，返回boolean， 是否能成功。想法是用一个水管就用一个map<流入口

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ath：global max 和 globa path，找到长的就更新
6. moving window average 和 mixing window median：minheap和maxheap

求offer!

陈润鹏 发表于 2016-5-2 05:32
关于第四轮第二题 我想问一下 update的时间复杂度是多少呀 我之前一直想在这个问题 但是是没有很好的结果  ...

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

tcomein2009 发表于 2016-5-2 10:55
麻烦楼主说说第四题具体怎么回事可以吗？
pair， 当用户购买新的组合，update
具体在做什么

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

关于第四轮第二题 我想问一下 update的时间复杂度是多少呀 我之前一直想在这个问题 但是是没有很好的结果 如果用heap 删掉一个元素 然后再填入  时间复杂度O（n）.如果知道是哪个元素 可以做到log n 的更新 但是僬侥直接做heap了

楼主第六轮的题能具体讲一下嘛？谢谢！

moving window average: 就是leetcode 的原题
然后moving window median， 就是之前用两个heap 找data stream 的median 问题，一个maxheap， 一个minheap，刚好把数据分成大，小两组，然后median就是两heap中其中一个pop，或者sum/2

google 在西雅图有办公室吗？

3. 吃饭，同校的美国人 吃饭 是面试考察范围内吗？

对的，西雅图也有狗狗campus， 吃饭就是随便聊聊，理论上不计入任何考核

febman 发表于 2016-5-2 04:01
moving window average: 就是leetcode 的原题
然后moving window median， 就是之前用两个heap 找data str ...

那你是怎么从heap中删除已经跑出window的元素的？

求问狗狗西雅图的食堂也是免费的吗？
咦，好像关注的点不太一样。。。。

麻烦楼主说说第四题具体怎么回事可以吗？
pair<商品1， 商品2>， 当用户购买新的组合，update
具体在做什么

谢谢楼主！