一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 3121|回复: 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四轮-google 1point3acres
电面:
1. 序列化和反序列化二叉树
2. 求字符串中最长的总共不相同字符个数不超过M的最长子串长度。
国人小哥,北京打来的电话,人很nice,虽然我磕磕绊绊,两道题还是做出来了,虽然被小哥一直提醒这有bug,那有bug的。面完之后我以为跪了,结果下午hr就打电话邀请我onsite,让我很惊喜。-google 1point3acres

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)了,然后就结束了,随便问了几个问题。. 鍥磋鎴戜滑@1point 3 acres
over………………………………

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

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


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

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

补充内容 (2015-9-17 17:27):
可能我还没抓到点,可能也还是我太弱了,至少他们是这么感觉的。.鐣欏璁哄潧-涓浜-涓夊垎鍦

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

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

评分

19

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:52:28 | 显示全部楼层
  1. /*
  2. 一个数组,可在数中间插入+或-,输出所有可能的结果。  . Waral 鍗氬鏈夋洿澶氭枃绔,
  3. 如input:[1, 2, 3]  可能的结果是:1+2+3=6, 1+2-3=0, 1-2+3=2, 1-2-3=-4   
  4. */

  5. #include <iostream>
  6. #include <string>
  7. #include <set>
  8. #include <climits>
  9. #include <cmath>
  10. #include <stack>
  11. #include <algorithm>
  12. #include<vector>
  13. using namespace std;. 1point 3acres 璁哄潧

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

  24.                 vector<int> res;
  25.                 set<int> cur;
  26.                 cur.insert(arr[0]);
  27.                 for(int i = 1; i < arr.size(); i++)
  28.                 {
  29.                         set<int> next;. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.                         set<int>::iterator setItr = cur.begin();
  31.                         for(; setItr != cur.end(); setItr++).鏈枃鍘熷垱鑷1point3acres璁哄潧
  32.                         {
  33.                                 int d = *setItr;
  34.                                 int plusRes = d + arr[i];. visit 1point3acres.com for more.
  35.                                 int subRes = d - arr[i];
  36.                                 next.insert(plusRes);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  37.                                 next.insert(subRes);
  38.                         }. from: 1point3acres.com/bbs
  39.                         cur.clear();
  40.                         cur = next;
  41.                 }

  42.                 set<int>::iterator setItr = cur.begin();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  43.                 for(; setItr != cur.end(); setItr++)
  44.                         res.push_back(*setItr);
  45.                 return res;
  46.         }
  47. };

  48. //int main()
  49. //{
  50. //        int a[] = {1,2,3,4};
  51. //        int n = sizeof(a)/sizeof(int);
  52. //        vector<int> v(a, a+n);
  53. // 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  54. //        Solution ss;
  55. //        vector<int> res = ss.calculate(v);
  56. //        int i = 0;
  57. //}
复制代码
回复 支持 反对

