推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6241|回复: 55
收起左侧

Google电面,面经

[复制链接] |试试Instant~ |关注本帖
mc422 发表于 2015-9-30 04:08:11 | 显示全部楼层 |阅读模式

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

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

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

x
地里的同志帮忙给的内推,在这里谢谢了, @whuwangyi
. 1point3acres.com/bbs
电面的是中国同胞,上来介绍完就开始做题。
. 1point3acres.com/bbs
第一问,totalpass of an element x in array A is defined as the number of elements which is larger than element x. Given an array A, find the maximun totalpass of this array.

第二问,leftpass of an element x is defined as the number of elements on left side of x which is larger than element x. find the maximum leftpass of an array.
上来先用brute force给解了。但之后没想出improved solution。试着想用stack去存larger element,但发现是条dead end。
最后面试官给hint,用BST做。单没想出怎么maintain这个BST。只能简单的写出伪代码。.鏈枃鍘熷垱鑷1point3acres璁哄潧

发现GeekforGeek 上有道类似的题,用的就是BST,有兴趣可以看看:
http://www.geeksforgeeks.org/cou ... ents-on-right-side/. From 1point 3acres bbs

估计是要跪了。祝大家好运。.鏈枃鍘熷垱鑷1point3acres璁哄潧



补充内容 (2015-10-5 00:51):
结果竟然拿到onsite了,可能是面试小哥手下留情了。总之大家加油,地里朋友祝我好运啊。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

八月槎 发表于 2015-10-10 15:16:44 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第二题可以用两个priority_queue(就是堆),第一个大根堆存储比当前数小的数字,第二个小根堆存比当前数大的数字
然后每次move next 就看数变大还是变小了,然后从一个堆pop()到另一个堆. 1point 3acres 璁哄潧
回复 支持 2 反对 0

使用道具 举报

flexwang 发表于 2015-9-30 16:12:46 | 显示全部楼层
关注一亩三分地微博:
Warald
  1. #include <vector>
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <utility>

  5. using namespace std;


  6. //left pass
  7. void merge_sort(vector<pair<int,int>> &vp, vector<int> &sp) {
  8.     if (vp.size() < 2) return;. 1point3acres.com/bbs
  9.     int m = vp.size()/2;
  10.     vector<pair<int,int>> va(vp.begin(), vp.begin()+m),
  11.         vb(vp.begin()+m, vp.end());.1point3acres缃
  12.     merge_sort(va, sp);
  13.     merge_sort(vb, sp);
  14.     for (int i=0,j=0,k=0; i<va.size()||j<vb.size();) {
  15.         if (i<va.size() && j<vb.size()) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.             if (va[i].first > vb[j].first)
  17.                 vp[k++] = va[i++];
  18.             else {
  19.                 int id = vb[j].second;
  20.                 sp[id] += i;
  21.                 vp[k++] = vb[j++];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.             }
  23.         }
  24.         else if (i<va.size())
  25.             vp[k++] = va[i++];
  26.         else {. 1point3acres.com/bbs
  27.             int id = vb[j].second;
  28.             sp[id] += i;
  29.             vp[k++] = vb[j++];-google 1point3acres
  30.         }
  31.     }
  32. }
  33. int left_pass(vector<int> v) {
  34.     int len = v.size();
  35.     vector<int> sp(len, 0);
  36.     vector<pair<int,int>> vp;. Waral 鍗氬鏈夋洿澶氭枃绔,
  37.     for (int i=0; i<v.size(); i++)
  38.         vp.push_back(make_pair(v[i], i));
  39.     merge_sort(vp, sp);
  40.     int ans = 0;
  41.     for (auto x:sp)
  42.         ans = max(ans, x);
  43.     return ans;
  44. }
  45. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  46. int left_pass_brute_force(vector<int> v) {
  47.     int ans = 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  48.     for (int i=1; i<v.size(); i++) {
  49.         int cnt = 0;. From 1point 3acres bbs
  50.         for (int j=i-1; j>=0; j--)
  51.             if (v[i] < v[j]) cnt++;. From 1point 3acres bbs
  52.         ans = max(ans, cnt);
  53.     }
  54.     return ans;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  55. }

  56. void test_left_pass(int ncase) {
  57.     int npass = 0;
  58.     for (int i=0; i<ncase; i++) {
  59.         int size = rand()%1007;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  60.         vector<int> v(size);
  61.         for (int j=0; j<size; j++)
  62.             v[j] = rand()%17;
  63.         if (left_pass(v) == left_pass_brute_force(v))
  64.             npass ++;
  65.     }
  66.     printf("%d/%d\n", npass, ncase);
  67. }

  68. int main()
  69. {   
  70.     test_left_pass(1007);
  71.     return 0;
  72. }
