一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 4302|回复: 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的最长子串长度。
.鏈枃鍘熷垱鑷1point3acres璁哄潧国人小哥,北京打来的电话,人很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………………………………. From 1point 3acres bbs

还没出结果,坐等hr电话中,发个面经,求过。
我的面经真的不足以为例,我觉得太简单了…………不是我牛,是真的很简单…………我刷了leetcode+cc150+剑指offer+编程之美,刷了3遍,结果一个都没碰上,代码电面写了两道,onsite总共写了3道…………木有recursion,木有dfs,木有bfs,木有dp,什么都木有.1point3acres缃
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
还是很忐忑的等hr的feedback中,我待会会把最近在地里收集到的面经以及自己写的答案代码发上来,求攒rp!


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

补充内容 (2015-9-17 17:27):. more info on 1point3acres.com
刚收到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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
下面我会把我在地里搜集到的面经题,以及自己的解法都放上来,大部分都是自己写的,所以也可能有错误,大家参考参考。
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:52:28 | 显示全部楼层
关注一亩三分地微博:
Warald
  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. #include <iostream>
  6. #include <string>
  7. #include <set>
  8. #include <climits>
  9. #include <cmath>
  10. #include <stack>. Waral 鍗氬鏈夋洿澶氭枃绔,
  11. #include <algorithm>
  12. #include<vector>
  13. using namespace std;
  14. . 鍥磋鎴戜滑@1point 3 acres
  15. class Solution
  16. {
  17. public:
  18.         //注意题意只有+和-,所以肯定是顺序执行的,没有优先级一说,也没有加括号
  19.         //所以不需要DFS,不需要分治来考虑
  20.         //如果有*或/,或者有(),则需要分治,因为计算的顺序改变了,不是单纯的从左到右
  21.         vector<int> calculate(vector<int> arr)-google 1point3acres
  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++)
  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];
  36.                                 int subRes = d - arr[i];. more info on 1point3acres.com
  37.                                 next.insert(plusRes);
  38.                                 next.insert(subRes);
  39.                         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  40.                         cur.clear();
  41.                         cur = next;
  42.                 }
  43. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  44.                 set<int>::iterator setItr = cur.begin();
  45.                 for(; setItr != cur.end(); setItr++)
  46.                         res.push_back(*setItr);. From 1point 3acres bbs
  47.                 return res;
  48.         }
  49. };. from: 1point3acres.com/bbs
  50. . from: 1point3acres.com/bbs
  51. //int main()
  52. //{
  53. //        int a[] = {1,2,3,4};
  54. //        int n = sizeof(a)/sizeof(int);
  55. //        vector<int> v(a, a+n);
  56. //
  57. //        Solution ss;
  58. //        vector<int> res = ss.calculate(v);
  59. //        int i = 0;
  60. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:53:33 | 显示全部楼层
  1. /*
  2. 给一个数字的array,两个数字间只用+或者* 算出最大的值. from: 1point3acres.com/bbs
  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;. 1point3acres.com/bbs

  13. class Solution {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14. public: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.         int maxResWithPlusAndMul(vector<int> &arr)
  16.         {
  17.                 int maxR = INT_MIN;
  18.                 helper(arr, 0, arr.size() - 1, maxR);
  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). 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++). from: 1point3acres.com/bbs
  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;
    . visit 1point3acres.com for more.
  40.                         for(int i = 0; i < 2; i++)
  41.                         {-google 1point3acres
  42.                                 for(int j = 0; j < 2; j++)
  43.                                 {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.                                         int t1 = leftAns[i] * rightAns[j];
  45.                                         int t2 = leftAns[i] + rightAns[j];. visit 1point3acres.com for more.
  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);.1point3acres缃
  53.                 }
  54.                 return res;
  55.         }
  56. };
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  57. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  58. //int main()
  59. //{. from: 1point3acres.com/bbs
  60. //        int arr[] = {1, -2, -3};. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  61. //        int n = sizeof(arr)/sizeof(int);
  62. //        vector<int> v(arr, arr+n);.1point3acres缃
  63. //        Solution ss;
  64. //        cout<<ss.maxResWithPlusAndMul(v);
  65. //        int i = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  66. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| 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格中的一格,
  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;. from: 1point3acres.com/bbs
  17. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18. class Solution
  19. {
  20. public:
  21.         /*
  22.         首先我们令len[r][c]表示从(r,c)点出发的最长路径长度.. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.     可以知道如下状态转移方程:. from: 1point3acres.com/bbs
  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();-google 1point3acres

  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.                         {. Waral 鍗氬鏈夋洿澶氭枃绔,
  41.                                 int tmp = dfs(moutain, lenDP, i, j);
  42.                                 longestP = max(longestP, tmp);
  43.                         }
  44.                 }
  45.                 return longestP + 1;
  46.         }
  47. . visit 1point3acres.com for more.
  48.         int dfs(vector<vector<int> > &moutain, vector<vector<int> > &lenDP, int r, int c)
  49.         {
  50.                 if(lenDP[r][c] != 0). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  51.                         return lenDP[r][c];

  52.                 int dr[] = {1,-1,0,0};
  53.                 int dc[] = {0,0,1,-1};
  54.                 . 1point 3acres 璁哄潧
  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;

  62.                         if(moutain[r][c] > moutain[newR][newC]). From 1point 3acres bbs
  63.                         {
  64.                                 int tmp = dfs(moutain, lenDP, newR, newC) + 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  65.                                 lenDP[r][c] = max(lenDP[r][c], tmp);
  66.                         }
  67.                 }. 1point3acres.com/bbs
  68.                 return lenDP[r][c];
  69.         }
  70. };
  71. . 鍥磋鎴戜滑@1point 3 acres
  72. //int main(). Waral 鍗氬鏈夋洿澶氭枃绔,
  73. //{
  74. //        vector<vector<int> > mountain;
  75. //        int r1[] = {1,2,3,4,5};
  76. //        vector<int> v1(r1, r1+5);
  77. //        int r2[] = {16,17,18,19,6};
  78. //        vector<int> v2(r2, r2+5);
  79. //        int r3[] = {15,24,25,20,7};;
  80. //        vector<int> v3(r3, r3+5);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  81. //        int r4[] = {14,23,22,21,8};;
  82. //        vector<int> v4(r4, r4+5);
  83. //
  84. //        int r5[] = {13,12,11,10,9};;
  85. //        vector<int> v5(r5, r5+5);
  86. //        mountain.push_back(v1);
  87. //        mountain.push_back(v2);
  88. //        mountain.push_back(v3);
  89. //        mountain.push_back(v4);
  90. //        mountain.push_back(v5);. From 1point 3acres bbs
  91. //. more info on 1point3acres.com
  92. //        Solution ss;
  93. //        cout<<ss.longestPath(mountain);
  94. //        int i = 0;
  95. //}
复制代码
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| 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>
  10. using namespace std;
  11. . 鍥磋鎴戜滑@1point 3 acres
  12. class Solution
  13. {
  14. public:
  15.         //k次方,如,k=2,或3
  16.         vector<int> getAllGoodNumber(int n, int k)
  17.         {
  18.                 vector<int> res;
  19.                 if(n < 3)
  20.                         return res;.1point3acres缃

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

  23.                 for(int i = 2; i <= n; i++)
    . 1point3acres.com/bbs
  24.                 {
  25.                         int t = squareNum[squareNum.size()-1].second;
  26.                         int newSqure = pow(double(t+1), k);
  27.                         if(newSqure <= i)
  28.                                 squareNum.push_back(make_pair(newSqure, t+1));

  29.                         if(getTwoMoreSquareSum(i, squareNum))
  30.                                 res.push_back(i);
  31.                 }
  32.                 return res; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  33.         }.1point3acres缃

  34.         bool getTwoMoreSquareSum(int digit, vector<pair<int, int> >& squareNum)
  35.         {
  36.                 int left = 0, right = squareNum.size()-1;
  37.                 int count = 0;
  38.                 while(left <= right). 1point3acres.com/bbs
  39.                 {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  40.                         int sum = squareNum[left].first + squareNum[right].first;
  41.                         if(sum == digit)
  42.                                 count++, left++, right--;
  43.                         else if(sum < digit)
  44.                                 left++;
  45.                         else
  46.                                 right --;
  47.                                
  48.                         if(count >= 2)
  49.                                 break;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  50.                 }
  51.                 return (count >= 2);
  52.         }
  53. };. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  54. //int main()
  55. //{
  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. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  4. class Solution {
  5. public:
  6.     int lengthOfLongestSubstringTwoDistinct(string s) {
  7.         if(s.size() < 1)
    . From 1point 3acres bbs
  8.             return 0;. 鍥磋鎴戜滑@1point 3 acres
  9.         
  10.         int N = 2;
  11.         int left = 0;. 1point3acres.com/bbs
  12.         int right = 0;
  13.         int maxLen = 0;
  14.         map<char, int> mp;

  15.         for(; right < s.size(); right++). visit 1point3acres.com for more.
  16.         {
  17.             if(mp.count(s[right]) > 0)
  18.                 mp[s[right]]++;
  19.             else. 1point3acres.com/bbs
  20.             {
  21.                 if(mp.size() == N)
  22.                 {
  23.                     while(mp[s[left]] > 0). 鍥磋鎴戜滑@1point 3 acres
  24.                     {
  25.                         mp[s[left]] --;. visit 1point3acres.com for more.
  26.                         if(mp[s[left]] == 0)
  27.                         {
  28.                             mp.erase(s[left]);
  29.                             left++;
  30.                             break;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.                         }
  32.                         left ++;
  33.                     }
  34.                 }
  35.                 mp[s[right]] = 1;
  36.             }
  37.             maxLen = max(right - left + 1, maxLen);
  38.         }. 1point3acres.com/bbs
  39.       
  40.         if(maxLen < s.size() + 1). 1point 3acres 璁哄潧
  41.             return maxLen;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  42.         else
  43.             return 0;
  44.     }. from: 1point3acres.com/bbs
  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. */.鏈枃鍘熷垱鑷1point3acres璁哄潧

  6. #include <iostream>-google 1point3acres
  7. #include <map>
  8. #include <set>. from: 1point3acres.com/bbs
  9. #include <unordered_map>
  10. #include <unordered_set>
  11. #include <stack>
  12. #include<vector>-google 1point3acres
  13. using namespace std;

  14. .1point3acres缃
  15. class Solution
  16. {. more info on 1point3acres.com
  17. public:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.         vector<int> getPopularDigits(vector<int> arr)
  19.         {
  20.                 vector<int> res;. more info on 1point3acres.com
  21.                 if(arr.size() < 4)
  22.                         return arr;
  23.                
  24.                 int requreC = arr.size()/4;. 1point 3acres 璁哄潧
  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;
  35.                                 right = left + requreC;
  36.                         }
  37.                         else
  38.                         {
  39.                                 left = getNewLeftIndex(arr, left, right);
  40.                                 right = left + requreC;
  41.                         }
  42.                 }
  43.                 return res;. from: 1point3acres.com/bbs
  44.         }
  45.         . from: 1point3acres.com/bbs
  46.         int getNewLeftIndex(vector<int> &arr, int left, int right)
  47.         {. Waral 鍗氬鏈夋洿澶氭枃绔,
  48.                 int target = arr[right];
  49.                 while(1)
    . 1point3acres.com/bbs
  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
  57.                                 left = mid; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  58.                 }
  59.         }. 鍥磋鎴戜滑@1point 3 acres
  60. };. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  61. //
  62. //int main()
  63. //{. more info on 1point3acres.com
  64. //        int arr[] = {1,1,1,1,2,2,2,2,3,3,3};
  65. //        int n = sizeof(arr)/sizeof(int);
    . 1point 3acres 璁哄潧
  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.鏈枃鍘熷垱鑷1point3acres璁哄潧
四面第二题,最优应该是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的 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
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二面是因为简历的缘故吗,所以问了这么多语言的细节
. 1point3acres.com/bbs
并没有,简历就是正常的,说自己会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-4-24 08:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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