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


一亩三分地论坛

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

[找工就业] Google intern 2018 summer 2轮面试

[复制链接] |试试Instant~ |关注本帖
战士 发表于 2017-11-12 06:15:40 | 显示全部楼层 |阅读模式

2018(10-12月)-[17]CS硕士+3个月-1年 - 内推| 码农类实习@Googlefresh grad应届毕业生

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

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

x
这周五两轮google intern的电话面试。
第一轮只有一道题:给定若干个区间以及一个数,返回这个数对应的区间序号。例如区间为[1,10],[11,20],[21,30],给了数字15,那么就应该返回1 (对应的是第二个区间[11,20])。思路是用binary search,但需要同时判别左右两个边界。这道题我比较快给了思路,然后写出了代码。考官之后让设计几个test case测一下,然后发现存在一些问题,后来纠正过来了。之后问如果要scale up的话可以怎么做,我就说可以用多线程,然后把代码改了一下。后面问了要怎么处理corner cases。最后问还可以如何改进我写的代码,我没太明白他说的改进是什么意思,就问他加注释、统一代码风格这些算不算,然后他说可以。。。总之这个面试的题目很简单,但是不知道follow up答得算不算ok。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

第二轮有两道题:第一题是给一个int,返回它的二进制的最高位1的Index。比如,对于int 4,二进制是100,最高位1的index就是2;对于int 1,二进制是1,最高位的index是0;对于0,返回-1;对于负数,因为最高位都是符号位,所以返回31。解法就是对于正数,不断的除2,然后计算除多少次能得到0,对于负数返回1,对于0返回-1。很简单的一道题。
第二题是leetcode 652 find duplicate subtrees。因为之前做过,所以比较快写出了答案。写完之后问了一下时间、空间复杂度,然后考官介绍了一下moutain view总部的情况,就结束了。

感觉这两轮面试都比较简单。。。但是不知道自己答的怎么样。希望能来offer。

评分

3

查看全部评分

 楼主| 战士 发表于 2017-11-13 05:31:59 | 显示全部楼层
gggpps 发表于 2017-11-13 01:08
请问一下,第一题scale up的话怎么用多线程?没有接触过multithread...
祝早日拿到offer~

我用java写的,只是单纯把那个函数写进了一个thread类里面,然后解释说可以用多线程处理并发

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| 战士 发表于 2017-11-12 06:18:32 | 显示全部楼层
第二轮第一题,对于复数应该返回31,写错了
回复 支持 反对

使用道具 举报

蜥蜴飞飞 发表于 2017-11-12 06:20:28 | 显示全部楼层
楼主一面二面做题前没有聊简历或者问问题吗?
回复 支持 反对

使用道具 举报

wangjingrzwd 发表于 2017-11-12 06:52:37 | 显示全部楼层
想问下第一题怎么写的。。
回复 支持 反对

使用道具 举报

wangjingrzwd 发表于 2017-11-12 06:53:20 | 显示全部楼层
是要按区间start排序吗
回复 支持 反对

使用道具 举报

lalasparrow 发表于 2017-11-12 07:04:42 | 显示全部楼层
请问一下楼主,第一轮的第一题有没有overlap,就是区间重叠的部分?如果有的话,是怎么处理的?
谢谢楼主!
回复 支持 反对

使用道具 举报

大灰灰 发表于 2017-11-12 07:26:22 | 显示全部楼层
求个time line...谢谢lz
回复 支持 反对

使用道具 举报

 楼主| 战士 发表于 2017-11-12 08:07:39 | 显示全部楼层
蜥蜴飞飞 发表于 2017-11-12 06:20
楼主一面二面做题前没有聊简历或者问问题吗?

一面有的,问了一下简历上的项目。二面直接上来就是做题
回复 支持 反对

使用道具 举报

 楼主| 战士 发表于 2017-11-12 08:12:05 | 显示全部楼层
第一轮第一题的range是不存在overlap的,也就是说给定的数只会match到0或1个range(会存在match不到任何range的情况)。解法是:将所有range按照left boundary排序,然后根据给定的数,对左边界进行binary search。在判断下一次是往左查找还是往右查找的时候还需要看当前range的右边界。我记得leetcode上有类似的题,但是不记得名字了。
回复 支持 反对

