近期论坛无法登录的解决方案


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3587|回复: 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]

那么计数之后就是
[ 2, 3, 2, 2, 0, 0]
-google 1point3acres
最大计数是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]
[0, 1, 3]
[0, 2, 3]

举例 n = 4, 那么结果就是
[0, 1, 2, 3, 4]
[0, 1, 2, 4]
[0, 1, 3, 4]. from: 1point3acres.com/bbs
[0, 2, 3, 4]
[0, 2, 4]
[0, 4]

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

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

.鏈枃鍘熷垱鑷1point3acres璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-11-20 13:03):
RPN是逆波兰表达式,面试时具体的题目是这样的:
输入"(* 1 2 3)" => 输出 6
输入"(+ 1 2)" => 输出 3. 1point3acres.com/bbs
输入"(* 1)" => 1
输入"(+ 1)" => 1. Waral 鍗氬鏈夋洿澶氭枃绔,
输入"(+ 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;-google 1point3acres
  8.         vector<int> path = {0};. 1point3acres.com/bbs
  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) {. more info on 1point3acres.com
  15.             result.push_back(path);
  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();.1point3acres缃
  22.         }
  23.         return;
  24.     }-google 1point3acres
  25. };

  26. int main() {. Waral 鍗氬鏈夋洿澶氭枃绔,
  27.     Solution solution;
  28.     vector<vector<int>> result = solution.generate(4);
  29.     for_each(result.begin(), result.end(), [](vector<int>& v) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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. 1point 3acres 璁哄潧
第二题是inorder successor吗?
-google 1point3acres
可以先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
请问楼主是在哪里面的昂赛特呀?

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是什么?
. more info on 1point3acres.com
加到补充里面啦
回复 支持 反对

使用道具 举报

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

差不多这个意思,最后follow up是有什么可以优化的
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

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

如果没有root的话,有parent指针吗?. 1point3acres.com/bbs
如果都没有的话,请问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是有什么可以优化的

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-27 05:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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