一亩三分地论坛

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

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

11月首发 Google电面

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

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

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

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

x
听口音是个白人大哥, 上来介绍了下自己, 对我没有丝毫兴趣, 然后开始做题
第一道设计一个iterator, 输入一个数组[3,8,1,9,2,12]
每次调用next()得到8,8,8,9,12,12. visit 1point3acres.com for more.
问了半天才明白就是偶数index表示重复次数, 奇数index是要输出的数字
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题3Sum smaller. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

第三题median data stream, follow up: 如果heap的size是固定的, 但是有很多input怎么办

题其实不难, 所以还是要看运气...
攒人品求onsite求offer!. 1point3acres.com/bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 57, 订阅: 5
jiongjiongyoush 发表于 2016-11-2 06:31:06 | 显示全部楼层
如果heap的size是固定的, 但是有很多input怎么办. more info on 1point3acres.com
zenmezuode ?
xiexie lz
回复 支持 反对

使用道具 举报

澹水猪 发表于 2016-11-2 06:39:33 | 显示全部楼层
我天 一口气面了三道题么 太厉害
回复 支持 反对

使用道具 举报

wanglele 发表于 2016-11-2 13:41:04 | 显示全部楼层
第三题是不是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 找中间那个就行
回复 支持 反对

使用道具 举报

类与对象tju 发表于 2016-11-2 14:17:10 | 显示全部楼层
楼主请问下你最后一问的followup怎么去回答的,谢谢~
回复 支持 反对

使用道具 举报

 楼主| coolkid11 发表于 2016-11-2 21:55:56 | 显示全部楼层
wanglele 发表于 2016-11-2 13:41
第三题是不是median data stream 是不是就是用bucket sort/counting sort来, 假设integer是4bytes, 总共 ...

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

使用道具 举报

 楼主| coolkid11 发表于 2016-11-2 21:57:40 | 显示全部楼层
类与对象tju 发表于 2016-11-2 14:17
楼主请问下你最后一问的followup怎么去回答的,谢谢~

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

使用道具 举报

zzgzzm 发表于 2016-11-2 23:03:00 | 显示全部楼层
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).. 1point 3acres 璁哄潧
  1. class MyIterator {
  2. private:
  3.   vector<int>::const_iterator _itr, _itrend;
  4.   int _count;
  5. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  6. public:
  7.   MyIterator(const vector<int>& arr) :_itr(arr.begin()), _itrend(arr.end()), _count(-1) {
  8.     if (_itr != _itrend) _count = *_itr++;. 1point3acres.com/bbs
  9.   }

  10.   int next() {
  11.     while (_itr != _itrend) {
  12.       if (_count > 0) { _count--; return *_itr; }
  13.       else if (_count == 0 && ++_itr != _itrend) _count = *_itr++;. visit 1point3acres.com for more.
  14.       else return INT_MIN;
  15.     }
  16.     return INT_MIN;
  17.   }
  18. };. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-2 23:30:41 | 显示全部楼层
coolkid11 发表于 2016-11-2 21:57. from: 1point3acres.com/bbs
当时没想到什么比较好的方案, 就说了一个如果超过size的话每次都同时把最小和最大两个值去掉, 试了两个ca ...

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

我的想法:其实这个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就行了。不知道是不是这个意思。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-3 01:15:17 | 显示全部楼层
第三题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
  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.1point3acres缃
  8. .1point3acres缃
  9. public:
  10.   MyPQ(int cap) :_capacity(cap), _size(0) { _top = _pqs.rend(); }

  11.   // time O(log capacity). more info on 1point3acres.com
  12.   void push(int x) {
  13.     // add a new pq if capacity is full
  14.     if (_pqs.empty() || _pqs.rbegin()->size() == _capacity) _pqs.push_back(priority_queue<int>());. 1point 3acres 璁哄潧
  15.     _pqs.rbegin()->push(x); _size++;
  16.     // update top value position
  17.     if (_top == _pqs.rend() || x > _top->top()) _top = _pqs.rbegin();
  18.   }

  19.   // time O(1)
  20.   int top() {
  21.     return _top == _pqs.rend() ? INT_MIN : _top->top();
  22.   }

  23.   // time O(1)
  24.   int size() {
  25.     return _size;
  26.   }
  27. . 1point3acres.com/bbs
  28.   // time O(log capacity + N/capacity)
  29.   // note _pq.size() = O(N/capacity)
  30.   void pop() {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  31.     if (_top == _pqs.rend()) return;
  32.     _top->pop();
  33.     if (--_size == 0) {
  34.       _pqs.clear(); _top = _pqs.rend();
  35.     }
  36.     // move top value from last pq to the pq used to have global top value
  37.     // to keep its size full capacity (makes sure to have min size of list _pqs)
  38.     if (_top != _pqs.rbegin()) {
  39.       _top->push(_pqs.rbegin()->top());
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  40.       _pqs.rbegin()->pop();
  41.       if (_pqs.rbegin()->empty()) _pqs.erase(--_pqs.end());
  42.     }
  43.     // recalculate global top value position
  44.     for (auto it = _pqs.rbegin(); it != _pqs.rend(); ++it)
  45.       if (it->top() > _top->top()) _top = it;
  46.   }
  47. };
复制代码
回复 支持 反对

使用道具 举报

shiningdong 发表于 2016-11-3 02:19:39 | 显示全部楼层
zzgzzm 发表于 2016-11-2 23:03.1point3acres缃
Problem 1: 这个题有没有说遇到invalid的情况怎么办?1. arr.size()不是偶数;2.某个arr[even Index] < 0;  ...
-google 1point3acres
我觉得当input invalid的时候,可以直接throw exception
回复 支持 反对

使用道具 举报

 楼主| coolkid11 发表于 2016-11-3 06:46:43 | 显示全部楼层
zzgzzm 发表于 2016-11-2 23:03
Problem 1: 这个题有没有说遇到invalid的情况怎么办?1. arr.size()不是偶数;2.某个arr[even Index] < 0;  ...

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

使用道具 举报

 楼主| coolkid11 发表于 2016-11-3 06:51:14 | 显示全部楼层
zzgzzm 发表于 2016-11-3 01:15
第三题follow-up: 当每个heap max size有限制时,我写了一个自己的用多个有max capacity的heap来实现的gen ...

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

使用道具 举报

sunnyroom 发表于 2016-11-26 12:24:45 | 显示全部楼层
wanglele 发表于 2016-11-2 13:41
第三题是不是median data stream 是不是就是用bucket sort/counting sort来, 假设integer是4bytes, 总共 ...

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 11:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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