一亩三分地论坛

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

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

Google Onsite

[复制链接] |试试Instant~ |关注本帖
izzy 发表于 2016-11-18 07:14:25 | 显示全部楼层 |阅读模式

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

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

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

x
今天面的,已经接了其他offer所以全程很放松。.鐣欏璁哄潧-涓浜-涓夊垎鍦

1. 给定一个数组,从每个元素向后面查找,计算出后面比它大的元素的个数,返回最大个数的元素的index
比如
[5, 2, 4, 1, 7, 6]
. visit 1point3acres.com for more.
那么计数之后就是
[ 2, 3, 2, 2, 0, 0]

最大计数是3,返回index就是1

复杂度需要 O(nlogn)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
2. given a valid no-duplicates binary search tree and a TreeNode, find the TreeNode that has the smallest larger value than given TreeNode in BST

3. given positive number n, find all of the sequences, so that the difference of neighbor elements are power of 2 and the greatest number is not greater than n.
举例 n = 3, 那么结果就是:
[0, 1, 2, 3]
[0, 1, 3]
[0, 2, 3]
.鏈枃鍘熷垱鑷1point3acres璁哄潧
举例 n = 4, 那么结果就是
[0, 1, 2, 3, 4]
[0, 1, 2, 4] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
[0, 1, 3, 4]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
[0, 2, 3, 4]
[0, 2, 4]
[0, 4]

4. RPN. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

5. solve maze, 自己想输入输出的数据结构
. 1point 3acres 璁哄潧
.1point3acres缃

补充内容 (2016-11-20 13:03):
RPN是逆波兰表达式,面试时具体的题目是这样的:
输入"(* 1 2 3)" => 输出 6
输入"(+ 1 2)" => 输出 3.1point3acres缃
输入"(* 1)" => 1
输入"(+ 1)" => 1
输入"(+ 1 (* 2 3) 4)" => 11
输入"(+ 1 (* 2 3))" => 7

评分

1

查看全部评分

本帖被以下淘专辑推荐:

蜗牛君 发表于 2016-11-18 08:12:54 | 显示全部楼层
感谢楼主,请问楼主第一题用了什么数据结构,我以前是用BST解的,但是worst case是O(n ^ 2),是不是不行?   另外第四题RPN是什么? 谢谢!
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-11-18 08:26:10 | 显示全部楼层
请问第三题和第四题什么意思呀
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

hellojay 发表于 2016-11-18 08:34:10 | 显示全部楼层
前排占个座
回复 支持 反对

使用道具 举报

j20120307 发表于 2016-11-18 10:07:06 | 显示全部楼层
  1. #include <iostream>
  2. #include <vector>

  3. using namespace std;

  4. class Solution {. Waral 鍗氬鏈夋洿澶氭枃绔,
  5. public:
  6.     vector<vector<int>> generate(int n) {
  7.         vector<vector<int>> result;
  8.         vector<int> path = {0};
  9.         helper(0, n, path, result);
  10.         return result;
  11.     }
  12. private:
  13.     void helper(int k, int n, vector<int>& path, vector<vector<int>>& result) {
  14.         if (k >= n) {
  15.             result.push_back(path);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.             return;
  17.         }
  18.         for (int delta = 1; delta + k <= n; delta *= 2) {
  19.             path.push_back(delta + k);
  20.             helper(delta + k, n, path, result);
  21.             path.pop_back();
  22.         }
  23.         return;
  24.     }
  25. };

  26. int main() {. more info on 1point3acres.com
  27.     Solution solution;
  28.     vector<vector<int>> result = solution.generate(4);
  29.     for_each(result.begin(), result.end(), [](vector<int>& v) {
  30.         for_each(v.begin(), v.end(), [](int& i) {. From 1point 3acres bbs
  31.             cout << i << " ";
  32.         });. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.         cout << endl;
  34.     });. more info on 1point3acres.com
  35.     return 0;
  36. }
复制代码
回复 支持 反对

使用道具 举报

