一亩三分地论坛

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

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

10/19 Google onsite

[复制链接] |试试Instant~ |关注本帖
raychien 发表于 2016-11-11 08:41:24 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Pass在职跳槽

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

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

x
Round 1 國人大叔:
給一個 sorted array 和一個 interval [low, high],求連續區間總和介於 interval 之間的可能性有多少種。例如給 2, 3, 5, 7 和 interval [6, 11],返回 2,因為只有兩種可能 [2, 3, 5] 和 [3, 5]。.鐣欏璁哄潧-涓浜-涓夊垎鍦
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Round 2 白人大叔:
設計一個兩人遊戲,給一個字典都是剛好 5 letters 的字,A 從字典裡挑一個字,B 從字典挑字去猜,A 會告訴 B 說你猜對幾個字,但是不會告訴你對的是哪幾個字母。寫兩個 function,一個判定 B 是否猜對,另一個給定上一輪猜的字和 A 的 feedback,從字典裡 narrow down search space。

Round 3 老印:
給一個 tree,每個 node 的 children 數目不固定,寫一個 function 把 tree serialize。之後再寫一個 function 把 tree rebuild 回原本的樣子。follow up: 若不能用特殊符號如何 serialize。

Round 4 白人姊姊:
給一個 class 挑錯,一個一個挑出來改正,有些是 bug,有些是設計不好。第二題 read4K。
. Waral 鍗氬鏈夋洿澶氭枃绔,
Round 5 國人小哥:
寫一個 API,給定一個字典,輸入 prefix,返回所有包含這個 prefix 的字。follow up: 1. 假如空間不夠怎麼辦 2. 如何返回比較熱門的搜尋字 3. 如果輸入有 typo 怎麼辦

--

LZ 第一輪就炸了,題目看起來不難但是寫起來 bug 一堆,debug 到一半時間就到了,導致後面幾輪壓力都很大。最後一輪答的最好,面試官直接說我是他面過寫最好的一個。中間幾輪面的較普通,從面試官表情看不出自己答的好不好。中間無數次寄信 follow up HR 都不理人,最後受不了打過去被告知過了 HC 也是醉了。看來 G 家面試還是看種交流的過程,其中一輪沒答好不必放在心上,好好把握每一輪應該就夠了。

祝福各位面試順利!

评分

1

查看全部评分

zzgzzm 发表于 2016-11-19 22:28:04 | 显示全部楼层
catinclay 发表于 2016-11-19 14:38
那你i>i0的時候不就會把右半邊的範圍變大了嗎?

你说的没错,我短路了。... -_-:
回复 支持 1 反对 0

使用道具 举报

