May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

Google Onsite

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

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

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

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

x
今天面的,已经接了其他offer所以全程很放松。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

1. 给定一个数组,从每个元素向后面查找,计算出后面比它大的元素的个数,返回最大个数的元素的index
比如
[5, 2, 4, 1, 7, 6]

那么计数之后就是. 1point 3acres 璁哄潧
[ 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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

. 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]

举例 n = 4, 那么结果就是
[0, 1, 2, 3, 4]
[0, 1, 2, 4].鐣欏璁哄潧-涓浜-涓夊垎鍦
[0, 1, 3, 4]
[0, 2, 3, 4]
[0, 2, 4]
[0, 4]
.鏈枃鍘熷垱鑷1point3acres璁哄潧
4. RPN

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

.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-11-20 13:03):
RPN是逆波兰表达式,面试时具体的题目是这样的:
输入"(* 1 2 3)" => 输出 6. more info on 1point3acres.com
输入"(+ 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>
  2. #include <vector>

  3. using namespace std;

  4. class Solution {
  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);
  16.             return;
  17.         }
  18.         for (int delta = 1; delta + k <= n; delta *= 2) {
  19.             path.push_back(delta + k);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  20.             helper(delta + k, n, path, result);
  21.             path.pop_back();
  22.         }
  23.         return;
  24.     }
  25. };
    . 鍥磋鎴戜滑@1point 3 acres

  26. int main() {
  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) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.             cout << i << " "; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32.         });
  33.         cout << endl;
  34.     });
  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. 1point3acres.com/bbs
第二题是inorder successor吗?

可以先right child然后一直走left child吗?
回复 支持 反对

使用道具 举报

蜗牛君 发表于 2016-11-18 11:56:13 | 显示全部楼层
stevelee1012 发表于 2016-11-18 11:03.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一題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 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问楼主是在哪里面的昂赛特呀?

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是什么?
. 鍥磋鎴戜滑@1point 3 acres
加到补充里面啦
回复 支持 反对

使用道具 举报

 楼主| 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 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
多谢!
也就是说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. 1point3acres.com/bbs
如果没有root的话,有parent指针吗?
如果都没有的话,请问LZ 思路是啥啊
. visit 1point3acres.com for more.
噢噢对,忘了说明了,每个node都有left,right,还有parent指针
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-23 00:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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