近期论坛无法登录的解决方案


一亩三分地论坛

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

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

GG onsite面经

[复制链接] |试试Instant~ |关注本帖
yinghuoaa 发表于 2015-10-8 07:27:34 | 显示全部楼层 |阅读模式

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

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

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

x
刚刚结束onsite。。。趁还记得
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一轮,国人大哥。
首先是安卓手机那种九个点的锁屏,找所有可能的序列。followup是限制长度怎么改。. more info on 1point3acres.com
然后给线段数组,求最多选多少个互相不overlap的线段,问怎么证明贪心是对的,然后code。
最后是给先增后减的数组,问怎么search一个target。讲完没时间code了。
. 1point3acres.com/bbs
第二轮,给一个pattern(可能会有最多一个*号)的字典,问怎么判断输入单词是不是在字典里。Trie从头写了一白板。。。followup怎么优化。。

第三轮,国人妹子带shadow。
leetcode那个找循环小数的题。
然后是merge interval,稍微更改是连续的也merge,比如[1, 2]和[3, 4]。
这一轮写得bug略多。。。两位面试官各种提示。。不知是好是坏。。。

最后,
先写了个array变BST,followup是改成iterate,然后又写了个模拟栈的版本。
第二题是怎么在二叉树里随机一个数(等概率),提示说可以增加node的data。。比如。。size。。

求RP,求offer啊。。
BTW,可以自己点名认识的人做lunch interviewer真是不错啊=,=. visit 1point3acres.com for more.

评分

3

查看全部评分

本帖被以下淘专辑推荐:

storm_hair 发表于 2015-10-8 10:25:28 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
此贴甚好 此题甚难
回复 支持 1 反对 0

使用道具 举报

nothingtrouble 发表于 2015-10-9 23:55:14 | 显示全部楼层
关注一亩三分地微博:
Warald
hulahu 发表于 2015-10-9 15:10. visit 1point3acres.com for more.
楼主, “然后给线段数组,求最多选多少个互相不overlap的线段,问怎么证明贪心是对的,然后code。”==》 ...

这个应该是Activity Selection Problem: http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

八月槎 发表于 2015-10-10 13:13:09 | 显示全部楼层
第二题需要这么复杂吗……   每个node的值除了26个字母之外再加一个‘*’不就可以了? 比如说把’*‘的值视作26

插入的时候‘*’就当作‘*‘处理, 查找的时候用递归做,遇到有child[26]=1的情况都添加一个条件分支就可以了
回复 支持 1 反对 0

使用道具 举报

Wizmann 发表于 2015-10-9 02:22:21 | 显示全部楼层
>> 第二轮,给一个pattern(可能会有最多一个*号)的字典,问怎么判断输入单词是不是在字典里。Trie从头写了一白板。。。followup怎么优化。。.1point3acres缃
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个怎么做?

我的想法是把pattern从*这里分开,建两棵Trie树。

正着查一次,反着查一次。然后merge下答案。

这样OK不?
回复 支持 反对

使用道具 举报

何打发123 发表于 2015-10-9 04:49:17 | 显示全部楼层
storm_hair 发表于 2015-10-8 10:25
此贴甚好 此题甚难
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
哈哈哈哈!!~~
回复 支持 反对

使用道具 举报

 楼主| yinghuoaa 发表于 2015-10-9 07:49:53 | 显示全部楼层
Wizmann 发表于 2015-10-9 02:22
>> 第二轮,给一个pattern(可能会有最多一个*号)的字典,问怎么判断输入单词是不是在字典里。Trie从头写 ...

恩,followup是这么答得,没code
只写了前缀树爆搜的。。
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-9 13:52:05 | 显示全部楼层
第一題不限長度  因該是DFS ? 最長的因該是9個  因為每個可以當作起點  所以time complexity o(n*m(n*m)) ? 如果有限長度  思路不依樣嗎? 能說說怎麼優化?
. Waral 鍗氬鏈夋洿澶氭枃绔,
最後一題的變BST 是 i ,2i 2i+1 這樣去access array嗎? LZ能說說iterative 跟隨機怎麼解的嗎? 有點不太懂

感謝LZ
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-9 15:07:19 | 显示全部楼层
Wizmann 发表于 2015-10-9 02:22. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
>> 第二轮,给一个pattern(可能会有最多一个*号)的字典,问怎么判断输入单词是不是在字典里。Trie从头写 ...

