一亩三分地论坛

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

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

Google Onsite

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

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

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

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

x
今天面的,已经接了其他offer所以全程很放松。

1. 给定一个数组,从每个元素向后面查找,计算出后面比它大的元素的个数,返回最大个数的元素的index. from: 1point3acres.com/bbs
比如 .鐣欏璁哄潧-涓浜-涓夊垎鍦
[5, 2, 4, 1, 7, 6]

那么计数之后就是
[ 2, 3, 2, 2, 0, 0]

最大计数是3,返回index就是1
.鐣欏璁哄潧-涓浜-涓夊垎鍦
复杂度需要 O(nlogn) . 1point3acres.com/bbs

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. visit 1point3acres.com for more.

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.com/bbs

举例 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
. from: 1point3acres.com/bbs
5. solve maze, 自己想输入输出的数据结构



补充内容 (2016-11-20 13:03):
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 | 显示全部楼层
感谢楼主,请问楼主第一题用了什么数据结构,我以前是用BST解的,但是worst case是O(n ^ 2),是不是不行?   另外第四题RPN是什么? 谢谢!
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

j20120307 发表于 2016-11-18 10:07:06 | 显示全部楼层
  1. #include <iostream>
  2. #include <vector>
    -google 1point3acres
  3. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4. using namespace std;
    . from: 1point3acres.com/bbs

  5. class Solution {
  6. public:. 鍥磋鎴戜滑@1point 3 acres
  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;
  12.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  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);. From 1point 3acres bbs
  22.             path.pop_back();
  23.         }
  24.         return;. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.     }
  26. };

  27. int main() {
  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) {. from: 1point3acres.com/bbs
  32.             cout << i << " ";
  33.         });
  34.         cout << endl;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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 思路類似

看来真的要学到最优解,我把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
请问楼主是在哪里面的昂赛特呀?
. 1point3acres.com/bbs
NYC,字数字数字数
回复 支持 反对

使用道具 举报

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

不是,题目的输入只有一个参数,就是BST中的一个节点,不一定是root
. 1point3acres.com/bbs
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 | 显示全部楼层
. more info on 1point3acres.com
差不多这个意思,最后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
多谢!. Waral 鍗氬鏈夋洿澶氭枃绔,
也就是说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
如果没有root的话,有parent指针吗?
如果都没有的话,请问LZ 思路是啥啊

噢噢对,忘了说明了,每个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, 2016-12-10 02:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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