zzgzzm 发表于 2016-11-19 09:46:45 | 显示全部楼层
catinclay 发表于 2016-11-19 01:15. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
res += (upper_bound(i+1, i0, high, greater) - lower_bound(i+1, i0, low, greater));
res += (upp ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
感谢指正! 在更新res时我漏了给high和low "+*i" (这里i的类型是vector<int>::iterator):
  1. res += (upper_bound(i+1, i0, high+*i, greater) - lower_bound(i+1, i0, low+*i, greater));
  2. res += (upper_bound(i0, sum.end(), high+*i) - lower_bound(i0, sum.end(), low+*i);
复制代码
对于iterator i < j, 因为要求:low<= *j-*i<=high,等价于low+*i<=*j<=high+*i
回复 支持 1 反对 0

使用道具 举报

sophie0815 发表于 2016-11-11 14:53:23 | 显示全部楼层
能不能麻烦楼主详细讲下第二题? 我也在其他面经看到这题。 请问在不告诉你是哪个字母猜对的情况下,如何narrow search space ?
回复 支持 反对

使用道具 举报

sophie0815 发表于 2016-11-11 15:00:06 | 显示全部楼层
还有问下楼主最后一问follow up是怎么答得?
1. 空间不够解决方法是放在多个机器吗?   
2. 搜索热门的词语 建个数据库 给每个词count frequency 然后根据frequency 排序吗?
3. 有typo怎么办呀? 没想出来
回复 支持 反对

使用道具 举报

木易wen 发表于 2016-11-11 23:40:44 | 显示全部楼层
lz 的hr是selma么?我这送hc2周了hr也是怎么发邮件都不回
回复 支持 反对

使用道具 举报

 楼主| raychien 发表于 2016-11-12 06:16:04 | 显示全部楼层
sophie0815 发表于 2016-11-11 14:53.鏈枃鍘熷垱鑷1point3acres璁哄潧
能不能麻烦楼主详细讲下第二题? 我也在其他面经看到这题。 请问在不告诉你是哪个字母猜对的情况下,如何na ...

B 每猜一次就可以得到 A 的 feedback,利用這個 feedback 就可以把字典裡不可能的字去掉,然後再隨便猜一個,再把不可能的字去掉,如此循環。最差情況猜到最後字典裡剩一個字了,就一定能猜對。
回复 支持 反对

使用道具 举报

 楼主| raychien 发表于 2016-11-12 06:54:54 | 显示全部楼层
sophie0815 发表于 2016-11-11 15:00
还有问下楼主最后一问follow up是怎么答得?
1. 空间不够解决方法是放在多个机器吗?   
2. 搜索热门的 ...

我覺得 follow up 沒有標準答案,合理就行
1. distributed system. visit 1point3acres.com for more.
2. heap or quick select
3. 查字典裡相似的字,cache 常見 typo

回复 支持 反对

使用道具 举报

 楼主| raychien 发表于 2016-11-12 06:55:38 | 显示全部楼层
木易wen 发表于 2016-11-11 23:40
lz 的hr是selma么?我这送hc2周了hr也是怎么发邮件都不回

不是,貌似狗家 HR 都比較高冷。。。
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-12 11:14:40 | 显示全部楼层
麻烦问一下楼主第一题楼主怎么做的, 如果这个array里面有负数的话, two pointers 好像行不通那? 楼主的时间复杂度是多少
回复 支持 反对

使用道具 举报

xinyukkkk028 发表于 2016-11-12 13:09:15 | 显示全部楼层
请问楼主第二题是要求想function么?排除不可能的除了完全没有重复字母的和重复字母数大于猜对数字的以外,还有别的可以排除吗
回复 支持 反对

使用道具 举报

 楼主| raychien 发表于 2016-11-13 09:49:28 | 显示全部楼层
zhan1612 发表于 2016-11-12 11:14
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴麻烦问一下楼主第一题楼主怎么做的, 如果这个array里面有负数的话, two pointers 好像行不通那? 楼主的 ...

sorted 就用 binary search 吧,複雜度 O(nlogn),應該無法更快了,面試官也同意
回复 支持 反对

使用道具 举报

sophie0815 发表于 2016-11-13 11:20:18 | 显示全部楼层
raychien 发表于 2016-11-12 06:16
B 每猜一次就可以得到 A 的 feedback,利用這個 feedback 就可以把字典裡不可能的字去掉,然後再隨便猜一 ...

这道题可以优化吗?  比如我给dictionary 建个trie 然后根据每次的feedback 去掉某些branch ?
回复 支持 反对

使用道具 举报

 楼主| raychien 发表于 2016-11-13 12:31:40 | 显示全部楼层
xinyukkkk028 发表于 2016-11-12 13:09.1point3acres缃
请问楼主第二题是要求想function么?排除不可能的除了完全没有重复字母的和重复字母数大于猜对数字的以外, ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
這道題基本就是考你如何設計遊戲 API,你想怎麼做都行,合理就好。基本上每輪猜的字要含有上次猜的字才有可能,且個數要一樣,不能多也不能少。
回复 支持 反对

使用道具 举报

 楼主| raychien 发表于 2016-11-13 12:34:02 | 显示全部楼层
sophie0815 发表于 2016-11-13 11:20
这道题可以优化吗?  比如我给dictionary 建个trie 然后根据每次的feedback 去掉某些branch ?

這道題應該跟 trie 沒啥關聯吧
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-13 13:59:51 | 显示全部楼层
Round1: 若这个题的sorted array的条件是不是太强了?其实只要正元素都出现在负元素的后面就可以达到O(N*logN)了吧。我是把array a转化成partial sum array sum[j] = sum[j-1]+a[j-1] with sum[0]=0,那么a[]的连续元素和就一定是sum[j] - sum[\i]其中j>i。 而且sum[]一定是单调的或者先递减再递增的(这个并不需要a一定是sorted)。C++ STL lower_bound 和upper_bound functions对sorted container就是O(logN)的。
  1. int ComboSum(vector<int>& a, int low, int high) {
  2.   if (a.empty() || low > high) return 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.   vector<int> sum(a.size()+1, 0); int res = 0;
  4.   for (int i = 1; i < a.size(); ++i) sum[i] = sum[i-1] + a[i-1];
  5.   auto i0 = sum.begin() + (lower_bound(a.begin(), a.end(), 0)-a.begin());
  6.   auto greater = [](int x, int y) { return x > y; };.鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.   for (auto i = sum.begin(); i != sum.end()-1; ++i) {
  8.     res += (upper_bound(i+1, i0, high, greater) - lower_bound(i+1, i0, low, greater));
  9.     res += (upper_bound(i0, sum.end(), high) - lower_bound(i0, sum.end(), low)); .1point3acres缃
  10.   }
  11.   return res;
  12. }
复制代码

补充内容 (2016-11-19 09:41):
更正: Line8-9: (+*i):
res += (upper_bound(i+1, i0, high+*i, greater) - lower_bound(i+1, i0, low+*i, greater));
res += (upper_bound(i0, sum.end(), high+*i) - lower_bound(i0, sum.end(), low+*i);
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 01:30:32 | 显示全部楼层
Round 2: 这个题目限制了word length=5,所以我估计在function narrowDown中就是暴力搜索每个单词看是不是与guess word的公共letter个数是A给的feedback了?也就是说面试官不要求对字典做任何预处理了?因为如果这个游戏玩很多遍的话,那么这样narrow down是比较慢的,没有考虑单词彼此之间的联系。
我就写了个简单版本:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  1. class WordGame {
  2. private:
  3.   vector<string> _dict;
  4.   int _ansIdx; // index of answer word picked by A
  5.   unordered_map<char, int> _freq; // char frequency of answer word
  6.   
  7.   // calculate A's feedback for a guess word
  8.   int numCommonChars(string& guess) {
  9.     unordered_map<char, int> guessFreq; int res = 0;
  10.     for (char c:guess) guessFreq[c]++;
  11.     for (auto& p:_freq) if (guessFreq.count(p.first)) res += min(p.second, guessFreq[p.first]);
  12.     return res;
  13.   }
  14.   // narrow down search words based on a guess and feedback
  15.   void narrowDown(unordered_set<string>& candidates, string& guess, int feedback) {. more info on 1point3acres.com
  16.     for (auto& w:candidates) {
  17.       if(feedback != numCommonChars(guess, w)) candidates.erase(w);
  18.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.   }. 1point3acres.com/bbs
  20.   
  21.   bool correctGuess(string& guess) { return guess == _dict[_ansIdx]; }

  22. public:
  23.   WordGame(vector<string>& dict):_dict(dict) {
  24.     if (!_dict.size()) { cout << "empty dictionary!\n"; return; }
  25.     _ansIdx = rand()%_dict.size();
  26.   }. 1point3acres.com/bbs
  27.   // make a random guess within candiates and narrow down search candiates
  28.   bool makeAGuess(unordered_set<string>& candidates, string& guess) {
  29.     guess = *candidates.begin(); candidates.erase(guess);
  30.     narrowDown(candidates, guess, numCommonChars(guess));
  31.     return correctGuess(guess);
  32.   }
  33.   // get all guesses sequence by B
  34.   void allGuesses(vector<string>& guesses) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  35.     unordered_set<string> candidates; string guess;
  36.     for (auto& w:_dict) candidates.insert(w);
  37.     while (!makeAGuess(candidates, guess)) { guesses.push_back(guess); }
  38.     guesses.push_back(guess);
  39.   }.1point3acres缃
  40. };
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 02:32:35 | 显示全部楼层
xinyukkkk028 发表于 2016-11-12 13:09. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请问楼主第二题是要求想function么?排除不可能的除了完全没有重复字母的和重复字母数大于猜对数字的以外, ...

先写一个API类似于getNumCommonChars(string s1, string s2),这个很容易。那么当用guess word = w得到的feedback = k (0<=k<=5)时,字典中只有满足getNumCommonChars(w, s)==k的那些s才有可能成为candidates.
回复 支持 反对

使用道具 举报

davidhunter 发表于 2016-11-14 02:47:08 | 显示全部楼层
请问一下楼主timeline.鏈枃鍘熷垱鑷1point3acres璁哄潧
等了多久收到结果的?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 03:21:10 | 显示全部楼层
sophie0815 发表于 2016-11-13 11:20
这道题可以优化吗?  比如我给dictionary 建个trie 然后根据每次的feedback 去掉某些branch ?

我也在想这个题要不要预处理字典。其实就是说这个游戏要不要玩很多次?若是的话预处理字典是肯定的了。但这个游戏只和letter count有关,所以不用Trie (trie和prefix or order有关)。. 鍥磋鎴戜滑@1point 3 acres
关键是每次(尤其是第一次)narrow down字典candidates的时候O(N)复杂度是可以用预处理和空间的代价来做trade-off,相当于在class constructor里cache和每个word有恰好k个相同letter的words是什么(unordered_map<string, vector<unordered_set<string>>>)。这个时间空间都是O(N^2),但是都是在constructor里完成一次性的。只要字典不变,每次游戏重来(A重新生成一个答案)的话不必重新计算。
  1. class WordGame {
    . from: 1point3acres.com/bbs
  2. private:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.   vector<string> _dict;
    -google 1point3acres
  4.   int _ansIdx; // index of answer word picked by A
  5.   // _common[s][k]:= set of words having k common chars with s
  6.   unordered_map<string, vector<unordered_set>> _common;
  7.   
  8.   // calculate number of common chars between s1 and s2
  9.   int numCommonChars(string& s1, string& s2) {
  10.     unordered_map<char, int> freq1, freq2; int res = 0;. 鍥磋鎴戜滑@1point 3 acres
  11.     for (char c:s1) freq1[c]++; for (char c:s2) freq2[c]++;
  12.     if (freq1.size() > freq2.size()) swap(freq1, freq2);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  13.     for (auto& p:freq1) if (freq2.count(p.first)) res += min(p.second, freq2[p.first]);
  14.     return res;. From 1point 3acres bbs
  15.   }
  16.   // narrow down search words based on a guess and feedback
  17.   void narrowDown(unordered_set<string>& candidates, string& guess, int feedback) {
  18.     auto words = _common[guess][feedback];
  19.     if (candidates.size() > words.size()) swap(candidates, words);
  20.     for (auto& w:candidates) {
  21.       if(!words.count(w)) candidates.erase(w);
  22.     }
  23.   }
  24.   
  25.   bool correctGuess(string& guess) { return guess == _dict[_ansIdx]; }. From 1point 3acres bbs
  26.   // make a random guess within candiates and narrow down search candiates
  27.   .鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.   bool makeAGuess(unordered_set<string>& candidates, string& guess) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  29.     guess = *candidates.begin(); candidates.erase(guess);
  30.     narrowDown(candidates, guess, numCommonChars(_dict[_ansIdx], guess));-google 1point3acres
  31.     return correctGuess(guess);
  32.   }
  33.   
  34. public:
  35.   WordGame(vector<string>& dict):_dict(dict) { // O(N^2)
  36.     if (!_dict.size()) { cout << "empty dictionary!\n"; return; }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  37.     _ansIdx = rand()%_dict.size(); // geneerate a random answer
  38.     for (int i = 0; i < _dict.size()-1; ++i)
  39.     for (int j = i+1; j < _dict.size()-1; ++j) {
  40.       int k = numCommonChars(_dict[i], _dict[j]);
  41.       _common[_dict[i]][k].insert(_dict[j]);
  42.       _common[_dict[j]][k].insert(_dict[i]);
  43.     }
    -google 1point3acres
  44.   }

  45.   // get all guesses sequence by B
  46.   void allGuesses(vector<string>& guesses) {
  47.     unordered_set<string> candidates; string guess;
  48.     for (auto& w:_dict) candidates.insert(w);
  49.     while (!makeAGuess(candidates, guess)) { guesses.push_back(guess); }
    . from: 1point3acres.com/bbs
  50.     guesses.push_back(guess);
  51.   }
  52.   
  53.   void resetGame() { _ansIdx = rand()%_dict.size(); }. more info on 1point3acres.com
  54. };
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 03:28:45 | 显示全部楼层
请问Round 3 "不能用特殊符號"是说连delimiter的符号和NULL的符号都不能用的意思吗?这个serialized result是个string还是允许别的形式?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 04:19:22 | 显示全部楼层
Round 5:我用了Trie:
  1. typedef pair<string,int> SI;
  2. class Dictionary {
  3. private:. From 1point 3acres bbs
  4.   Node* _r;
  5.   int _k; // number of top searched prefixes to track
  6.   unordered_map<string, int> _freq;
  7.   set<SI> _topk;. 鍥磋鎴戜滑@1point 3 acres
  8.   unordered_map<string,set<SI>::iterator> _pos;. 1point3acres.com/bbs
  9.   
  10.   void getWords(Node* r, vector<string>& ws) {
  11.     if (!r) return;
  12.     if (!r->word.empty()) ws.push_back(r->word);
  13.     getWords(r->left, ws); getWords(r->right, ws);
  14.   }
  15.   
  16.   Node* getPrefix(string& prefix) {
  17.     Node* res = _r;
  18.     for (char c:prefix) {-google 1point3acres
  19.       int idx = c-'a';
  20.       if (!res->next[idx]) return NULL;
  21.       res = res->next[idx];.1point3acres缃
  22.     }. From 1point 3acres bbs
  23.     return res;
  24.   }
  25.   
  26.   void updateFreq(string& prefix) {
  27.     _freq[prefix]++;
  28.     if (_pos.count(prefix)) {
  29.       _topk.erase(_pos[prefix]); _pos.erase(prefix);    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.     }
  31.     if (_topk.size() < k) {
  32.       _topk.emplace(prefix, _freq[prefix]);
  33.       _pos[prefix] = --_topk.end();
  34.     }
  35.     else if (_freq[prefix] > _top.rbegin()->second) {
  36.       _pos.erase(_topk.rbegin()->first);   
  37.       _topk.pop_back();
  38.       _topk.emplace(prefix, _freq[prefix]);
  39.       _pos[prefix] = --_topk.end();
  40.     }
  41.   }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  42.   . from: 1point3acres.com/bbs
  43. public:
  44.   Dictionary(int k):_r(new Node()),_k(k) {}
  45.   
  46.   void add(string& w, bool overwrite) {
  47.     auto cur = _r;
  48.     for (char c:w) {
  49.       int idx = c-'a';. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  50.       if (!cur->next[idx]) cur->next[idx] = new Node();
  51.       cur = cur->next[idx];
  52.     }
  53.     if (cur->word.empty() || overwrite) cur->word = w;. visit 1point3acres.com for more.
  54.   }
  55.   
  56.   vector<string> searchPrefix(string& prefix) {
  57.     updateFreq(prefix);
  58.     vector<string> ws;
  59.     getWords(getPrefix(prefix), ws);
  60.     return ws;. From 1point 3acres bbs
  61.   }
  62.   
  63.   vector<string> getTopSearched() {
  64.     vector<string> res;
  65.     for (auto& p:_topk) res.push_back(p.first);
  66.     return res;
  67.   }
  68. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 06:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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