一亩三分地论坛

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

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

Google 9月2日电面,9月15日onsite面经

[复制链接] |试试Instant~ |关注本帖
zzwzhong698800 发表于 2015-9-16 09:44:06 | 显示全部楼层 |阅读模式

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

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

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

x
9月2日的电面,15号的onsite的,本人在北京,想肉身翻墙,就报了usa的Google,师兄给内推的,2号的电面,15号的onsite四轮
电面:
1. 序列化和反序列化二叉树
2. 求字符串中最长的总共不相同字符个数不超过M的最长子串长度。
国人小哥,北京打来的电话,人很nice,虽然我磕磕绊绊,两道题还是做出来了,虽然被小哥一直提醒这有bug,那有bug的。面完之后我以为跪了,结果下午hr就打电话邀请我onsite,让我很惊喜。

onsite:
我能说很简单麽…………不知道是大家都这样,还是我上辈子积了太多德,题目真的好简单……四个面试官都是米国飞过来的
一轮,印度小哥,态度不算差,都还是有说有笑,题目竟然是电面的第二题…………还是那个不相同字符个数不超过M的最长子串长度…………我当时就惊了,一分钟写完code,然后小哥拍了照,说follow up,如果这是个字符流,只能遍历一次,怎么办,我当时想的很混乱,写的也很混乱,不知道小哥怎么看,反正这面不是很好。
二轮,中国小哥,人特别nice,让我自我介绍了一下,然后问了我malloc和new的区别,析构函数为什么不能抛异常,异常的机制,c中内存分配方式的情况,然后用怎么分配一个二维数组,。然后写了四行代码…………小哥真的很nice。到后面我专业术语我实在没法用英语说了,全用中文了。
三轮,hk小哥,英文,设计买票系统,有几个requirement,每人只能一次看10个seats,每个人不能同时看相同范围的seats,一个人只能一次book一个seat,两分钟内没有book自动退出。然后就设计了几个api接口,然后设计了底层database,然后小哥一直针对系统问问题,一直给提示,我就顺着他的思路说,加cookie,session,blabla之类的。人也很nice,一直都给hint
四轮,白人小哥,小哥英语讲得太快了,是这四轮里,我听得最费劲的,我听力和口语都只是正常国内学术的水平,所以一直在pardon中……,很简单的两道题……一道是求一个数二进制表示中bit为1的个数,二是设计一个类,实现insert,remove,poprandom一个字符,很简答的,我开始用set和vector,然后小哥一个个让我分析复杂度,其实函数超级简单,所以复杂度也是一眼就能看出来,就跟vector和set本身的操作复杂度一样,后来小哥说popRandom复杂度可不可以降一下,我说想想,然后把vector去掉了,直接用set来做,然后就降到O(logn)了,然后就结束了,随便问了几个问题。
over………………………………

还没出结果,坐等hr电话中,发个面经,求过。
我的面经真的不足以为例,我觉得太简单了…………不是我牛,是真的很简单…………我刷了leetcode+cc150+剑指offer+编程之美,刷了3遍,结果一个都没碰上,代码电面写了两道,onsite总共写了3道…………木有recursion,木有dfs,木有bfs,木有dp,什么都木有

还是很忐忑的等hr的feedback中,我待会会把最近在地里收集到的面经以及自己写的答案代码发上来,求攒rp!

. more info on 1point3acres.com
补充内容 (2015-9-16 09:51):
大家可以给我加点米么?我是用学弟的账号登的,之前下东西用了很多大米了,求大家给我加点米,我会视大家的慷慨贴代码的,我还是藏了很多代码的~~-google 1point3acres

补充内容 (2015-9-17 17:27):
刚收到hr电话,跪了,feedback是虽然都做出来了都答出来了,但是没有最优化……其实我也很无奈与无辜,给我的题是很简单,我不知道这是幸运还是不幸,都是几行代码可以搞定的,感觉没有什么可优化的了

补充内容 (2015-9-17 17:27):
可能我还没抓到点,可能也还是我太弱了,至少他们是这么感觉的。