stevelee1012 发表于 2016-11-18 11:03:11 | 显示全部楼层
第一題binary indexed tree 可以解 leetcode counting smaller 思路類似
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-11-18 11:10:54 | 显示全部楼层
第二题是inorder successor吗?
回复 支持 反对

使用道具 举报

hellojay 发表于 2016-11-18 11:14:56 | 显示全部楼层
houqingniao 发表于 2016-11-18 11:10
第二题是inorder successor吗?
. 1point3acres.com/bbs
可以先right child然后一直走left child吗?
回复 支持 反对

使用道具 举报

蜗牛君 发表于 2016-11-18 11:56:13 | 显示全部楼层
stevelee1012 发表于 2016-11-18 11:03
第一題binary indexed tree 可以解 leetcode counting smaller 思路類似

看来真的要学到最优解,我把BST的解看懂了就以为万事大吉- -
回复 支持 反对

使用道具 举报

ElenaCHAO 发表于 2016-11-19 00:27:52 | 显示全部楼层
请问楼主是在哪里面的昂赛特呀?
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-19 12:59:23 | 显示全部楼层
麻烦问一下楼主第三题RPN是什么?
回复 支持 反对

使用道具 举报

 楼主| izzy 发表于 2016-11-20 13:05:21 | 显示全部楼层
ElenaCHAO 发表于 2016-11-19 00:27. 1point 3acres 璁哄潧
请问楼主是在哪里面的昂赛特呀?

NYC,字数字数字数
回复 支持 反对

使用道具 举报

 楼主| izzy 发表于 2016-11-20 13:10:33 | 显示全部楼层
houqingniao 发表于 2016-11-18 11:10
第二题是inorder successor吗?

不是,题目的输入只有一个参数,就是BST中的一个节点,不一定是root

TreeNode findNextLarger(TreeNode node) {}
回复 支持 反对

使用道具 举报

 楼主| izzy 发表于 2016-11-20 13:11:21 | 显示全部楼层
zhan1612 发表于 2016-11-19 12:59
麻烦问一下楼主第三题RPN是什么?

加到补充里面啦
回复 支持 反对

使用道具 举报

 楼主| izzy 发表于 2016-11-20 13:12:09 | 显示全部楼层

差不多这个意思,最后follow up是有什么可以优化的
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-11-20 13:13:02 | 显示全部楼层
izzy 发表于 2016-11-20 13:10
不是,题目的输入只有一个参数,就是BST中的一个节点,不一定是root
. 1point 3acres 璁哄潧
TreeNode findNextLarger(TreeNod ...

多谢!
也就是说root是不知道的,只知道这个node是bst中node?. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

 楼主| izzy 发表于 2016-11-20 13:15:42 | 显示全部楼层
houqingniao 发表于 2016-11-20 13:13
多谢!
也就是说root是不知道的,只知道这个node是bst中node?

对的,输出是最小的比这个节点值更大的节点,如果没有则返回Null
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-11-21 00:32:47 | 显示全部楼层
izzy 发表于 2016-11-20 13:15. From 1point 3acres bbs
对的,输出是最小的比这个节点值更大的节点,如果没有则返回Null

. 1point 3acres 璁哄潧如果没有root的话,有parent指针吗?
如果都没有的话,请问LZ 思路是啥啊
回复 支持 反对

使用道具 举报

 楼主| izzy 发表于 2016-11-21 03:24:13 | 显示全部楼层
houqingniao 发表于 2016-11-21 00:32. 1point3acres.com/bbs
如果没有root的话,有parent指针吗?
如果都没有的话,请问LZ 思路是啥啊
. Waral 鍗氬鏈夋洿澶氭枃绔,
噢噢对,忘了说明了,每个node都有left,right,还有parent指针
回复 支持 反对

使用道具 举报

j20120307 发表于 2016-11-21 04:51:24 | 显示全部楼层
izzy 发表于 2016-11-20 13:12
差不多这个意思,最后follow up是有什么可以优化的

楼主怎么答的?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-24 02:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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