一亩三分地论坛

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

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

Google Onsite

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

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

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

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

x
今天面的,已经接了其他offer所以全程很放松。. Waral 鍗氬鏈夋洿澶氭枃绔,
. 鍥磋鎴戜滑@1point 3 acres
1. 给定一个数组,从每个元素向后面查找,计算出后面比它大的元素的个数,返回最大个数的元素的index
比如
[5, 2, 4, 1, 7, 6]

那么计数之后就是. 鍥磋鎴戜滑@1point 3 acres
[ 2, 3, 2, 2, 0, 0]

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

复杂度需要 O(nlogn)

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]. From 1point 3acres bbs
[0, 1, 3].鏈枃鍘熷垱鑷1point3acres璁哄潧
[0, 2, 3]

举例 n = 4, 那么结果就是
[0, 1, 2, 3, 4]
[0, 1, 2, 4].鏈枃鍘熷垱鑷1point3acres璁哄潧
[0, 1, 3, 4]
[0, 2, 3, 4]
[0, 2, 4]
[0, 4]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
4. RPN

5. solve maze, 自己想输入输出的数据结构

.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-11-20 13:03):. 鍥磋鎴戜滑@1point 3 acres
RPN是逆波兰表达式,面试时具体的题目是这样的:
输入"(* 1 2 3)" => 输出 6. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
输入"(+ 1 2)" => 输出 3
输入"(* 1)" => 1
输入"(+ 1)" => 1
输入"(+ 1 (* 2 3) 4)" => 11
输入"(+ 1 (* 2 3))" => 7. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

神罗天征 发表于 2016-11-18 08:26:10 | 显示全部楼层
关注一亩三分地微博:
Warald
请问第三题和第四题什么意思呀
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

  3. using namespace std;

  4. . from: 1point3acres.com/bbs
  5. class Solution {
  6. public:
  7.     vector<vector<int>> generate(int n) {
  8.         vector<vector<int>> result;
  9.         vector<int> path = {0};
  10.         helper(0, n, path, result);
  11.         return result;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  13. private:
  14.     void helper(int k, int n, vector<int>& path, vector<vector<int>>& result) {
  15.         if (k >= n) {
  16.             result.push_back(path);
  17.             return;
  18.         }
  19.         for (int delta = 1; delta + k <= n; delta *= 2) {
  20.             path.push_back(delta + k);
  21.             helper(delta + k, n, path, result);
  22.             path.pop_back();
  23.         }
  24.         return;
  25.     }
  26. };

  27. int main() {. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.     Solution solution;
  29.     vector<vector<int>> result = solution.generate(4);
  30.     for_each(result.begin(), result.end(), [](vector<int>& v) {
  31.         for_each(v.begin(), v.end(), [](int& i) {
  32.             cout << i << " ";
  33.         });
  34.         cout << endl;
  35.     });
  36.     return 0;
  37. }
复制代码
回复 支持 反对

使用道具 举报

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吗?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
可以先right child然后一直走left child吗?
回复 支持 反对

使用道具 举报

蜗牛君 发表于 2016-11-18 11:56:13 | 显示全部楼层
stevelee1012 发表于 2016-11-18 11:03
第一題binary indexed tree 可以解 leetcode counting smaller 思路類似
-google 1point3acres
看来真的要学到最优解,我把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
请问楼主是在哪里面的昂赛特呀?
-google 1point3acres
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是有什么可以优化的
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-11-20 13:13:02 | 显示全部楼层
izzy 发表于 2016-11-20 13:10
不是,题目的输入只有一个参数,就是BST中的一个节点,不一定是root

TreeNode findNextLarger(TreeNod ...

多谢!
也就是说root是不知道的,只知道这个node是bst中node?
回复 支持 反对

使用道具 举报

 楼主| 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
对的,输出是最小的比这个节点值更大的节点,如果没有则返回Null

如果没有root的话,有parent指针吗?
如果都没有的话,请问LZ 思路是啥啊
回复 支持 反对

使用道具 举报

 楼主| izzy 发表于 2016-11-21 03:24:13 | 显示全部楼层
houqingniao 发表于 2016-11-21 00:32. From 1point 3acres bbs
如果没有root的话,有parent指针吗?
如果都没有的话,请问LZ 思路是啥啊

噢噢对,忘了说明了,每个node都有left,right,还有parent指针
回复 支持 反对

使用道具 举报

j20120307 发表于 2016-11-21 04:51:24 | 显示全部楼层
izzy 发表于 2016-11-20 13:12
差不多这个意思,最后follow up是有什么可以优化的
.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主怎么答的?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-30 04:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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