使用道具 举报

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

  5. #include <iostream>
  6. #include <string>
  7. #include <sstream>.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8. #include <unordered_set>
  9. #include <algorithm>
  10. #include<vector>. 1point3acres.com/bbs
  11. #include <map>. visit 1point3acres.com for more.
  12. using namespace std;. 鍥磋鎴戜滑@1point 3 acres

  13. class Solution {
  14. public:
  15.         int maxResWithPlusAndMul(vector<int> &arr). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.         {
  17.                 int maxR = INT_MIN;. more info on 1point3acres.com
  18.                 helper(arr, 0, arr.size() - 1, maxR);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.                 return maxR;
  20.         }
  21.         vector<int> helper(vector<int> &arr, int left, int right, int &maxR)
  22.         {
  23.                 vector<int> res;
  24.                 if(left > right).鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.                 {
  26.                         return res;
  27.                 }. from: 1point3acres.com/bbs
  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. . Waral 鍗氬鏈夋洿澶氭枃绔,
  39.                         int larger = INT_MIN;
  40.                         int smaller = INT_MAX;
  41.                         for(int i = 0; i < 2; i++)
  42.                         {
  43.                                 for(int j = 0; j < 2; j++). from: 1point3acres.com/bbs
  44.                                 {
  45.                                         int t1 = leftAns[i] * rightAns[j];
  46.                                         int t2 = leftAns[i] + rightAns[j];
  47.                                         larger = max(max(larger, t1), t2);. more info on 1point3acres.com
  48.                                         smaller = min(min(smaller, t2), t2);
  49.                                 }
  50.                         }

  51.                         res.push_back(smaller);
  52.                         res.push_back(larger);
  53. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  54.                         maxR = max(maxR, larger);
  55.                 }
  56.                 return res;
  57.         }
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  58. };

  59. //int main()
  60. //{
  61. //        int arr[] = {1, -2, -3};
  62. //        int n = sizeof(arr)/sizeof(int);
  63. //        vector<int> v(arr, arr+n);
  64. //        Solution ss;
  65. //        cout<<ss.maxResWithPlusAndMul(v);
  66. //        int i = 0;
  67. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:56:37 | 显示全部楼层
  1. /*. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2. http://blog.csdn.net/u013480600/article/details/27558813
  3. 滑雪(DFS+DP)

  4. 给你一个R*C的数字矩阵,要你找出矩阵中一条递减的最长路径的长度。
  5. 即从矩阵的一个点出发(起点任意),只能走数字递减的上下左右4格中的一格,. 1point 3acres 璁哄潧
  6. 能走的最长距离(包括起点).
  7. */
  8. #include <iostream>
  9. #include <string>
  10. #include <set>
  11. #include <map>. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12. #include <unordered_map>
  13. #include<vector>
  14. #include <queue>
  15. #include <unordered_set>
  16. using namespace std;

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

  32.         if(row < 1 || col < 1). from: 1point3acres.com/bbs
  33.             return 0;

  34.                 vector<vector<int> > lenDP(row, vector<int>(col, 0));. 1point3acres.com/bbs
  35. . From 1point 3acres bbs
  36.                 int longestP = 0;. 1point3acres.com/bbs
  37.                 for(int i = 0; i < row; i++)
  38.                 {
  39.                         for(int j = 0; j < col; j++). visit 1point3acres.com for more.
  40.                         {
  41.                                 int tmp = dfs(moutain, lenDP, i, j);
  42.                                 longestP = max(longestP, tmp);
  43.                         }
  44.                 }
  45.                 return longestP + 1;
  46.         }

  47.         int dfs(vector<vector<int> > &moutain, vector<vector<int> > &lenDP, int r, int c). from: 1point3acres.com/bbs
  48.         {. more info on 1point3acres.com
  49.                 if(lenDP[r][c] != 0)
  50.                         return lenDP[r][c];

  51.                 int dr[] = {1,-1,0,0};. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  52.                 int dc[] = {0,0,1,-1};
  53.                
  54.                 lenDP[r][c] = 1;
  55.                 for(int k = 0; k < 4; k++)
  56.                 {
  57.                         int newR = r + dr[k];
  58.                         int newC = c + dc[k];
  59.                         if(newR < 0 || newR >= moutain.size() || newC < 0 || newC >= moutain[0].size())
  60.                                 continue;

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

  70. //int main()
  71. //{. 1point3acres.com/bbs
  72. //        vector<vector<int> > mountain;
  73. //        int r1[] = {1,2,3,4,5};
  74. //        vector<int> v1(r1, r1+5);
    . From 1point 3acres bbs
  75. //        int r2[] = {16,17,18,19,6};
  76. //        vector<int> v2(r2, r2+5);. more info on 1point3acres.com
  77. //        int r3[] = {15,24,25,20,7};;
  78. //        vector<int> v3(r3, r3+5);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  79. //        int r4[] = {14,23,22,21,8};;
  80. //        vector<int> v4(r4, r4+5);
  81. //
  82. //        int r5[] = {13,12,11,10,9};;. 1point3acres.com/bbs
  83. //        vector<int> v5(r5, r5+5);
  84. //        mountain.push_back(v1);
  85. //        mountain.push_back(v2);
  86. //        mountain.push_back(v3);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  87. //        mountain.push_back(v4);-google 1point3acres
  88. //        mountain.push_back(v5);
  89. //. 1point3acres.com/bbs
  90. //        Solution ss;
  91. //        cout<<ss.longestPath(mountain);
  92. //        int i = 0;
  93. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:58:52 | 显示全部楼层
  1. /*
  2. good number问题。 一个数如果能用(至少两组)两个立方数相加得到那么就是good number。
  3. print 小于等于n的所有good number。
  4. 分析时间复杂度。我先把小于n的所有立方数存起来。然后就变成了2 sum问题了。。。

  5. */

  6. #include <vector>
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <math.h>. from: 1point3acres.com/bbs
  10. using namespace std;

  11. class Solution
  12. {
  13. public:
  14.         //k次方,如,k=2,或3
  15.         vector<int> getAllGoodNumber(int n, int k)
  16.         {
  17.                 vector<int> res; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.                 if(n < 3). from: 1point3acres.com/bbs
  19.                         return res;

  20.                 //前面存k方数,后面存数字本身
  21.                 vector<pair<int, int> > squareNum(1, make_pair(1,1));

  22.                 for(int i = 2; i <= n; i++)
  23.                 {
  24.                         int t = squareNum[squareNum.size()-1].second;
  25.                         int newSqure = pow(double(t+1), k);
  26.                         if(newSqure <= i). 鍥磋鎴戜滑@1point 3 acres
  27.                                 squareNum.push_back(make_pair(newSqure, t+1));

  28.                         if(getTwoMoreSquareSum(i, squareNum)). Waral 鍗氬鏈夋洿澶氭枃绔,
  29.                                 res.push_back(i);
  30.                 }
  31.                 return res;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  32.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  33.         bool getTwoMoreSquareSum(int digit, vector<pair<int, int> >& squareNum)
  34.         {
  35.                 int left = 0, right = squareNum.size()-1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  36.                 int count = 0;
  37.                 while(left <= right)
  38.                 {
  39.                         int sum = squareNum[left].first + squareNum[right].first;
  40.                         if(sum == digit).鐣欏璁哄潧-涓浜-涓夊垎鍦
  41.                                 count++, left++, right--;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  42.                         else if(sum < digit)
  43.                                 left++;
  44.                         else
  45.                                 right --;
  46.                                
    .1point3acres缃
  47.                         if(count >= 2)
  48.                                 break;
  49.                 }
  50.                 return (count >= 2);
  51.         }.1point3acres缃
  52. };
  53. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  54. //int main()
  55. //{. from: 1point3acres.com/bbs
  56. //        vector<int> res;
  57. //        Solution ss;
  58. //        res = ss.getAllGoodNumber(100000,3);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  59. //        int i = 0;
  60. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| 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. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4. class Solution {
  5. public:
  6.     int lengthOfLongestSubstringTwoDistinct(string s) {
  7.         if(s.size() < 1)
  8.             return 0;
  9.         
  10.         int N = 2;.1point3acres缃
  11.         int left = 0;
  12.         int right = 0;
  13.         int maxLen = 0;
  14.         map<char, int> mp;

  15.         for(; right < s.size(); right++)
  16.         {
  17.             if(mp.count(s[right]) > 0)
  18.                 mp[s[right]]++;
  19.             else. 1point 3acres 璁哄潧
  20.             {
  21.                 if(mp.size() == N)
  22.                 {
  23.                     while(mp[s[left]] > 0)
  24.                     {
  25.                         mp[s[left]] --;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  26.                         if(mp[s[left]] == 0)
  27.                         {
  28.                             mp.erase(s[left]);
  29.                             left++;
  30.                             break;
  31.                         }
  32.                         left ++;.1point3acres缃
  33.                     }. 鍥磋鎴戜滑@1point 3 acres
  34.                 }
  35.                 mp[s[right]] = 1;
  36.             }
  37.             maxLen = max(right - left + 1, maxLen);
  38.         }. more info on 1point3acres.com
  39.       
  40.         if(maxLen < s.size() + 1)-google 1point3acres
  41.             return maxLen;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  42.         else
  43.             return 0;. From 1point 3acres bbs
  44.     }
  45. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 10:09:28 | 显示全部楼层
  1. /*
  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. #include <iostream>
  7. #include <map>
  8. #include <set>
  9. #include <unordered_map>
  10. #include <unordered_set>. From 1point 3acres bbs
  11. #include <stack>. visit 1point3acres.com for more.
  12. #include<vector>
  13. using namespace std;. Waral 鍗氬鏈夋洿澶氭枃绔,
  14. . 1point3acres.com/bbs
  15. class Solution
  16. {
  17. public:
  18.         vector<int> getPopularDigits(vector<int> arr)
  19.         {
  20.                 vector<int> res;
  21.                 if(arr.size() < 4). from: 1point3acres.com/bbs
  22.                         return arr;
  23.                
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  24.                 int requreC = arr.size()/4;
  25.                 int left = 0;
  26.                 int right = requreC;
  27.                 while(right < arr.size()). 1point 3acres 璁哄潧
  28.                 {
  29.                         if(arr[left] == arr[right])
  30.                         {
  31.                                 //如果没哟下面的判断,case 1,1,1,1,2,结果就会为1,1了,有两个1.1point3acres缃
  32.                                 if(res.empty() || arr[left] != res[res.size() - 1])
  33.                                         res.push_back(arr[left]);
  34.                                 left = right + 1;
  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.        
  46.         int getNewLeftIndex(vector<int> &arr, int left, int right). 鍥磋鎴戜滑@1point 3 acres
  47.         {
  48.                 int target = arr[right];
  49.                 while(1)
  50.                 {
  51.                         int mid = (left + right)/2;
  52.                         if(arr[mid] != target && arr[mid+1] == target)
  53.                                 return mid+1;
  54.                         else if(arr[mid] == target)
  55.                                 right = mid;
  56.                         else.1point3acres缃
  57.                                 left = mid;
  58.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  59.         }
  60. };
  61. //. Waral 鍗氬鏈夋洿澶氭枃绔,
  62. //int main()
  63. //{
  64. //        int arr[] = {1,1,1,1,2,2,2,2,3,3,3};. from: 1point3acres.com/bbs
  65. //        int n = sizeof(arr)/sizeof(int);
  66. //        vector<int> v(arr,arr+n);
  67. //        Solution ss;. more info on 1point3acres.com
  68. //        cout<<n/4<<endl; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  69. //        vector<int> res = ss.getPopularDigits(v);
  70. //        map<int, int> mp = ss.getCount(v);
  71. //        int i =0;. more info on 1point3acres.com
  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
四面第二题,最优应该是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, 2017-1-18 07:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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