”正着查一次, 反着查一次 “ 啥意思啊?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-9 15:10:52 | 显示全部楼层
楼主, “然后给线段数组,求最多选多少个互相不overlap的线段,问怎么证明贪心是对的,然后code。”==》 您是怎么证明啊? 用dp解吗?
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-9 17:08:19 | 显示全部楼层
话说GG面试能自带键盘么。。。

MBP键盘简直难用到死。
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <iostream>.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5. #include <vector>
  6. #include <unordered_set>
  7. #include <cassert>. From 1point 3acres bbs

  8. using namespace std;. visit 1point3acres.com for more.

  9. #define print(x) cout << x << endl
  10. #define input(x) cin >> x
  11. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  12. template<typename value_t>
  13. class TrieDict {
  14.     static const int ALPHA = 26;
  15.     struct TrieNode {
  16.         TrieNode() {. visit 1point3acres.com for more.
  17.             next.resize(ALPHA, -1);
  18.         }. from: 1point3acres.com/bbs
  19.         vector<value_t> values;
  20.         vector<int> next;
  21.     };
  22. public:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.     TrieDict() {
  24.         _idx = 0;
  25.         _nodes.push_back(TrieNode());
  26.     }. more info on 1point3acres.com
  27. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.     void add(const string& key, const value_t& value) {
  29.         int ptr = 0;
  30.         for (size_t i = 0; i < key.size(); i++) {
  31.             int c = key[i] - 'a';
  32.             int next = _nodes[ptr].next[c];
  33.             if (next == -1) {. more info on 1point3acres.com
  34.                 _nodes[ptr].next[c] = ++_idx;
  35.                 _nodes.push_back(TrieNode());
  36.                 next = _idx;
  37.             } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  38.             ptr = next;
  39.         }. visit 1point3acres.com for more.
  40.         _nodes[ptr].values.push_back(value);
  41.     }
  42.     vector<value_t> search(const string& needle) {
  43.         vector<value_t> values;. Waral 鍗氬鏈夋洿澶氭枃绔,
  44.         int ptr = 0;
  45.         for (size_t i = 0; i < needle.size() && ptr != -1; i++) {.1point3acres缃
  46.             int c = needle[i] - 'a';
  47.             int next = _nodes[ptr].next[c];
  48.             copy(_nodes[ptr].values.begin(),
  49.                  _nodes[ptr].values.end(),
  50.                  back_inserter(values));
  51.             ptr = next;
  52.         }
  53.         if (ptr != -1) {
  54.             copy(_nodes[ptr].values.begin(),
  55.                 _nodes[ptr].values.end(),
  56.                 back_inserter(values));
  57.         }
  58.         return values;
  59.     }
  60. private:
  61.     int _idx;
  62.     vector<TrieNode> _nodes;
  63. };. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  64. class TrieWithStar {.1point3acres缃
  65.     struct Node {
  66.         int strid;.1point3acres缃
  67.         int status;
  68.     };
  69. public:. 鍥磋鎴戜滑@1point 3 acres
  70.     TrieWithStar(): idx(0) {}

  71.     void add(const string& key) {
  72.         auto star_idx = key.find("*");
  73.         if (star_idx == string::npos) {
  74.             _trie.add(key, {idx, FULL});.鏈枃鍘熷垱鑷1point3acres璁哄潧
  75.             return;
  76.         }
  77.         
  78.         auto left  = key.substr(0, star_idx);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  79.         
  80.         auto right = key.substr(star_idx + 1);
  81.         reverse(right.begin(), right.end());
  82.          鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  83.         _trie.add(left,  {idx, STAR});
  84.         _trie_r.add(right, {idx, STAR});
  85.         ++idx;
  86.     }

  87.     bool search(string needle) {. more info on 1point3acres.com
  88.         auto vec_a = _trie.search(needle);
  89.         reverse(needle.begin(), needle.end());
  90.         auto vec_b = _trie_r.search(needle);
  91.         return do_check(vec_a, vec_b);
  92.     }
  93. private:
  94.     bool do_check(const vector<Node>& vec_a, const vector<Node>& vec_b) {
  95.         unordered_set<int> st;
  96.         for (auto node: vec_a) {
  97.             if (node.status == FULL) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  98.                 return true;
  99.             }
  100.             st.insert(node.strid);
  101.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  102. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  103.         for (auto node: vec_b) {
  104.             int strid = node.strid;
  105.             if (st.find(strid) != st.end()) {-google 1point3acres
  106.                 return true;
    . 1point 3acres 璁哄潧
  107.             }
  108.         }
  109.         return false;
  110.     }
  111. private:
  112.     static const int FULL = 1;
  113.     static const int STAR = 0;
  114. private:. 1point3acres.com/bbs
  115.     TrieDict<Node> _trie;. From 1point 3acres bbs
  116.     TrieDict<Node> _trie_r;
  117.     int idx;
  118. };

  119. int main() {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  120.     TrieWithStar tws;

  121.     tws.add("fnck*me");
  122.     tws.add("bullshit");
  123.     tws.add("sob");
  124.     tws.add("microsoft*windows");
  125.     tws.add("foo*");. from: 1point3acres.com/bbs

  126.     assert(tws.search("fnckxxxxxxxxxxxme") == true);
  127.     assert(tws.search("fnckme") == true);
  128.     assert(tws.search("f*ckme") == false);
  129.     assert(tws.search("bullshit") == true);
  130.     assert(tws.search("s*b") == false);
  131.     assert(tws.search("microsoftwindows10") == false); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  132.     assert(tws.search("foobar") == true);

  133.     return 0;.1point3acres缃
  134. }
