一亩三分地论坛

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

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

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]。

Round 2 白人大叔:
設計一個兩人遊戲,給一個字典都是剛好 5 letters 的字,A 從字典裡挑一個字,B 從字典挑字去猜,A 會告訴 B 說你猜對幾個字,但是不會告訴你對的是哪幾個字母。寫兩個 function,一個判定 B 是否猜對,另一個給定上一輪猜的字和 A 的 feedback,從字典裡 narrow down search space。. visit 1point3acres.com for more.

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

Round 4 白人姊姊:
給一個 class 挑錯,一個一個挑出來改正,有些是 bug,有些是設計不好。第二題 read4K。.鐣欏璁哄潧-涓浜-涓夊垎鍦

Round 5 國人小哥:
寫一個 API,給定一個字典,輸入 prefix,返回所有包含這個 prefix 的字。follow up: 1. 假如空間不夠怎麼辦 2. 如何返回比較熱門的搜尋字 3. 如果輸入有 typo 怎麼辦

--

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

祝福各位面試順利!
. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 398, 订阅: 23
zzgzzm 发表于 2017-2-24 23:35:35 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
吃啥才算成熟 发表于 2017-2-22 05:18
我觉得你有可能理解错题意了. 想多了. 我在下面pseudo写一个,你看看make sense么.
. 鍥磋鎴戜滑@1point 3 acres
nums -->sums// {2 ...

关键是原题中并没有说sorted array nums[]一定都是非负元素,所以array sums[]有可能先递减再递增,在sums[]整体范围做binary search我觉得是不行的。

我觉得这个题就是将nums[]转化为sums[],然后找有多少对(i < j)使得sums[j] - sums[\i] 在[lo, up]区间中。至于怎么binary search sums[]得分单调区间(所以我觉得只要nums[]中正元素都在负之后就可以了,没有用到nums[]本身sorted的性质,因为关注的是sums[], 不是nums[])。

. Waral 鍗氬鏈夋洿澶氭枃绔,PS:刚刚发现LZ的例子中将single sum "7"没有算,若是这样的话,那么再要求i+1 < j.
回复 支持 2 反对 0

使用道具 举报

zzgzzm 发表于 2016-11-19 22:28:04 | 显示全部楼层
关注一亩三分地微博:
Warald
catinclay 发表于 2016-11-19 14:38. 鍥磋鎴戜滑@1point 3 acres
那你i&gt;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)); -google 1point3acres
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 ?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

sophie0815 发表于 2016-11-11 15:00:06 | 显示全部楼层
还有问下楼主最后一问follow up是怎么答得?
1. 空间不够解决方法是放在多个机器吗?   
2. 搜索热门的词语 建个数据库 给每个词count frequency 然后根据frequency 排序吗?. from: 1point3acres.com/bbs
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
能不能麻烦楼主详细讲下第二题? 我也在其他面经看到这题。 请问在不告诉你是哪个字母猜对的情况下,如何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
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. 1point3acres.com/bbs
B 每猜一次就可以得到 A 的 feedback,利用這個 feedback 就可以把字典裡不可能的字去掉,然後再隨便猜一 ...

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

使用道具 举报

 楼主| raychien 发表于 2016-11-13 12:31:40 | 显示全部楼层
xinyukkkk028 发表于 2016-11-12 13:09
请问楼主第二题是要求想function么?排除不可能的除了完全没有重复字母的和重复字母数大于猜对数字的以外, ...
. From 1point 3acres bbs
這道題基本就是考你如何設計遊戲 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;
  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) {. 1point 3acres 璁哄潧
  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));
  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是比较慢的,没有考虑单词彼此之间的联系。. from: 1point3acres.com/bbs
我就写了个简单版本:
  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) {
  16.     for (auto& w:candidates) {
  17.       if(feedback != numCommonChars(guess, w)) candidates.erase(w);
  18.     }
  19.   }
  20.   
  21.   bool correctGuess(string& guess) { return guess == _dict[_ansIdx]; }

  22. public:
  23.   WordGame(vector<string>& dict):_dict(dict) {. From 1point 3acres bbs
  24.     if (!_dict.size()) { cout << "empty dictionary!\n"; return; }
  25.     _ansIdx = rand()%_dict.size();
  26.   }
  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) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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.   }
  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
等了多久收到结果的?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-14 03:21:10 | 显示全部楼层
sophie0815 发表于 2016-11-13 11:20
这道题可以优化吗?  比如我给dictionary 建个trie 然后根据每次的feedback 去掉某些branch ?
. From 1point 3acres bbs
我也在想这个题要不要预处理字典。其实就是说这个游戏要不要玩很多次?若是的话预处理字典是肯定的了。但这个游戏只和letter count有关,所以不用Trie (trie和prefix or order有关)。
关键是每次(尤其是第一次)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 {
  2. private:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.   vector<string> _dict;
  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.   .1point3acres缃
  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;
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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]; }
  26.   // make a random guess within candiates and narrow down search candiates
  27.   
  28.   bool makeAGuess(unordered_set<string>& candidates, string& guess) {
  29.     guess = *candidates.begin(); candidates.erase(guess);
  30.     narrowDown(candidates, guess, numCommonChars(_dict[_ansIdx], guess));
  31.     return correctGuess(guess);
  32.   }. 1point3acres.com/bbs
  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. from: 1point3acres.com/bbs
  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.     }
  44.   }

  45.   // get all guesses sequence by B. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  46.   void allGuesses(vector<string>& guesses) {
  47.     unordered_set<string> candidates; string guess;
    . 1point 3acres 璁哄潧
  48.     for (auto& w:_dict) candidates.insert(w);
  49.     while (!makeAGuess(candidates, guess)) { guesses.push_back(guess); }
  50.     guesses.push_back(guess);
  51.   }
  52.   
  53.   void resetGame() { _ansIdx = rand()%_dict.size(); }
  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:. 鍥磋鎴戜滑@1point 3 acres
  1. typedef pair<string,int> SI;
  2. class Dictionary {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  3. private:
  4.   Node* _r;
  5.   int _k; // number of top searched prefixes to track. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  6.   unordered_map<string, int> _freq;
  7.   set<SI> _topk;
  8.   unordered_map<string,set<SI>::iterator> _pos;
  9.   . 1point 3acres 璁哄潧
  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);. From 1point 3acres bbs
  14.   }
  15.   
  16.   Node* getPrefix(string& prefix) {
  17.     Node* res = _r;
  18.     for (char c:prefix) {
  19.       int idx = c-'a';
  20.       if (!res->next[idx]) return NULL;
  21.       res = res->next[idx];
  22.     }
  23.     return res;
  24.   }. From 1point 3acres bbs
  25.   . Waral 鍗氬鏈夋洿澶氭枃绔,
  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) {
    . From 1point 3acres bbs
  32.       _topk.emplace(prefix, _freq[prefix]);
  33.       _pos[prefix] = --_topk.end();-google 1point3acres
  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]);.1point3acres缃
  39.       _pos[prefix] = --_topk.end();
  40.     }
  41.   }
  42.   
  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;
  54.   }
  55.   
  56.   vector<string> searchPrefix(string& prefix) {
  57.     updateFreq(prefix);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  58.     vector<string> ws;
  59.     getWords(getPrefix(prefix), ws);
  60.     return ws;
  61.   }
  62.   
  63.   vector<string> getTopSearched() {
  64.     vector<string> res;
  65.     for (auto& p:_topk) res.push_back(p.first);
  66.     return res;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  67.   }. from: 1point3acres.com/bbs
  68. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-27 08:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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