May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

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

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

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

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

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

x
9月2日的电面,15号的onsite的,本人在北京,想肉身翻墙,就报了usa的Google,师兄给内推的,2号的电面,15号的onsite四轮. more info on 1point3acres.com
电面:
1. 序列化和反序列化二叉树-google 1point3acres
2. 求字符串中最长的总共不相同字符个数不超过M的最长子串长度。
国人小哥,北京打来的电话,人很nice,虽然我磕磕绊绊,两道题还是做出来了,虽然被小哥一直提醒这有bug,那有bug的。面完之后我以为跪了,结果下午hr就打电话邀请我onsite,让我很惊喜。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
onsite:. 1point3acres.com/bbs
我能说很简单麽…………不知道是大家都这样,还是我上辈子积了太多德,题目真的好简单……四个面试官都是米国飞过来的
一轮,印度小哥,态度不算差,都还是有说有笑,题目竟然是电面的第二题…………还是那个不相同字符个数不超过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!
. from: 1point3acres.com/bbs

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

补充内容 (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 | 显示全部楼层
关注一亩三分地公众号:
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    -google 1point3acres
  4. */

  5. #include <iostream>. 1point3acres.com/bbs
  6. #include <string>
  7. #include <set>
  8. #include <climits>
  9. #include <cmath>
  10. #include <stack>
  11. #include <algorithm>-google 1point3acres
  12. #include<vector>
  13. using namespace std;

  14. class Solution. Waral 鍗氬鏈夋洿澶氭枃绔,
  15. {
  16. public:
  17.         //注意题意只有+和-,所以肯定是顺序执行的,没有优先级一说,也没有加括号
  18.         //所以不需要DFS,不需要分治来考虑
  19.         //如果有*或/,或者有(),则需要分治,因为计算的顺序改变了,不是单纯的从左到右
  20.         vector<int> calculate(vector<int> arr). 鍥磋鎴戜滑@1point 3 acres
  21.         {. from: 1point3acres.com/bbs
  22.                 if(arr.size() < 2)
  23.                         return vector<int>();. 1point 3acres 璁哄潧
  24. .1point3acres缃
  25.                 vector<int> res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.                 set<int> cur;
  27.                 cur.insert(arr[0]);
    . visit 1point3acres.com for more.
  28.                 for(int i = 1; i < arr.size(); i++). Waral 鍗氬鏈夋洿澶氭枃绔,
  29.                 {
  30.                         set<int> next;
  31.                         set<int>::iterator setItr = cur.begin();
  32.                         for(; setItr != cur.end(); setItr++)
  33.                         {. From 1point 3acres bbs
  34.                                 int d = *setItr;
  35.                                 int plusRes = d + arr[i];. 鍥磋鎴戜滑@1point 3 acres
  36.                                 int subRes = d - arr[i];
  37.                                 next.insert(plusRes);
  38.                                 next.insert(subRes);
  39.                         }. 1point3acres.com/bbs
  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().1point3acres缃
  50. //{
  51. //        int a[] = {1,2,3,4};
  52. //        int n = sizeof(a)/sizeof(int);
  53. //        vector<int> v(a, a+n);
  54. //
  55. //        Solution ss;
  56. //        vector<int> res = ss.calculate(v);
  57. //        int i = 0;
  58. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 09:53:33 | 显示全部楼层
  1. /*. Waral 鍗氬鏈夋洿澶氭枃绔,
  2. 给一个数字的array,两个数字间只用+或者* 算出最大的值
  3. z下面也可以改为求所有情况 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4. */

  5. #include <iostream>
  6. #include <string>
  7. #include <sstream>
  8. #include <unordered_set>
  9. #include <algorithm>. Waral 鍗氬鏈夋洿澶氭枃绔,
  10. #include<vector>
  11. #include <map>
  12. using namespace std;

  13. class Solution {-google 1point3acres
  14. public:.1point3acres缃
  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;
    .1point3acres缃
  24.                 if(left > right)
  25.                 {. from: 1point3acres.com/bbs
  26.                         return res;
  27.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.                 {. more info on 1point3acres.com
  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++). 1point3acres.com/bbs
  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};. From 1point 3acres bbs
  60. //        int n = sizeof(arr)/sizeof(int);. From 1point 3acres bbs
  61. //        vector<int> v(arr, arr+n);
  62. //        Solution ss;. from: 1point3acres.com/bbs
  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
  3. 滑雪(DFS+DP)

  4. 给你一个R*C的数字矩阵,要你找出矩阵中一条递减的最长路径的长度。. 1point3acres.com/bbs
  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>. more info on 1point3acres.com
  15. #include <unordered_set>
  16. using namespace std;

  17. class Solution
  18. {
  19. public:
  20.         /*
  21.         首先我们令len[r][c]表示从(r,c)点出发的最长路径长度.
  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;
  30.                 int row = moutain.size();
  31.                 int col = moutain[0].size();

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

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

  35.                 int longestP = 0;
  36.                 for(int i = 0; i < row; i++).鐣欏璁哄潧-涓浜-涓夊垎鍦
  37.                 {
  38.                         for(int j = 0; j < col; j++).鏈枃鍘熷垱鑷1point3acres璁哄潧
  39.                         {
  40.                                 int tmp = dfs(moutain, lenDP, i, j);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  41.                                 longestP = max(longestP, tmp);
  42.                         }
  43.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  44.                 return longestP + 1;
  45.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  46. . From 1point 3acres bbs
  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.                 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;. 1point3acres.com/bbs

  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);
  65.                         }
  66.                 }
  67.                 return lenDP[r][c];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  68.         }. 鍥磋鎴戜滑@1point 3 acres
  69. };

  70. //int main()
  71. //{
  72. //        vector<vector<int> > mountain;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  73. //        int r1[] = {1,2,3,4,5};
  74. //        vector<int> v1(r1, r1+5);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  75. //        int r2[] = {16,17,18,19,6};
  76. //        vector<int> v2(r2, r2+5);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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};;
  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);
  88. //        mountain.push_back(v5);
  89. //
  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. */. 1point 3acres 璁哄潧

  6. #include <vector>
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <math.h>
  10. using namespace std;

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

  20.                 //前面存k方数,后面存数字本身
  21.                 vector<pair<int, int> > squareNum(1, make_pair(1,1));
  22. . From 1point 3acres bbs
  23.                 for(int i = 2; i <= n; i++).鐣欏璁哄潧-涓浜-涓夊垎鍦
  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));. From 1point 3acres bbs

  29.                         if(getTwoMoreSquareSum(i, squareNum))
  30.                                 res.push_back(i);
  31.                 }
  32.                 return res;
  33.         }

  34.         bool getTwoMoreSquareSum(int digit, vector<pair<int, int> >& squareNum)
  35.         {
  36.                 int left = 0, right = squareNum.size()-1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  37.                 int count = 0;
  38.                 while(left <= right). from: 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)-google 1point3acres
  44.                                 left++;
  45.                         else
  46.                                 right --;
  47.                                
  48.                         if(count >= 2)
  49.                                 break;
  50.                 }
  51.                 return (count >= 2);
  52.         }
  53. };
  54. . more info on 1point3acres.com
  55. //int main()
  56. //{
  57. //        vector<int> res;
  58. //        Solution ss;
  59. //        res = ss.getAllGoodNumber(100000,3);
  60. //        int i = 0;
  61. //}
