一亩三分地论坛

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

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

Google Phone Interviews for Summer Internship

[复制链接] |试试Instant~ |关注本帖
jianglilong0225 发表于 2016-1-15 09:06:33 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 实习@Google - 内推 - 技术电面 |Pass其他

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

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

x
第一面: 给了一堆老鼠, 然后判断两只老鼠是不是有血缘的关系。类似Lowest Common Ancestor of a Binary Tree。但是有两个Parent。
第二面:Game of Life, 问了些如何并行加速运算
加面:
(1) Given two strings, check whether they are same ignoring the space
(2) Give N points (x, y), find the shortest loop: 用了最简单的生成所有排列,然后找出所有距离最小的。
(3) Give N sorted arrays, find the intersection of all arrays:每次取所有头部的最大值,然后检查是否在所有arrays中出现,如果是,就加到并集里。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

本帖被以下淘专辑推荐:

snooze 发表于 2016-1-22 05:50:15 | 显示全部楼层
加面第三题,用一个map把所有array中的数字的出现次数统计出来(同一个array的同一个数字只统计一次),然后取map中所有value==(array的个数)的key就是交集了?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

不知道对array交集的定义是否理解正确。
回复 支持 1 反对 0

使用道具 举报

iwofr 发表于 2016-1-15 09:57:06 | 显示全部楼层
麻烦问下lz面试完多久收到的feedback啊?
回复 支持 反对

使用道具 举报

 楼主| jianglilong0225 发表于 2016-1-15 09:59:55 | 显示全部楼层
The second day after my last round. Feel free to ask your recruiter.
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-15 10:23:19 | 显示全部楼层
lz能具体讲一下,2 3题的解法么
回复 支持 反对

使用道具 举报

atwoodwang0918 发表于 2016-1-15 10:24:17 | 显示全部楼层
楼主能不能详细说下第一题的思路呀 包括老鼠这个类里面有哪些变量??谢谢了!!祝Offer!!

补充内容 (2016-1-15 10:27):. visit 1point3acres.com for more.
还有加面的第二题有点不太懂题目的意思 points怎么形成loop??求解答~ 非常感谢!!
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-15 10:32:12 | 显示全部楼层
最后一题,可以这么做么。
找到最少length的arr,然后把左右elements 放进map.然后遍历其它的arr,看哪些是common elements.
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-15 10:34:46 | 显示全部楼层
atwoodwang0918 发表于 2016-1-15 10:24
楼主能不能详细说下第一题的思路呀 包括老鼠这个类里面有哪些变量??谢谢了!!祝Offer!!. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (20 ...

我感觉是,
[1,2] -》[2,3]-》[3,7]-》[7,1]
这样就是一个cycle了。我也比较困惑。
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-1-15 11:00:09 | 显示全部楼层
请问如何并行加速计算呀
回复 支持 反对

使用道具 举报

atwoodwang0918 发表于 2016-1-15 11:17:17 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-15 10:34
我感觉是,
[1,2] -》[2,3]-》[3,7]-》[7,1]. From 1point 3acres bbs
这样就是一个cycle了。我也比较困惑。

嗦嘎 谢啦~这题你有思路么??我完全不知道该怎么做。。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-15 11:21:39 | 显示全部楼层
atwoodwang0918 发表于 2016-1-15 11:17
嗦嘎 谢啦~这题你有思路么??我完全不知道该怎么做。。。

有向图查cycle,或者用dfs遍历任何点,然后看路径中,有没有点和起始点重合。
lz比较牛,能写3道题。不过第一题,应该2分钟解决。第2题,可能用些时间吧。我对graph那一块也不是掌握的特别好。
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-1-15 11:30:49 | 显示全部楼层
楼主能详细说下第三题的做法吗,用了什么数据结构呀,以及找到之后怎么继续往后查找呢
回复 支持 反对

使用道具 举报

atwoodwang0918 发表于 2016-1-15 11:32:28 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-15 11:21
有向图查cycle,或者用dfs遍历任何点,然后看路径中,有没有点和起始点重合。
lz比较牛,能写3道题。不过 ...

还是不太懂 input是数组的数组 怎么通过这个构建一个有向图呢?dfs遍历任何点的话感觉时间复杂度会是O(n^n)啊...
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-15 11:36:15 | 显示全部楼层
atwoodwang0918 发表于 2016-1-15 11:32
还是不太懂 input是数组的数组 怎么通过这个构建一个有向图呢?dfs遍历任何点的话感觉时间复杂度会是O(n^ ...

leetcode里面有一道题是course schedule吧。-google 1point3acres
图,可以有几种方式表达。
[1,2] [2,3] 这种叫edge lists.

https://leetcode.com/problems/course-schedule/
一道很好的练习。
回复 支持 反对

使用道具 举报

atwoodwang0918 发表于 2016-1-15 12:15:01 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-15 11:36
leetcode里面有一道题是course schedule吧。
图,可以有几种方式表达。
[1,2] [2,3] 这种叫edge lists. ...

太感谢了!!
回复 支持 反对

使用道具 举报

 楼主| jianglilong0225 发表于 2016-1-16 09:46:17 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-15 10:23
lz能具体讲一下,2 3题的解法么
. more info on 1point3acres.com
1. 最短loop那道题我是生成了所有可能情况的排列,比如有三个点a1,a2,a3,就会有6种排列,对于其中一种排列a1,a2,a3,环是a1,a2,a3,a1,距离是dist(a1,a2) + dist(a2,a3) + dist(a3,a1)
2. 求交集的是每次取所有array当前头部的最大值,判断是否这个最大的头部在所有array中出现,如果出现,就加到交集里。
回复 支持 反对

使用道具 举报

 楼主| jianglilong0225 发表于 2016-1-16 09:47:46 | 显示全部楼层
jianglilong0225 发表于 2016-1-16 09:46
1. 最短loop那道题我是生成了所有可能情况的排列,比如有三个点a1,a2,a3,就会有6种排列,对于其中一种排 ...

最短Loop那个估计是个NP问题,应该有更好的解法。但是当时没想到。
回复 支持 反对

使用道具 举报

 楼主| jianglilong0225 发表于 2016-1-16 09:51:22 | 显示全部楼层
atwoodwang0918 发表于 2016-1-15 10:24. visit 1point3acres.com for more.
楼主能不能详细说下第一题的思路呀 包括老鼠这个类里面有哪些变量??谢谢了!!祝Offer!!

补充内容 (20 ...

struct Node {
    Node* mom, *dad,
    vector<Node*> children;
    vecctor<Node*> siblings;
};. from: 1point3acres.com/bbs
然后BFS求出他的所有ancestors, 然后求另一个的ancestors的时候查询是否有相同的ancestors。这轮美国哥几乎不说话,所以也不知道这种解法到底好不好。。。
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-1-16 09:53:59 | 显示全部楼层
jianglilong0225 发表于 2016-1-16 09:46
1. 最短loop那道题我是生成了所有可能情况的排列,比如有三个点a1,a2,a3,就会有6种排列,对于其中一种排 ...

1. 那找到头部的最大值之后,怎么更快地判断这个值是不是在所有数组里出现了呢?
2. 如果这个值在所有数组里面出现了,加入到结果中,下一步是把所有数组的指针挪到这个值的位置么?
回复 支持 反对

使用道具 举报

neverlandly 发表于 2016-1-16 12:12:25 | 显示全部楼层
不太懂LZ加面第3题,什么叫“每次取所有array当前头部的最大值”?比如下面几组数
1,2,3,4,5
3,4,5,6,7. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
3,5,7,9,10
什么是所有array当前头部的最大值?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-5 09:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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