补充内容 (2015-9-17 17:27):
突然觉得好迷茫,很想肉身翻墙,但是感觉除了谷歌都没有其他公司会给面试的机会,因为很少有公司会原来来华招人,我在地里也找人内推了很多,都得不到任何回复,心里还是很酸楚的。

补充内容 (2015-9-17 17:28):
本人女生,T大研究生,国内目前倒是拿了几个offer,百度凤巢,美团,京东广告,网易有道,但我却很想去国外呆呆,想去国外见见世面。有谁能指条路么?我现在想投都不知道往哪里投了,好心累,有谁可以指指路么?

评分

19

查看全部评分

本帖被以下淘专辑推荐:

 楼主| zzwzhong698800 发表于 2015-9-16 09:49:12 | 显示全部楼层
下面我会把我在地里搜集到的面经题,以及自己的解法都放上来,大部分都是自己写的,所以也可能有错误,大家参考参考。
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:52:28 | 显示全部楼层
  1. /*
  2. 一个数组,可在数中间插入+或-,输出所有可能的结果。  
  3. 如input:[1, 2, 3]  可能的结果是:1+2+3=6, 1+2-3=0, 1-2+3=2, 1-2-3=-4   
  4. */
  5. -google 1point3acres
  6. #include <iostream>
  7. #include <string>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8. #include <set>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9. #include <climits>
  10. #include <cmath>
  11. #include <stack>
  12. #include <algorithm>
  13. #include<vector>
  14. using namespace std;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  15. class Solution
  16. {
  17. public:. 鍥磋鎴戜滑@1point 3 acres
  18.         //注意题意只有+和-,所以肯定是顺序执行的,没有优先级一说,也没有加括号
  19.         //所以不需要DFS,不需要分治来考虑
  20.         //如果有*或/,或者有(),则需要分治,因为计算的顺序改变了,不是单纯的从左到右
  21.         vector<int> calculate(vector<int> arr)
  22.         {
  23.                 if(arr.size() < 2)
  24.                         return vector<int>();

  25.                 vector<int> res;
  26.                 set<int> cur;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.                 cur.insert(arr[0]);
  28.                 for(int i = 1; i < arr.size(); i++)-google 1point3acres
  29.                 {
  30.                         set<int> next;
  31.                         set<int>::iterator setItr = cur.begin();
  32.                         for(; setItr != cur.end(); setItr++)
  33.                         {
  34.                                 int d = *setItr;
  35.                                 int plusRes = d + arr[i];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.                                 int subRes = d - arr[i];
  37.                                 next.insert(plusRes);
  38.                                 next.insert(subRes);
  39.                         }
  40.                         cur.clear();
  41.                         cur = next;
  42.                 }

  43.                 set<int>::iterator setItr = cur.begin();
  44.                 for(; setItr != cur.end(); setItr++)
  45.                         res.push_back(*setItr);
  46.                 return res;
  47.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  48. }; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  49. //int main()
  50. //{
  51. //        int a[] = {1,2,3,4};. Waral 鍗氬鏈夋洿澶氭枃绔,
  52. //        int n = sizeof(a)/sizeof(int);
  53. //        vector<int> v(a, a+n);
  54. //. 1point3acres.com/bbs
  55. //        Solution ss;. from: 1point3acres.com/bbs
  56. //        vector<int> res = ss.calculate(v);
  57. //        int i = 0;
  58. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:53:33 | 显示全部楼层
  1. /*
  2. 给一个数字的array,两个数字间只用+或者* 算出最大的值
  3. z下面也可以改为求所有情况
  4. */

  5. #include <iostream>
  6. #include <string>
  7. #include <sstream> 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8. #include <unordered_set>
  9. #include <algorithm>
  10. #include<vector>
  11. #include <map>
  12. using namespace std;

  13. class Solution {
  14. public:
  15.         int maxResWithPlusAndMul(vector<int> &arr). Waral 鍗氬鏈夋洿澶氭枃绔,
  16.         {
    . more info on 1point3acres.com
  17.                 int maxR = INT_MIN;. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.                 helper(arr, 0, arr.size() - 1, maxR);
  19.                 return maxR;.1point3acres缃
  20.         }
  21.         vector<int> helper(vector<int> &arr, int left, int right, int &maxR)
  22.         {
  23.                 vector<int> res;
  24.                 if(left > right). visit 1point3acres.com for more.
  25.                 {
  26.                         return res;
  27.                 }
  28.                 if(right == left)
  29.                 {
  30.                         res.push_back(arr[left]);
  31.                         res.push_back(arr[left]);
  32.                         return res;
  33.                 }
  34.                 for(int i = left; i < right; i++)
  35.                 {
  36.                         vector<int> leftAns = helper(arr, left, i, maxR);
  37.                         vector<int> rightAns = helper(arr, i+1, right, maxR);

  38.                         int larger = INT_MIN;
  39.                         int smaller = INT_MAX;
  40.                         for(int i = 0; i < 2; i++)
  41.                         {
  42.                                 for(int j = 0; j < 2; j++)
  43.                                 {
  44.                                         int t1 = leftAns[i] * rightAns[j];
  45.                                         int t2 = leftAns[i] + rightAns[j];
  46.                                         larger = max(max(larger, t1), t2);
  47.                                         smaller = min(min(smaller, t2), t2);
  48.                                 }
  49.                         }

  50.                         res.push_back(smaller);
  51.                         res.push_back(larger);

  52.                         maxR = max(maxR, larger);
  53.                 }
  54.                 return res;
  55.         }
  56. };

  57. //int main()
  58. //{
  59. //        int arr[] = {1, -2, -3};
  60. //        int n = sizeof(arr)/sizeof(int);
  61. //        vector<int> v(arr, arr+n);. Waral 鍗氬鏈夋洿澶氭枃绔,
  62. //        Solution ss;
  63. //        cout<<ss.maxResWithPlusAndMul(v);
  64. //        int i = 0;
  65. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:56:37 | 显示全部楼层
  1. /*
  2. http://blog.csdn.net/u013480600/article/details/27558813.1point3acres缃
  3. 滑雪(DFS+DP). 鍥磋鎴戜滑@1point 3 acres
  4. . 1point 3acres 璁哄潧
  5. 给你一个R*C的数字矩阵,要你找出矩阵中一条递减的最长路径的长度。
  6. 即从矩阵的一个点出发(起点任意),只能走数字递减的上下左右4格中的一格,
  7. 能走的最长距离(包括起点).
  8. */
  9. #include <iostream>
  10. #include <string>. visit 1point3acres.com for more.
  11. #include <set>
  12. #include <map>
  13. #include <unordered_map>. Waral 鍗氬鏈夋洿澶氭枃绔,
  14. #include<vector>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15. #include <queue>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16. #include <unordered_set>
  17. using namespace std;. visit 1point3acres.com for more.

  18. class Solution
  19. {
  20. public:
  21.         /*. 鍥磋鎴戜滑@1point 3 acres
  22.         首先我们令len[r][c]表示从(r,c)点出发的最长路径长度.
  23.     可以知道如下状态转移方程:
  24.     len[r][c]= max(len[r+1][c], len[r-1][c], len[r][c-1],len[r][c+1])+1.
  25.     注意上面的方程转移的条件是(r,c)点的数字比它4个方向的数字都大,如果某个方向不满足该条件,则不可转移.
  26.         */
  27.         int longestPath(vector<vector<int> > &moutain)
  28.         {
  29.                 if(moutain.empty())
  30.                 return 0;
  31.                 int row = moutain.size();
  32.                 int col = moutain[0].size(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  33.         if(row < 1 || col < 1)
  34.             return 0;

  35.                 vector<vector<int> > lenDP(row, vector<int>(col, 0));

  36.                 int longestP = 0;
  37.                 for(int i = 0; i < row; i++)
  38.                 {
  39.                         for(int j = 0; j < col; j++)
  40.                         {
  41.                                 int tmp = dfs(moutain, lenDP, i, j);
  42.                                 longestP = max(longestP, tmp);
  43.                         }
  44.                 }
  45.                 return longestP + 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.         }

  47.         int dfs(vector<vector<int> > &moutain, vector<vector<int> > &lenDP, int r, int c)
  48.         {
  49.                 if(lenDP[r][c] != 0)
  50.                         return lenDP[r][c];
  51. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  52.                 int dr[] = {1,-1,0,0};
  53.                 int dc[] = {0,0,1,-1};. 1point 3acres 璁哄潧
  54.                
  55.                 lenDP[r][c] = 1;
  56.                 for(int k = 0; k < 4; k++)
  57.                 {
  58.                         int newR = r + dr[k];
  59.                         int newC = c + dc[k];
  60.                         if(newR < 0 || newR >= moutain.size() || newC < 0 || newC >= moutain[0].size())
  61.                                 continue;.1point3acres缃

  62.                         if(moutain[r][c] > moutain[newR][newC])
  63.                         {
  64.                                 int tmp = dfs(moutain, lenDP, newR, newC) + 1;
  65.                                 lenDP[r][c] = max(lenDP[r][c], tmp);. 1point3acres.com/bbs
  66.                         }
  67.                 }
  68.                 return lenDP[r][c];
    . From 1point 3acres bbs
  69.         }
  70. };

  71. //int main()
  72. //{
  73. //        vector<vector<int> > mountain;
  74. //        int r1[] = {1,2,3,4,5};
  75. //        vector<int> v1(r1, r1+5);
  76. //        int r2[] = {16,17,18,19,6};
  77. //        vector<int> v2(r2, r2+5);
  78. //        int r3[] = {15,24,25,20,7};;
  79. //        vector<int> v3(r3, r3+5);. visit 1point3acres.com for more.
  80. //        int r4[] = {14,23,22,21,8};;
  81. //        vector<int> v4(r4, r4+5);
  82. //
  83. //        int r5[] = {13,12,11,10,9};;. more info on 1point3acres.com
  84. //        vector<int> v5(r5, r5+5);
  85. //        mountain.push_back(v1);
  86. //        mountain.push_back(v2);
  87. //        mountain.push_back(v3);
  88. //        mountain.push_back(v4);
  89. //        mountain.push_back(v5);
  90. //
  91. //        Solution ss;
  92. //        cout<<ss.longestPath(mountain);
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  93. //        int i = 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
  94. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:58:52 | 显示全部楼层
  1. /*.1point3acres缃
  2. good number问题。 一个数如果能用(至少两组)两个立方数相加得到那么就是good number。
  3. print 小于等于n的所有good number。. Waral 鍗氬鏈夋洿澶氭枃绔,
  4. 分析时间复杂度。我先把小于n的所有立方数存起来。然后就变成了2 sum问题了。。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  5. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6. */

  7. #include <vector>
  8. #include <iostream>. Waral 鍗氬鏈夋洿澶氭枃绔,
  9. #include <algorithm>. 1point3acres.com/bbs
  10. #include <math.h>
  11. using namespace std;

  12. class Solution
  13. {
  14. public:
  15.         //k次方,如,k=2,或3
  16.         vector<int> getAllGoodNumber(int n, int k). 鍥磋鎴戜滑@1point 3 acres
  17.         {
  18.                 vector<int> res;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.                 if(n < 3)
  20.                         return res;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  21.                 //前面存k方数,后面存数字本身.1point3acres缃
  22.                 vector<pair<int, int> > squareNum(1, make_pair(1,1));
  23. -google 1point3acres
  24.                 for(int i = 2; i <= n; i++)
  25.                 {
  26.                         int t = squareNum[squareNum.size()-1].second;. from: 1point3acres.com/bbs
  27.                         int newSqure = pow(double(t+1), k);
  28.                         if(newSqure <= i)
  29.                                 squareNum.push_back(make_pair(newSqure, t+1));
  30. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  31.                         if(getTwoMoreSquareSum(i, squareNum)). Waral 鍗氬鏈夋洿澶氭枃绔,
  32.                                 res.push_back(i);. visit 1point3acres.com for more.
  33.                 }
  34.                 return res;
  35.         }. 鍥磋鎴戜滑@1point 3 acres

  36.         bool getTwoMoreSquareSum(int digit, vector<pair<int, int> >& squareNum)
  37.         {
  38.                 int left = 0, right = squareNum.size()-1;
  39.                 int count = 0;
  40.                 while(left <= right)
  41.                 {
  42.                         int sum = squareNum[left].first + squareNum[right].first;
  43.                         if(sum == digit)
  44.                                 count++, left++, right--;. Waral 鍗氬鏈夋洿澶氭枃绔,
  45.                         else if(sum < digit)
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  46.                                 left++;
  47.                         else
  48.                                 right --;. Waral 鍗氬鏈夋洿澶氭枃绔,
  49.                                
  50.                         if(count >= 2)
  51.                                 break;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  52.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  53.                 return (count >= 2);. 鍥磋鎴戜滑@1point 3 acres
  54.         }
  55. };
  56. . 1point3acres.com/bbs
  57. //int main()
  58. //{
  59. //        vector<int> res;
  60. //        Solution ss;
  61. //        res = ss.getAllGoodNumber(100000,3);
  62. //        int i = 0;
  63. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 10:01:04 | 显示全部楼层
  1. leetcode的变型,Given a stream, find thelongest substring with exact M distinct characters.
  2. 例如,M = 3, S = "abcddd", 那longest substring = "bcddd",我用的sliding window方法.

  3. class Solution { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4. public:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5.     int lengthOfLongestSubstringTwoDistinct(string s) {
  6.         if(s.size() < 1)
  7.             return 0;
  8.         
  9.         int N = 2;
  10.         int left = 0;
  11.         int right = 0;
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.         int maxLen = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.         map<char, int> mp;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  14.         for(; right < s.size(); right++)
  15.         {
  16.             if(mp.count(s[right]) > 0) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.                 mp[s[right]]++;. more info on 1point3acres.com
  18.             else
  19.             {. From 1point 3acres bbs
  20.                 if(mp.size() == N)
  21.                 {
  22.                     while(mp[s[left]] > 0)
  23.                     {
  24.                         mp[s[left]] --;
  25.                         if(mp[s[left]] == 0)
  26.                         {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.                             mp.erase(s[left]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.                             left++;
  29.                             break;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.                         }
  31.                         left ++;
  32.                     }
  33.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  34.                 mp[s[right]] = 1;
  35.             }
  36.             maxLen = max(right - left + 1, maxLen);
  37.         }
  38.        .鏈枃鍘熷垱鑷1point3acres璁哄潧
  39.         if(maxLen < s.size() + 1)
  40.             return maxLen;
  41.         else
  42.             return 0;. more info on 1point3acres.com
  43.     }
  44. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 10:09:28 | 显示全部楼层
  1. /*. 鍥磋鎴戜滑@1point 3 acres
  2. find the most popular number in an array of interger.
  3. The 'popular number' is defined as the number occurs more than n/4, . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4. where n is the length of array. The array is already sorted.
  5. */
  6. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  7. #include <iostream>
  8. #include <map>
  9. #include <set>
  10. #include <unordered_map>
  11. #include <unordered_set>
  12. #include <stack>
  13. #include<vector>
  14. using namespace std;

  15. class Solution
  16. {
  17. public:
  18.         vector<int> getPopularDigits(vector<int> arr). From 1point 3acres bbs
  19.         {
  20.                 vector<int> res;
  21.                 if(arr.size() < 4)
  22.                         return arr;
  23.                 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  24.                 int requreC = arr.size()/4;
  25.                 int left = 0;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26.                 int right = requreC;
  27.                 while(right < arr.size())
  28.                 {
  29.                         if(arr[left] == arr[right])
  30.                         {
  31.                                 //如果没哟下面的判断,case 1,1,1,1,2,结果就会为1,1了,有两个1
  32.                                 if(res.empty() || arr[left] != res[res.size() - 1])
  33.                                         res.push_back(arr[left]);
  34.                                 left = right + 1;.1point3acres缃
  35.                                 right = left + requreC;
  36.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.                         else
  38.                         {
  39.                                 left = getNewLeftIndex(arr, left, right);
  40.                                 right = left + requreC;
  41.                         }
  42.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  43.                 return res;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  44.         }
  45.         .1point3acres缃
  46.         int getNewLeftIndex(vector<int> &arr, int left, int right)
  47.         {-google 1point3acres
  48.                 int target = arr[right];
  49.                 while(1)
  50.                 {
  51.                         int mid = (left + right)/2;
  52.                         if(arr[mid] != target && arr[mid+1] == target).1point3acres缃
  53.                                 return mid+1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  54.                         else if(arr[mid] == target)
  55.                                 right = mid;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  56.                         else
  57.                                 left = mid;
  58.                 }
  59.         }
  60. };
  61. //
  62. //int main()
  63. //{
  64. //        int arr[] = {1,1,1,1,2,2,2,2,3,3,3};
  65. //        int n = sizeof(arr)/sizeof(int);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  66. //        vector<int> v(arr,arr+n);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  67. //        Solution ss;
  68. //        cout<<n/4<<endl;
  69. //        vector<int> res = ss.getPopularDigits(v);
  70. //        map<int, int> mp = ss.getCount(v);
  71. //        int i =0;
  72. //}
复制代码
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-16 10:51:46 | 显示全部楼层

楼主最后一题是用find range做的? 能不能用major element的思想,这样只要O(n), 并且不需要sorted的array也可以?
回复 支持 反对

使用道具 举报

alittlesheep 发表于 2015-9-16 12:18:05 | 显示全部楼层
四面第二题,最优应该是O(1),hashmap+vector洗牌
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 12:18:11 | 显示全部楼层
kelvinzhong 发表于 2015-9-16 10:51
楼主最后一题是用find range做的? 能不能用major element的思想,这样只要O(n), 并且不需要sorted的arra ...

是的,如果题意是没有sorted的话,可以用major来做,是o(n),但是上面的是有序的话,用上面的应该是小于O(n)的复杂度的
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 12:20:58 | 显示全部楼层
alittlesheep 发表于 2015-9-16 12:18
四面第二题,最优应该是O(1),hashmap+vector洗牌

恩,set底层也可以用hashtable来做,所以确实是o(1)的,不过我当时没想到用hashtable,一心想着rb-tree的set
回复 支持 反对

使用道具 举报

alittlesheep 发表于 2015-9-16 12:58:09 | 显示全部楼层
zzwzhong698800 发表于 2015-9-16 12:20
恩,set底层也可以用hashtable来做,所以确实是o(1)的,不过我当时没想到用hashtable,一心想着rb-tree的 ...

lz二面是因为简历的缘故吗,所以问了这么多语言的细节
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-16 13:03:53 | 显示全部楼层
楼主, 序列化和反序列化二叉树 是啥意思啊, 偶是海本, 看部懂

补充内容 (2015-9-16 13:04):
*看不懂。。

补充内容 (2015-9-16 14:37):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
看懂了。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-16 15:10:04 | 显示全部楼层
楼主, 能否具体说说system design 那道题
回复 支持 反对

使用道具 举报

minghang 发表于 2015-9-16 20:14:33 | 显示全部楼层
等楼主好消息。
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 21:29:56 | 显示全部楼层
alittlesheep 发表于 2015-9-16 12:18. From 1point 3acres bbs
四面第二题,最优应该是O(1),hashmap+vector洗牌
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
其实后来想想,不能用vector的,因为popRandom的复杂度为O(n),这个瓶颈就是因为把元素随机pop出去,在vector中就是erase那个下标,所以O(n)就是因为vector erase造成的,所以不能用vector,所以当时我就用把vector去掉,只用一个set就可以了,所以其实如果set的底层是hashtable,那么确实降为了O(1)
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 21:30:44 | 显示全部楼层
alittlesheep 发表于 2015-9-16 12:58
lz二面是因为简历的缘故吗,所以问了这么多语言的细节

并没有,简历就是正常的,说自己会c++/C,然后就问了这些,在malloc,new,内存分配上问了很久很久
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 21:44:20 | 显示全部楼层
hulahu 发表于 2015-9-16 15:10
楼主, 能否具体说说system design 那道题

这个其实也没什么好说的,因为感觉系统设计这东东完全看题目怎么出,然后面试官怎么提示了,要不然自己完全没思路。
就是一个订票系统,每个人只能一次看10个seats,不同人不能看范围有重合的10个seats。如果2分钟不定票就会退出订票的系统,就这些要求。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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