复制代码
回复 支持 反对

使用道具 举报

 楼主| zzwzhong698800 发表于 2015-9-16 10:01:04 | 显示全部楼层
  1. leetcode的变型,Given a stream, find thelongest substring with exact M distinct characters..1point3acres缃
  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.         .鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.         int N = 2;
  11.         int left = 0;
  12.         int right = 0;-google 1point3acres
  13.         int maxLen = 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.         map<char, int> mp;
  15. . 鍥磋鎴戜滑@1point 3 acres
  16.         for(; right < s.size(); right++). From 1point 3acres bbs
  17.         {
  18.             if(mp.count(s[right]) > 0)
  19.                 mp[s[right]]++;
  20.             else
  21.             {
  22.                 if(mp.size() == N)
  23.                 {
  24.                     while(mp[s[left]] > 0)
  25.                     {
  26.                         mp[s[left]] --;
  27.                         if(mp[s[left]] == 0)
  28.                         {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  29.                             mp.erase(s[left]);
  30.                             left++;
  31.                             break;
  32.                         }
  33.                         left ++;-google 1point3acres
  34.                     }
  35.                 }
  36.                 mp[s[right]] = 1;
  37.             }
  38.             maxLen = max(right - left + 1, maxLen);
  39.         }
  40.       
  41.         if(maxLen < s.size() + 1)
  42.             return maxLen;
  43.         else
  44.             return 0;
  45.     }
  46. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| 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. -google 1point3acres
  7. #include <iostream>
  8. #include <map>. 1point 3acres 璁哄潧
  9. #include <set>
  10. #include <unordered_map>
  11. #include <unordered_set>
  12. #include <stack>
  13. #include<vector>.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14. using namespace std;. from: 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)
  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;
  35.                                 right = left + requreC;
  36.                         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  37.                         else. 鍥磋鎴戜滑@1point 3 acres
  38.                         {
  39.                                 left = getNewLeftIndex(arr, left, right);. from: 1point3acres.com/bbs
  40.                                 right = left + requreC;
  41.                         }
  42.                 }
  43.                 return res;
  44.         }
  45.        
  46.         int getNewLeftIndex(vector<int> &arr, int left, int right)
  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. visit 1point3acres.com for more.
  57.                                 left = mid;.1point3acres缃
  58.                 }
  59.         }
  60. };
  61. //
  62. //int main()
  63. //{. visit 1point3acres.com for more.
  64. //        int arr[] = {1,1,1,1,2,2,2,2,3,3,3};
  65. //        int n = sizeof(arr)/sizeof(int);. from: 1point3acres.com/bbs
  66. //        vector<int> v(arr,arr+n);
  67. //        Solution ss;. 鍥磋鎴戜滑@1point 3 acres
  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):
*看不懂。。. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (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
. 1point 3acres 璁哄潧四面第二题,最优应该是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分钟不定票就会退出订票的系统,就这些要求。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-23 12:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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