一亩三分地论坛

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

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

Google Onsite (Search Infra) MTV

[复制链接] |试试Instant~ |关注本帖
samuel1989 发表于 2015-9-14 21:55:53 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
谷歌oniste面经
因为是一个原同事的内推外加几个别的公司onsite, 直接skip 电面。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

Mountain View, Building 42 and 43 onsite.

1. longest consective increasing sequence in binary tree.(start point happen anywhere in the node, not necessary start from root), 白人小哥
2. 中国北大姐,说是和我同一届本科毕业的,人家就是屌,国内直接来工作的。determine binary tree is complete tree. 感觉被low ball了, 也怪自己,对complete tree 不熟悉。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
3. 美国匹兹堡小哥(因为在匹兹堡读书,他顺带聊了下匹兹堡的事,他爸干啥干啥的) url list with relevance score sorted in descending order from two difference sources, how to organize and return unique url with descending order. (merge sort with de-duplicate) 简单题, 用merge sort的思想就完了。 代码里有个list.get(i), get element by index, pre-assume it would be arraylist. 结果在被问到what's assumption 时懵了。别的总体还好。
4.三哥,迟到15分钟, 急匆匆的进来了,给了个generate all possible complete tree with number of nodes is N. 然后中途还电话两次。 递归生成所有树,f(n) = { f(n-1) + attach two child nodes to any leaf of tree in f(n-1)}。在递归的时候要de-duplicate,用 serialize tree来保证树结构唯一性,(in-order + pre-order sequence).走了一遍serialization的例子。写的伪代码,因为没有时间写全所有的了,期间还有clone tree的操作。
5. 中国小哥,CMU毕业的。问了到 number的题。不知道怎么描述, given increase/decrease trend sequence, generate one possible sequence with minimal value. . 鍥磋鎴戜滑@1point 3 acres
for example, given sequence order "iddi" ->34215, "iii" -> 1234, "ddd"-> 4321. (solution有空在写, 直接慢慢琢磨出来的是O(n2)的solution, 小哥直接给hint说用链表结构能improve 到O(n) ).


面完,果断报告三哥迟到以及中途电话的事。

HR: feedback说buggy code, sigh....

如果有认识的匹兹堡Google的能麻烦推下吗?多谢了!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

agneshanlu 发表于 2015-9-17 04:03:42 | 显示全部楼层
hbsophia 发表于 2015-9-17 02:33.鏈枃鍘熷垱鑷1point3acres璁哄潧
大牛,能把第四题写下不,实在不会写啊,多谢多谢。