复制代码
回复 支持 2 反对 0

使用道具 举报

Wizmann 发表于 2015-9-30 09:39:49 | 显示全部楼层
第二题:
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <map>

  8. using namespace std;
  9. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10. #define print(x) cout << x << endl
  11. #define input(x) cin >> x. from: 1point3acres.com/bbs

  12. class BITree {
  13. public:
  14.     void init(int size) {
  15.         _tree.resize(size + 1);
  16.         fill(_tree.begin(), _tree.end(), 0);
  17.     }

  18.     void add(int pos, int value) {. 1point3acres.com/bbs
  19.         while (pos < _tree.size()) {
  20.             _tree[pos] += value;
  21.             pos += lowbit(pos);
  22.         }
  23.     }

  24.     int sum(int pos) {
  25.         int res = 0;
  26.         while (pos > 0) {
  27.             res += _tree[pos];
  28.             pos -= lowbit(pos);. 鍥磋鎴戜滑@1point 3 acres
  29.         }
  30.         return res;
  31.     }
  32. private:
  33.     inline int lowbit(int x) { return x & (-x); }

  34. private:
  35.     vector<int> _tree;
  36. };. 1point3acres.com/bbs

  37. int main() {
  38.     freopen("input.txt", "r", stdin);
  39.     int n;
  40.     vector<int> nums;
  41.     map<int, int> mp;.1point3acres缃
  42. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  43.     input(n);
  44.     nums.resize(n);
  45.     for (int i = 0; i < n; i++) {
  46.         input(nums[i]);-google 1point3acres
  47.         mp[nums[i]] = -1;
  48.     }

  49.     int idx = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  50.     for (auto& p: mp) {
  51.         p.second = ++idx;
  52.     }

  53.     BITree bitree;
  54.     bitree.init(n + 1);

  55.     int ans = 0;
  56.     for (int i = 0; i < n; i++) {
  57.         int u = nums[i];
  58.         ans = max(ans, bitree.sum(u));
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  59.         bitree.add(u, 1);
  60.     }
  61.     print(ans);
  62.     return 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  63. }
复制代码

补充内容 (2015-9-30 09:41):
代码没测过,仅供参考。轻拍。. 鍥磋鎴戜滑@1point 3 acres

