一亩三分地论坛

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

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

Google电面,面经

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

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

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

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

x
地里的同志帮忙给的内推,在这里谢谢了, @whuwangyi

电面的是中国同胞,上来介绍完就开始做题。

第一问,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.. more info on 1point3acres.com
上来先用brute force给解了。但之后没想出improved solution。试着想用stack去存larger element,但发现是条dead end。
最后面试官给hint,用BST做。单没想出怎么maintain这个BST。只能简单的写出伪代码。
-google 1point3acres
发现GeekforGeek 上有道类似的题,用的就是BST,有兴趣可以看看:.鐣欏璁哄潧-涓浜-涓夊垎鍦
http://www.geeksforgeeks.org/cou ... ents-on-right-side/.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
估计是要跪了。祝大家好运。



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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

八月槎 发表于 2015-10-10 15:16:44 | 显示全部楼层
第二题可以用两个priority_queue(就是堆),第一个大根堆存储比当前数小的数字,第二个小根堆存比当前数大的数字
然后每次move next 就看数变大还是变小了,然后从一个堆pop()到另一个堆.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 2 反对 0

使用道具 举报

flexwang 发表于 2015-9-30 16:12:46 | 显示全部楼层
  1. #include <vector>
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <utility>

  5. using namespace std;


  6. //left pass. Waral 鍗氬鏈夋洿澶氭枃绔,
  7. void merge_sort(vector<pair<int,int>> &vp, vector<int> &sp) {
  8.     if (vp.size() < 2) return;
  9.     int m = vp.size()/2;
  10.     vector<pair<int,int>> va(vp.begin(), vp.begin()+m),
  11.         vb(vp.begin()+m, vp.end());
  12.     merge_sort(va, sp);
  13.     merge_sort(vb, sp);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.     for (int i=0,j=0,k=0; i<va.size()||j<vb.size();) {
  15.         if (i<va.size() && j<vb.size()) {. From 1point 3acres bbs
  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 {
  27.             int id = vb[j].second;
  28.             sp[id] += i;
  29.             vp[k++] = vb[j++];
  30.         }
  31.     }
    -google 1point3acres
  32. }. from: 1point3acres.com/bbs
  33. int left_pass(vector<int> v) {
  34.     int len = v.size();
  35.     vector<int> sp(len, 0);.1point3acres缃
  36.     vector<pair<int,int>> vp; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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;
  50.         for (int j=i-1; j>=0; j--)
  51.             if (v[i] < v[j]) cnt++;
  52.         ans = max(ans, cnt);
  53.     }
  54.     return ans;.1point3acres缃
  55. }
  56. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  57. void test_left_pass(int ncase) {
  58.     int npass = 0;
  59.     for (int i=0; i<ncase; i++) {
  60.         int size = rand()%1007;
  61.         vector<int> v(size);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  62.         for (int j=0; j<size; j++).鐣欏璁哄潧-涓浜-涓夊垎鍦
  63.             v[j] = rand()%17;
  64.         if (left_pass(v) == left_pass_brute_force(v))
  65.             npass ++;
  66.     }
  67.     printf("%d/%d\n", npass, ncase);
  68. }. 1point 3acres 璁哄潧

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

使用道具 举报

Wizmann 发表于 2015-9-30 09:39:49 | 显示全部楼层
第二题:
  1. #include <cstdio>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2. #include <cstdlib>.1point3acres缃
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <map>

  8. using namespace std;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  9. #define print(x) cout << x << endl
  10. #define input(x) cin >> x
  11. .1point3acres缃
  12. class BITree {. visit 1point3acres.com for more.
  13. public:
  14.     void init(int size) {. visit 1point3acres.com for more.
  15.         _tree.resize(size + 1);
  16.         fill(_tree.begin(), _tree.end(), 0);
  17.     }
  18. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.     void add(int pos, int value) {
  20.         while (pos < _tree.size()) {
  21.             _tree[pos] += value;
  22.             pos += lowbit(pos);
  23.         }
  24.     }

  25.     int sum(int pos) {
  26.         int res = 0;
  27.         while (pos > 0) {
  28.             res += _tree[pos];. From 1point 3acres bbs
  29.             pos -= lowbit(pos);
  30.         }. more info on 1point3acres.com
  31.         return res;
  32.     }
  33. private:
  34.     inline int lowbit(int x) { return x & (-x); }

  35. private:
  36.     vector<int> _tree;
  37. };

  38. int main() {. Waral 鍗氬鏈夋洿澶氭枃绔,
  39.     freopen("input.txt", "r", stdin);
  40.     int n;
  41.     vector<int> nums;
  42.     map<int, int> mp;-google 1point3acres

  43. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  44.     input(n);
  45.     nums.resize(n);
  46.     for (int i = 0; i < n; i++) {.1point3acres缃
  47.         input(nums[i]);
  48.         mp[nums[i]] = -1;. From 1point 3acres bbs
  49.     }

  50.     int idx = 0;
  51.     for (auto& p: mp) {
  52.         p.second = ++idx;
  53.     }
  54. . From 1point 3acres bbs
  55.     BITree bitree;
  56.     bitree.init(n + 1);

  57.     int ans = 0;
  58.     for (int i = 0; i < n; i++) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  59.         int u = nums[i];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  60.         ans = max(ans, bitree.sum(u));. visit 1point3acres.com for more.
  61.         bitree.add(u, 1);
  62.     }
  63.     print(ans);
  64.     return 0;
  65. }. From 1point 3acres bbs
复制代码

补充内容 (2015-9-30 09:41):
代码没测过,仅供参考。轻拍。

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

补充内容 (2015-9-30 09:51):
果然写错了. 鍥磋鎴戜滑@1point 3 acres
67行应该是: ans = max(ans, bitree.sum(u - 1));

楼下的兄弟:
如果treeset对应的是std::set的话,那就是不行的。迭代器之间的距离需要O(N)的时间。
. 1point3acres.com/bbs
我一小时只能发两帖,不能跟帖回复了,抱歉。

补充内容 (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
第一题的题意不太懂,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 | 显示全部楼层

嗯,是的,要考虑duplicates,但是这道题目也就是找min value,然后找比他大的就行。如果array已经sort,就O(logn),没sort O(n).
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

mileschen2008 发表于 2015-9-30 07:16:37 | 显示全部楼层
kelvinzhong 发表于 2015-9-30 06:53
没sort的话可以O(n)解这题? 就算用BST也要O(nlogn)吧?
. From 1point 3acres bbs
我说的第一问哈。第二问BST当然得O(nlogn)啦。
回复 支持 反对

使用道具 举报

guzi 发表于 2015-9-30 07:56:46 | 显示全部楼层
第一问像是Leetcode上的h-index问题
大概看了一下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())
  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
第二题:

补充内容 (2015-9-30 09:41):

第二题不能用treeset么
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-30 10:15:51 | 显示全部楼层
readman 发表于 2015-9-30 09:45
第二题不能用treeset么

我觉得第二题可以用Java 的 TreeSet,TreeSet是Red-black bst。但是呢,有个限制条件是数组必须没有duplicates.
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-30 10:34:56 | 显示全部楼层
mileschen2008 发表于 2015-9-30 10:15
我觉得第二题可以用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应该是类似的思路
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 00:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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