楼主在底下的补充里面已经写了具体的细节。关键点有几个:
1. 每个node要不没有child,要不有两个children。. from: 1point3acres.com/bbs
2. 定义的n是指leafnode的数量。
所以可以用递归来实现。
这道题特别特别像leetcode里面一道题
https://leetcode.com/problems/unique-binary-search-trees/
1. 一种就是选择我root节点的左子树中leafnode的数量,然后根据左子树中leafnode的数量得到右子树的leafnode数量,递归得到全部的树。
2. 另一种就是我们可以发现上一种方法中,有很多重复计算。比如我generate n = 4,则我们会重复计算很多次n = 2的树。可能在左子树中也可能在右子树中。所以我们用dynamic programming的思想,来存储中间所得到的子树。
我可能说的不明白,我把代码写出来了。给你粘在这里。
  1. class TreeNode. visit 1point3acres.com for more.
  2. {
  3. public:
  4.     TreeNode()
  5.     {
  6.         left = NULL;
  7.         right = NULL;
  8.     }
  9.     TreeNode* left;
  10.     TreeNode* right;
  11. };
  12. //normal recursion
  13. //n is the number of the leaf node
  14. vector<TreeNode*> generateTrees(int n). from: 1point3acres.com/bbs
  15. {
  16.     vector<TreeNode*> trees;
  17.     if(n == 0)
  18.     {
  19.         return trees;
  20.     }
  21.     if(n == 1)
  22.     {
  23.         TreeNode* root = new TreeNode();. 1point3acres.com/bbs
  24.         trees.push_back(root);
  25.         return trees;
  26.     }
  27.     vector<TreeNode*> leftSubTrees;. more info on 1point3acres.com
  28.     vector<TreeNode*> rightSubTrees;. 鍥磋鎴戜滑@1point 3 acres
  29.     for(int i = 1; i < n; i++)
  30.     {
  31.         // get the subtree of left child by recursion generation
  32.         leftSubTrees = generateTrees(i);
  33.         //get the subtree of right child by recursion generation
  34.         rightSubTrees = generateTrees(n - i);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  35.         for(int j = 0; j < leftSubTrees.size(); j++)
  36.         { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  37.             for(int k = 0; k < rightSubTrees.size(); k++)
  38.             {
  39.                 TreeNode* root = new TreeNode();
  40.                 root->left = leftSubTrees[j];
  41.                 root->right = rightSubTrees[k];
  42.                 trees.push_back(root);
  43.             }
  44.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  45.     }
  46.     return trees;
  47. }. Waral 鍗氬鏈夋洿澶氭枃绔,
  48. vector<TreeNode*> dsGenerateTrees(int n)
  49. {
  50.     vector<TreeNode*> trees;
  51.     if(n == 0)
  52.     {
  53.         return trees;
  54.     }
  55.     //store the generated trees of different n
  56.     vector<vector<TreeNode*>>  subtrees;
  57.     //generate current n's trees. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  58.     for(int i = 0; i < n; i++)
  59.     {
  60.         vector<TreeNode*> currTrees;
  61.         
  62.         if(i == 0)
  63.         {
  64.             TreeNode* root = new TreeNode();
  65.             currTrees.push_back(root);
  66.             subtrees.push_back(currTrees);
  67.             continue;
  68.         }
  69.         for(int j = 0; j < subtrees.size(); j++). Waral 鍗氬鏈夋洿澶氭枃绔,
  70.         {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  71.             vector<TreeNode*> leftSubTrees = subtrees[j];
  72.             vector<TreeNode*> rightSubTrees = subtrees[i - j - 1];
  73.             for(int k = 0; k < leftSubTrees.size(); k++). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  74.             {
  75.                 for (int l = 0; l < rightSubTrees.size() ; l++)
  76.                 {
  77.                     TreeNode* root = new TreeNode();
  78.                     root->left = leftSubTrees[k];
  79.                     root->right = rightSubTrees[l]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  80.                     currTrees.push_back(root);
  81.                 }
  82.             }
  83.         }
  84.         subtrees.push_back(currTrees);
  85.     }-google 1point3acres
  86.     return subtrees[n - 1];
  87. }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| samuel1989 发表于 2015-10-13 21:33:57 | 显示全部楼层
不好意思 大家!关于第五题没有描述清楚,digit should be unique. 所以Google Candy 解法不能用。e.g. 1213212 三个1, 三个2, not unique.
回复 支持 1 反对 0

使用道具 举报

licheng2002 发表于 2015-9-15 07:08:18 | 显示全部楼层
个人一些想法, 请指正:. From 1point 3acres bbs
3. merge sort的同时用hash set记录是否出现URL,如果有就skip,如果没有,加入hash set同时加入到最后的结果中。
4. 这个是number of full binary tree,总的tree的数应该是Catalan number,f(n)=sum_{i=1...n-1) (f(i)*f(n-i))-google 1point3acres
5. 不知道这样可不可以,从1234...n序列开始,扫描ii...dd, 对于连续的i,可以skip,对于连续的d,找到d的起始点和终点,然后reverse这一段
    比如iidd, 以12345 开始,前两个ii,skip,然后dd,起始和最后的位置分别在2,3,那么reverse序列12345中的2到3+1的位置,那么序列变成12543. 还有楼主在原帖里的例子:"iddi"结果应该是14325吧?
欢迎讨论!
回复 支持 1 反对 0

使用道具 举报

flexwang 发表于 2015-9-15 13:19:19 | 显示全部楼层
  1. list<int> get_trend_sequence(string s) {
  2.     list<int> l;
  3.     l.push_back(1);
  4.     auto it = l.begin();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.     for (int i=0; i<s.length(); i++)
  6.         if (s[i] == 'i') {
  7.             l.push_back(i+2);
  8.             it = l.end();
  9.             it --;
  10.         }
  11.         else {.1point3acres缃
  12.             l.insert(it, i+2);
  13.             print(l);
  14.             it--;. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.         }
  16.     return l;
  17. }
复制代码
最后一题的c++ solution,list几乎没用过啊,正好学学。
. From 1point 3acres bbs

补充内容 (2015-9-15 13:20):
print(l)那一行是我用来debug的,没用。
回复 支持 1 反对 0

使用道具 举报

TerrenceLi 发表于 2015-9-15 02:46:29 | 显示全部楼层
第五题的描述没有看懂额。。lz能再描述下么,given的string怎样描述出trend的。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-15 03:24:20 | 显示全部楼层
楼主, 工作几年了。。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-15 03:40:33 | 显示全部楼层
generate all possible complete tree with number of nodes==>是full tree吧? 如果是complete 的话, 就一种啊。。
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-15 03:48:49 | 显示全部楼层
第三题 不同source是什么意思 会不会出现两组排序中URL相同但是相对排名不一致的情况
第五题 看不懂
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-15 04:44:58 | 显示全部楼层
麻烦LZ, 第五题能再具体点吗?
回复 支持 反对

使用道具 举报

 楼主| samuel1989 发表于 2015-9-15 05:21:46 | 显示全部楼层
不好意思,写的太仓促了。当时边写边觉得自己逻辑没写好。
重新整理写从第3题到第5题。
3. You have two lists of URLs from source A and source B. each URL has score and each list of URL order by score in descending order.
For example:,
source A: (u1, 0.9), (u2, 0.8), (u3, 0.75)
source B: (u1, 0.8), (u3, 0.6), (u4, 0.5). visit 1point3acres.com for more.
return : (u1, 0.9), (u2, 0.8), (u3, 0.75), (u4, 0.5). PS: only return unique URL with highest score from two sources.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

4. 重新定义下题。 given number N which represents total number of leaves in tree.  you need to generate all possible tree, such that each node in tree has zero child or two children. The return type should be a list of such kind of trees. Only tree structure matters, tree node doesn't have any value initially.
My solution: N = 1 and N = 2 are base cases.
For example, N = 3. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

      1                1
   /    \            /   \
  1     1         1     1
/ \                    /  \
1  1                  1   1

For N = 4, all possible trees can be generated from f(3) by attaching each leaf node with two children, recursively follow this pattern to return target N. (Note: f(3) indicates a list of trees with 3 nodes in structure described above)

5. First, "i" represents increase, "d" represents decrease, so for number 123, the sequence would be "ii", for number 87123, sequence would "ddii". . 1point 3acres 璁哄潧
The question is to generate the minimum number follows given sequence "iidd".
解法: while loop,
step1, "" -> [1], next number for step2 is 2
step2 "i" -> [1, 2], next number for step3 is 3 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
step3 "i" -> [1, 2, 3], next number for step4 is 4
到第四步发现 [1, 2, 3, 4] 不符合 iid, 怎么办呢? 把4 与前面的3 交换 [1, 2, 4, 3] match "iid"
到第五步发现[1, 2, 4, 3, 5] 又不符合 iidd 怎么办呢? 把5与插到4前 [1, 2, 5, 4, 3].
这样12543 应该是最小的number了.  . 1point 3acres 璁哄潧
. 鍥磋鎴戜滑@1point 3 acres
核心就是每次记录last decreasing point. insert next number before last decreasing point. 本来用string 做的, 然后有个小while loop to find last decreasing point. 后来小哥说用一个新的data structure 会快些。链表结构,you just need to keep track of the node which is last decreasing point node.

这题我觉得很像排列组合在leetcode还是geeksforgeeks里的一道题。Anyway, 当场写这题的时候,直接当场找规律。. visit 1point3acres.com for more.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

呼唤匹兹堡兄弟,求内推。
. from: 1point3acres.com/bbs


补充内容 (2015-9-15 09:45):.1point3acres缃
第四题, 返回的不是the count of all possible trees, 而且返回  a list of all possible trees

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

edna 发表于 2015-9-15 06:41:54 | 显示全部楼层
  1. ListNode* getNumber(string s) {
  2.         ListNode dummy(-1);
  3.         ListNode *prev = &dummy;
  4.         ListNode *newNode = new ListNode(1);
  5.         ListNode *lastNode = prev;
  6.         prev->next = newNode;
    -google 1point3acres
  7.         prev = prev->next;


  8.         for (int i = 0; i < s.length(); i++) {
  9.                 ListNode *newNode = new ListNode(i+2);
  10.                 if (s[i] == 'i') {
  11.                         prev->next = newNode;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.                         lastNode = prev;
  13.                         prev = prev->next;
  14.                         continue;
  15.                 } else {. 鍥磋鎴戜滑@1point 3 acres
  16.                         ListNode *temp = lastNode->next;
  17.                         lastNode->next = newNode;
  18.                         newNode->next = temp;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.                 }
  20.         }
  21. . visit 1point3acres.com for more.
  22.         return dummy.next;. more info on 1point3acres.com
  23. }
复制代码
试着写了一下第五题,应该是这个意思。

补充内容 (2015-9-15 06:42):
16行的continue毫无意义,请忽略
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-15 06:45:24 | 显示全部楼层
第一题也写了下
  1. void getLongestArrayReal(TreeNode *root, int *smaller, int *larger, int *result) {
  2.         if (root == NULL) {
  3.                 return;
  4.         } else if (root->left == NULL && root->right == NULL) {
  5.                 *smaller = 1;. 1point 3acres 璁哄潧
  6.                 *larger = 1;. visit 1point3acres.com for more.
  7.                 *result = max(*result, 1);
  8.         }

  9.         int leftSmaller = 0, leftLarger = 0, rightSmaller = 0, rightLarger = 0;
  10.         getLongestArrayReal(root->left, &leftSmaller, &leftLarger, result);
  11.         getLongestArrayReal(root->right, &rightSmaller, &rightLarger, result);
  12.         if (root->left) {
  13.                 if (root->val > root->left->val) {
  14.                         *smaller = max(*smaller, 1);
  15.                         *larger = max(*larger, leftLarger+1);.1point3acres缃
  16.                 } else {
  17.                         *smaller = max(*smaller, leftSmaller+1);
    . From 1point 3acres bbs
  18.                         *larger = max(*larger, 1);
  19.                 }
  20.         }
  21.         if (root->right) {
  22.                 if (root->val > root->right->val) {
  23.                         *smaller = max(*smaller, 1);
  24.                         *larger = max(*larger, rightLarger+1);
  25.                 } else {-google 1point3acres
  26.                         *smaller = max(*smaller, rightSmaller+1);
  27.                         *larger = max(*larger, 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.                 }
  29.         }
  30.         *result = max(*result, *smaller+*larger-1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.         return;
  32. }

  33. int getLongestArray(TreeNode *root) {
  34.         int smaller = 0, larger = 0, result = 0;
  35.         getLongestArrayReal(root, &smaller, &larger, &result);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.         return result;
  37. }
复制代码
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-15 09:28:17 | 显示全部楼层
那个complete tree的
f(0) = 1, f(1) = 1, f(n) = f(0)*f(n-2) + f(1)*f(n-3) + ... + f(n-2)*f(0). from: 1point3acres.com/bbs
这样不可以吗 为什么要去重
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-15 13:24:02 | 显示全部楼层
licheng2002 发表于 2015-9-15 07:08
个人一些想法, 请指正:
3. merge sort的同时用hash set记录是否出现URL,如果有就skip,如果没有,加入h ...
. 鍥磋鎴戜滑@1point 3 acres
5. 我觉得是可以的 而且复杂度也是O(n)
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-15 14:07:13 | 显示全部楼层
flexwang 发表于 2015-9-15 13:19. 1point 3acres 璁哄潧
最后一题的c++ solution,list几乎没用过啊,正好学学。

insert的复杂度是n吧?这样整个过程就是n square了。

用linked list的好处是插入的复杂度是1,不是n。
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-15 14:42:05 | 显示全部楼层
flexwang 发表于 2015-9-15 09:28
那个complete tree的
f(0) = 1, f(1) = 1, f(n) = f(0)*f(n-2) + f(1)*f(n-3) + ... + f(n-2)*f(0). 鍥磋鎴戜滑@1point 3 acres
这样 ...

你这个不是complete tree把,complete tree是要尽可能所有节点向左边移动
回复 支持 反对

使用道具 举报

snail_914 发表于 2015-9-15 15:30:36 | 显示全部楼层
楼主 第五题个人觉得应该使用 Google Candy 解法 以ididdi 为例 左扫得倒1212112 再右边扫回来得倒1213212
回复 支持 反对

使用道具 举报

minglotus 发表于 2015-9-15 16:41:35 | 显示全部楼层
licheng2002 发表于 2015-9-15 07:08
个人一些想法, 请指正:
3. merge sort的同时用hash set记录是否出现URL,如果有就skip,如果没有,加入h ...

为什么iddi不是12101呢?每一位的数字不能重复吗?
回复 支持 反对

使用道具 举报

snail_914 发表于 2015-9-15 19:23:09 | 显示全部楼层
snail_914 发表于 2015-9-15 15:30
楼主 第五题个人觉得应该使用 Google Candy 解法 以ididdi 为例 左扫得倒1212112 再右边扫回来得倒1213212

如17楼所说 如果不能出现重复数字 那么candy解法就不行了。 不然的话, 之前忘了考虑0,同样以ididdi 为例 左扫得到: 1201001, 再从右往左遍历一遍, 两次o(n)遍历最终结果应该是: 1202101
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-16 01:29:01 | 显示全部楼层
edna 发表于 2015-9-15 06:45
第一题也写了下

待人家来验证验证!感觉上是对的。
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-16 01:38:08 | 显示全部楼层
edna 发表于 2015-9-15 06:45
第一题也写了下

请教一下大牛,臣妾不才,15,16行看不懂呢,leftSmaller 和  leftLarger 记录的是 左子树的这个节点 root->left 的左边的节点的个数和 右边的节点的个数? 请大牛指导下,多谢多谢,这个题目在地里见了好多次了,就是不知道该怎么做。好不容易看到大牛写的答案,得抓紧弄懂了呢,这周五我onsite呢,还是有多不会的题。。。
多谢多谢。

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 04:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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