《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3939|回复: 23
收起左侧

Google Onsite

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

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

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

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

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

1. 给定一个数组,从每个元素向后面查找,计算出后面比它大的元素的个数,返回最大个数的元素的index. from: 1point3acres.com/bbs
比如
[5, 2, 4, 1, 7, 6]
. more info on 1point3acres.com
那么计数之后就是
[ 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]
[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]. more info on 1point3acres.com
[0, 2, 4]
[0, 4]

4. RPN. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
5. solve maze, 自己想输入输出的数据结构

. 鍥磋鎴戜滑@1point 3 acres

补充内容 (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>

  3. using namespace std;.鏈枃鍘熷垱鑷1point3acres璁哄潧

  4. class Solution {
  5. public:
  6.     vector<vector<int>> generate(int n) {
  7.         vector<vector<int>> result;
  8.         vector<int> path = {0};. 1point 3acres 璁哄潧
  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) {
    . 1point 3acres 璁哄潧
  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);
  20.             helper(delta + k, n, path, result);
  21.             path.pop_back();
  22.         }
  23.         return;
  24.     } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25. };
  26. . visit 1point3acres.com for more.
  27. int main() {
  28.     Solution solution;. From 1point 3acres bbs
  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. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题是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 3 acres
请问楼主是在哪里面的昂赛特呀?

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

使用道具 举报

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

不是,题目的输入只有一个参数,就是BST中的一个节点,不一定是root
. 鍥磋鎴戜滑@1point 3 acres
TreeNode findNextLarger(TreeNode node) {}
回复 支持 反对

使用道具 举报

 楼主| izzy 发表于 2016-11-20 13:11:21 | 显示全部楼层
zhan1612 发表于 2016-11-19 12:59
麻烦问一下楼主第三题RPN是什么?
. 1point 3acres 璁哄潧
加到补充里面啦
回复 支持 反对

使用道具 举报

 楼主| 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
多谢!-google 1point3acres
也就是说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 思路是啥啊
. from: 1point3acres.com/bbs
噢噢对,忘了说明了,每个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-11-24 08:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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