要是足够牛逼的话,可以手写一个AVL/SBT。用平衡树的性质做。(争取吓尿面试官(并不能

补充内容 (2015-9-30 09:51):
果然写错了
67行应该是: ans = max(ans, bitree.sum(u - 1));

楼下的兄弟:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果treeset对应的是std::set的话,那就是不行的。迭代器之间的距离需要O(N)的时间。

我一小时只能发两帖,不能跟帖回复了,抱歉。

补充内容 (2015-9-30 10:53):
66行改成:int u = mp[nums];

智商堪忧啊我擦
回复 支持 1 反对 0

使用道具 举报

mileschen2008 发表于 2015-9-30 05:44:49 | 显示全部楼层
第一题的题意不太懂,maximum totalpass感觉就是len-1啊,因为数组中最小值的totalpass最大,因为其他的len-1个数都大于它。如果理解错了,还希望楼主稍微再说明下题目,多谢啦。
回复 支持 反对

使用道具 举报

hanchen999 发表于 2015-9-30 05:54:38 | 显示全部楼层
这题看着怎么像segmenttree。。。第二问
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-30 06:04:29 | 显示全部楼层
mileschen2008 发表于 2015-9-30 05:44.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一题的题意不太懂,maximum totalpass感觉就是len-1啊,因为数组中最小值的totalpass最大,因为其他的len ...

[1,1,1]是什么
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-30 06:41:10 | 显示全部楼层
BST估计是每一个点记录右子&#127794;点得数量
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-30 06:42:33 | 显示全部楼层
Linzertorte 发表于 2015-9-30 06:04. From 1point 3acres bbs
[1,1,1]是什么
. visit 1point3acres.com for more.
嗯,是的,要考虑duplicates,但是这道题目也就是找min value,然后找比他大的就行。如果array已经sort,就O(logn),没sort O(n).
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-30 06:53:36 | 显示全部楼层
mileschen2008 发表于 2015-9-30 06:42. from: 1point3acres.com/bbs
嗯,是的,要考虑duplicates,但是这道题目也就是找min value,然后找比他大的就行。如果array已经sort, ...

没sort的话可以O(n)解这题? 就算用BST也要O(nlogn)吧?
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-30 07:16:37 | 显示全部楼层
kelvinzhong 发表于 2015-9-30 06:53. From 1point 3acres bbs
没sort的话可以O(n)解这题? 就算用BST也要O(nlogn)吧?

我说的第一问哈。第二问BST当然得O(nlogn)啦。
回复 支持 反对

使用道具 举报

guzi 发表于 2015-9-30 07:56:46 | 显示全部楼层
第一问像是Leetcode上的h-index问题. 鍥磋鎴戜滑@1point 3 acres
大概看了一下geeks for geeks 上关于第二问的解答,好长。。。确定是要在面试中全部写出来么? 感觉这一道题就可以用掉45分钟了。。PS: 没见过AVL的不就惨了?
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-30 08:53:46 | 显示全部楼层
感觉这道题的第二问好像可以用Stack来解决啊,还是需要先排序,从大到小排,然后还要用hash表存储好所有重复项的个数,接着向栈里面逐个压进去每一项,如果入栈的项的下标比栈顶的大,那么开始pop,直到栈顶的元素的下标比入栈项的小,这中间没pop出一个都可以计算出该项的leftpass值。说的有点儿晦涩,但是感觉确实可以用排序+栈来做!
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-9-30 09:30:26 | 显示全部楼层
第一题:
  1. nums = map(int, raw_input().split()). 1point 3acres 璁哄潧
  2. mini = min(nums)
  3. print len(filter(lambda x: x > mini, nums))
复制代码
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-30 09:45:56 | 显示全部楼层
Wizmann 发表于 2015-9-30 09:39
第二题:.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2015-9-30 09:41):
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二题不能用treeset么
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-30 10:15:51 | 显示全部楼层
readman 发表于 2015-9-30 09:45
第二题不能用treeset么
. Waral 鍗氬鏈夋洿澶氭枃绔,
我觉得第二题可以用Java 的 TreeSet,TreeSet是Red-black bst。但是呢,有个限制条件是数组必须没有duplicates.
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-30 10:34:56 | 显示全部楼层
mileschen2008 发表于 2015-9-30 10:15. 1point 3acres 璁哄潧
我觉得第二题可以用Java 的 TreeSet,TreeSet是Red-black bst。但是呢,有个限制条件是数组必须没有dupli ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
有dup也可以, 弄个counter 最后减一下
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-30 10:45:39 | 显示全部楼层
readman 发表于 2015-9-30 10:34
有dup也可以, 弄个counter 最后减一下

那这样的话,你得遍历每一个大于它的数了,这好像跟brute-force无异了。不知道我理解的对不对,你能不能稍微写个代码出来看看?
回复 支持 反对

使用道具 举报

Annabelle哈哈哈 发表于 2015-9-30 11:49:03 | 显示全部楼层
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-30 12:02:28 | 显示全部楼层
Annabelle哈哈哈 发表于 2015-9-30 11:49
http://www.lintcode.com/en/problem/count-of-smaller-number-before-itself/
第二题是不是这个

面试要写个segment tree也是醉了。
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-9-30 14:23:31 | 显示全部楼层
mileschen2008 发表于 2015-9-30 12:02
面试要写个segment tree也是醉了。

蛤蛤

也可以写块状链表,不过也不会更简单。
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-30 15:48:33 | 显示全部楼层
第二问就是求surpass吧,一般是用BIT或者merge sort吧 都是nlogn的 BST应该是类似的思路
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-26 15:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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