[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

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

11月首发 Google电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
coolkid11 发表于 2016-11-2 06:24:38 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2016(10-12月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
听口音是个白人大哥, 上来介绍了下自己, 对我没有丝毫兴趣, 然后开始做题. 留学申请论坛-一亩三分地
第一道设计一个iterator, 输入一个数组[3,8,1,9,2,12]
每次调用next()得到8,8,8,9,12,12
问了半天才明白就是偶数index表示重复次数, 奇数index是要输出的数字. 1point3acres

第二题3Sum smaller

. 牛人云集,一亩三分地第三题median data stream, follow up: 如果heap的size是固定的, 但是有很多input怎么办

题其实不难, 所以还是要看运气.... 1point 3acres 论坛
攒人品求onsite求offer!. From 1point 3acres bbs

评分

参与人数 1大米 +40 收起 理由
阿童木 + 40

查看全部评分


上一篇:亚麻 OA1
下一篇:SnapChat电面跪经

本帖被以下淘专辑推荐:

  • · Google|主题: 459, 订阅: 124
  • · google|主题: 68, 订阅: 19
我的人缘0
jiongjiongyoush 发表于 2016-11-2 06:31:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
如果heap的size是固定的, 但是有很多input怎么办
zenmezuode ?
xiexie lz
回复 支持 反对

使用道具 举报

我的人缘0
wanglele 发表于 2016-11-2 13:41:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第三题是不是median data stream 是不是就是用bucket sort/counting sort来, 假设integer是4bytes, 总共需要2^32个bucket, 每个bucket再用一个int当counter 也就是总共需要2^32 * 4 Bytes = 2^34 bytes = 16GB memory.   最后根据total count 找中间那个就行
回复 支持 反对

使用道具 举报

我的人缘0
类与对象tju 发表于 2016-11-2 14:17:10 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主请问下你最后一问的followup怎么去回答的,谢谢~
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| coolkid11 发表于 2016-11-2 21:55:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
wanglele 发表于 2016-11-2 13:41
第三题是不是median data stream 是不是就是用bucket sort/counting sort来, 假设integer是4bytes, 总共 ...

我用的是标准解法, 两个heap, 一个minheap一个maxheap
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| coolkid11 发表于 2016-11-2 21:57:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
类与对象tju 发表于 2016-11-2 14:17
楼主请问下你最后一问的followup怎么去回答的,谢谢~

当时没想到什么比较好的方案, 就说了一个如果超过size的话每次都同时把最小和最大两个值去掉, 试了两个case貌似可以过, 他就没有再细问了, 但是后来想想应该不对
回复 支持 反对

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-2 23:03:00 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
Problem 1: 这个题有没有说遇到invalid的情况怎么办?1. arr.size()不是偶数;2.某个arr[even Index] < 0; 3. 如果某个arr[even Index] == 0,就按照忽略继续处理arr[even Index+2]吗?我是用vector iterator来遍历数组的,若遇到invalid的情况next()返回一个default value (i.e. INT_MIN). next()时间最差O(N)(若考虑忽略处理0 count), 空间O(1).
  1. class MyIterator {
  2. private:
  3.   vector<int>::const_iterator _itr, _itrend;. visit 1point3acres for more.
  4.   int _count;

  5. public:
  6.   MyIterator(const vector<int>& arr) :_itr(arr.begin()), _itrend(arr.end()), _count(-1) {
  7.     if (_itr != _itrend) _count = *_itr++;
  8.   }

  9.   int next() {
  10.     while (_itr != _itrend) {
  11.       if (_count > 0) { _count--; return *_itr; }
  12.       else if (_count == 0 && ++_itr != _itrend) _count = *_itr++;
  13.       else return INT_MIN;
  14.     }
  15.     return INT_MIN;
  16.   }
  17. };
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-2 23:30:41 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
coolkid11 发表于 2016-11-2 21:57
当时没想到什么比较好的方案, 就说了一个如果超过size的话每次都同时把最小和最大两个值去掉, 试了两个ca ...

第三题follow-up: 当每个heap max size有限制时,同时去掉min head的min value和max heap的max value是没有办法保证最后能准确算出整个stream's median的。因为只有同时去掉对称的kth largest and kth smallest不影响最终的median,但是这在当前时刻无法保证。-google 1point3acres

我的想法:其实这个stream's median问题我觉得无论怎么限制总空间是不可能节省的(hold in memory or hold in file),因为在没有读到stream最后一刻,任何当前的value都有可能改变median的值。所以既然每个heap max size有限制,那么就转化成一个经典data structure构造题目:如何用多个heap来实现一个heap?这个用一个额外的heap来存一个pair of每个heap top value以及指向那个heap的pointer就行了。不知道是不是这个意思。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-3 01:15:17 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
第三题follow-up: 当每个heap max size有限制时,我写了一个自己的用多个有max capacity的heap来实现的general heap数据结构。因为连经典题里的用额外的heap来存一个pair of每个heap top value以及指向那个heap的pointer的size都有限制,所以我只能用list来代替,这样的代价是pop()时间复杂度为O(log capacity + N/capacity)。其他的top(), size()和STL的一样,push()可以优化到log(capacity),而不是O(log N). 然后用这个class再开一个min head and max heap同样做就可以了。
不知道面试官是不是这个意思。。。
  1. // using a list of priority_queues with max capacity to simulate a general priority_queue
  2. class MyPQ {
  3. private:
  4.   int _capacity; // max size of each priority queue
  5.   int _size; // total size of MyPQ. visit 1point3acres for more.
  6.   list<priority_queue<int>> _pqs; // each pq has size _capacity except last one (size <= _capacity)
  7.   list<priority_queue<int>>::reverse_iterator _top; // position of top value in _pqs
  8. . visit 1point3acres for more.
  9. public:
  10.   MyPQ(int cap) :_capacity(cap), _size(0) { _top = _pqs.rend(); }
  11. . 围观我们@1point 3 acres
  12.   // time O(log capacity)
  13.   void push(int x) {
  14.     // add a new pq if capacity is full
  15.     if (_pqs.empty() || _pqs.rbegin()->size() == _capacity) _pqs.push_back(priority_queue<int>());
  16.     _pqs.rbegin()->push(x); _size++;
  17.     // update top value position
  18.     if (_top == _pqs.rend() || x > _top->top()) _top = _pqs.rbegin();
  19.   }

  20.   // time O(1)
  21.   int top() {
  22.     return _top == _pqs.rend() ? INT_MIN : _top->top();
  23.   }
  24. .本文原创自1point3acres论坛
  25.   // time O(1)
  26.   int size() {
  27.     return _size;
  28.   }. 牛人云集,一亩三分地

  29.   // time O(log capacity + N/capacity)
  30.   // note _pq.size() = O(N/capacity). Waral 博客有更多文章,
  31.   void pop() {
  32.     if (_top == _pqs.rend()) return;
  33.     _top->pop(); . more info on 1point3acres
  34.     if (--_size == 0) {
  35.       _pqs.clear(); _top = _pqs.rend();
  36.     }
  37.     // move top value from last pq to the pq used to have global top value
  38.     // to keep its size full capacity (makes sure to have min size of list _pqs)
  39.     if (_top != _pqs.rbegin()) {
  40.       _top->push(_pqs.rbegin()->top());
  41.       _pqs.rbegin()->pop();
  42.       if (_pqs.rbegin()->empty()) _pqs.erase(--_pqs.end());.本文原创自1point3acres论坛
  43.     }
  44.     // recalculate global top value position-google 1point3acres
  45.     for (auto it = _pqs.rbegin(); it != _pqs.rend(); ++it)
  46.       if (it->top() > _top->top()) _top = it;
  47.   }
  48. };
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
shiningdong 发表于 2016-11-3 02:19:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zzgzzm 发表于 2016-11-2 23:03
Problem 1: 这个题有没有说遇到invalid的情况怎么办?1. arr.size()不是偶数;2.某个arr[even Index] < 0;  ...

我觉得当input invalid的时候,可以直接throw exception
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| coolkid11 发表于 2016-11-3 06:46:43 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zzgzzm 发表于 2016-11-2 23:03. visit 1point3acres for more.
Problem 1: 这个题有没有说遇到invalid的情况怎么办?1. arr.size()不是偶数;2.某个arr[even Index] < 0;  ...

问了他各种corner case, 只要不符合的一律返回-1就可以, 假设数组里全是正数, 而且都是valid input
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| coolkid11 发表于 2016-11-3 06:51:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zzgzzm 发表于 2016-11-3 01:15
第三题follow-up: 当每个heap max size有限制时,我写了一个自己的用多个有max capacity的heap来实现的gen ...

大神~~
因为当时没时间了所以我觉得他就是随口一问, 他应该是想问如果memory不够怎么办
回复 支持 反对

使用道具 举报

我的人缘0
sunnyroom 发表于 2016-11-26 12:24:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
wanglele 发表于 2016-11-2 13:41. 留学申请论坛-一亩三分地
第三题是不是median data stream 是不是就是用bucket sort/counting sort来, 假设integer是4bytes, 总共 ...

怎么根据total count找中间那个?. visit 1point3acres for more.
全部bucket扫一遍吗?
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-19 13:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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