复制代码

评分

3

查看全部评分

回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-9 17:10:23 | 显示全部楼层
hulahu 发表于 2015-10-9 15:07
”正着查一次, 反着查一次 “ 啥意思啊?

下面有full code
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-9 17:45:21 | 显示全部楼层
第一题的偷懒写法:

1! + 2! + 3! + ... 9!

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴虽然比合理的数多一些,但是可以用来估算。
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-9 19:33:41 | 显示全部楼层

能具体说说思路吗 只看得懂java。。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-10-10 05:27:18 | 显示全部楼层
安卓手机那种九个点的锁屏,找所有可能的序列.
若没有长度限制,答案不是无限嘛?比如:1-2-1-2-1-2-1-2-1-2-1-2....
回复 支持 反对

使用道具 举报

 楼主| yinghuoaa 发表于 2015-10-10 06:01:10 | 显示全部楼层
jiebour 发表于 2015-10-10 05:27
安卓手机那种九个点的锁屏,找所有可能的序列..1point3acres缃
若没有长度限制,答案不是无限嘛?比如:1-2-1-2-1-2-1-2-1 ...

忘了说。。一个密码里一个点只能用一次。。
回复 支持 反对

使用道具 举报

 楼主| yinghuoaa 发表于 2015-10-10 06:01:54 | 显示全部楼层
Wizmann 发表于 2015-10-9 17:08
话说GG面试能自带键盘么。。。

MBP键盘简直难用到死。

onsite都是白板写吧=,=
自带笔可以?
回复 支持 反对

使用道具 举报

 楼主| yinghuoaa 发表于 2015-10-10 06:05:28 | 显示全部楼层
say543 发表于 2015-10-9 13:52 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一題不限長度  因該是DFS ? 最長的因該是9個  因為每個可以當作起點  所以time complexity o(n*m(n*m)) ? ...

忘说了。。一个密码里一个点只能用一次. from: 1point3acres.com/bbs
iterate就是自己建一个state结构函数调用的所有argument,就是模拟c++的函数栈
随即那个他说可以给node加data,然后我就加了“以当前节点为根的子树的节点个数”,然后随机一个数k,再在树里找第k大
回复 支持 反对

使用道具 举报

 楼主| yinghuoaa 发表于 2015-10-10 06:12:07 | 显示全部楼层
hulahu 发表于 2015-10-9 15:10. From 1point 3acres bbs
楼主, “然后给线段数组,求最多选多少个互相不overlap的线段,问怎么证明贪心是对的,然后code。”==》 ...
.1point3acres缃
数学归纳法证的,假设一个最优解,证明贪心的每一步都不会比这个最优解差
回复 支持 反对

使用道具 举报

 楼主| yinghuoaa 发表于 2015-10-10 06:20:25 | 显示全部楼层
Wizmann 发表于 2015-10-9 17:08
话说GG面试能自带键盘么。。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴MBP键盘简直难用到死。

这代码大赞啊!. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-22 22:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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