使用道具 举报

 楼主| 战士 发表于 2017-11-12 08:13:12 | 显示全部楼层
大灰灰 发表于 2017-11-12 07:26
求个time line...谢谢lz

9月末内推,10月的第一周拿到OA,第二三周安排面试,这周五两轮店面
回复 支持 反对

使用道具 举报

wangjingrzwd 发表于 2017-11-12 11:02:53 | 显示全部楼层
战士 发表于 2017-11-12 08:13
9月末内推,10月的第一周拿到OA,第二三周安排面试,这周五两轮店面
.1point3acres缃
想问下楼主 lc 652那道题 时间复杂度是多少呢? lc上没什么讨论关于这个 感觉是 o(n^3)如果用java 做的话
回复 支持 反对

使用道具 举报

 楼主| 战士 发表于 2017-11-12 12:24:45 | 显示全部楼层
wangjingrzwd 发表于 2017-11-12 11:02
想问下楼主 lc 652那道题 时间复杂度是多少呢? lc上没什么讨论关于这个 感觉是 o(n^3)如果用java 做的话
. From 1point 3acres bbs
是O(n)吧,只用遍历一遍tree就可以了
回复 支持 反对

使用道具 举报

wangjingrzwd 发表于 2017-11-12 15:35:56 | 显示全部楼层
战士 发表于 2017-11-12 12:24
是O(n)吧,只用遍历一遍tree就可以了

但是 catenate 字符串不也要花时间吗。。这个不计入吗。。
回复 支持 反对

使用道具 举报

 楼主| 战士 发表于 2017-11-13 00:12:24 | 显示全部楼层
wangjingrzwd 发表于 2017-11-12 15:35
但是 catenate 字符串不也要花时间吗。。这个不计入吗。。

你可以参考一下leetcode上的解法:
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {. 1point 3acres 璁哄潧
    List<TreeNode> res = new LinkedList<>();
    postorder(root, new HashMap<>(), res);. 1point 3acres 璁哄潧
    return res;
}

public String postorder(TreeNode cur, Map<String, Integer> map, List<TreeNode> res) {
    if (cur == null) return "#";  
    String serial = cur.val + "," + postorder(cur.left, map, res) + "," + postorder(cur.right, map, res); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    if (map.getOrDefault(serial, 0) == 1) res.add(cur);
    map.put(serial, map.getOrDefault(serial, 0) + 1);
    return serial;
}
回复 支持 反对

使用道具 举报

大灰灰 发表于 2017-11-13 00:42:14 | 显示全部楼层
战士 发表于 2017-11-12 08:13
9月末内推,10月的第一周拿到OA,第二三周安排面试,这周五两轮店面

谢谢lz哈,祝早日拿到offer~
回复 支持 反对

使用道具 举报

gggpps 发表于 2017-11-13 01:08:44 | 显示全部楼层
请问一下,第一题scale up的话怎么用多线程?没有接触过multithread...
祝早日拿到offer~
回复 支持 反对

使用道具 举报

570468837 发表于 2017-11-13 03:57:57 | 显示全部楼层
战士 发表于 2017-11-12 08:12
第一轮第一题的range是不存在overlap的,也就是说给定的数只会match到0或1个range(会存在match不到任何ran ...

谢谢LZ,已加米。
请问LZ,如果原来给的区间没排序,为什么不直接遍历一遍所有区间呢?这样只要O(n)了吧。
回复 支持 反对

使用道具 举报

smileyvenice 发表于 2017-11-13 04:01:07 | 显示全部楼层
请问scale up是什么意思呀?楼主是怎么处理的?
回复 支持 反对

使用道具 举报

 楼主| 战士 发表于 2017-11-13 05:32:44 | 显示全部楼层
570468837 发表于 2017-11-13 03:57
谢谢LZ,已加米。
请问LZ,如果原来给的区间没排序,为什么不直接遍历一遍所有区间呢?这样只要O(n)了吧 ...

是的。但是binary search只用log(n)啊,就比直接遍历的n要好
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 16:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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