聊聊在私立文理读cs的两年感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3215|回复: 21
收起左侧

Google Phone Interviews for Summer Internship

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

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

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

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

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: 用了最简单的生成所有排列,然后找出所有距离最小的。. visit 1point3acres for more.
(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就是交集了?
. 1point3acres
不知道对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):
还有加面的第二题有点不太懂题目的意思 points怎么形成loop??求解答~ 非常感谢!!
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-15 10:32:12 | 显示全部楼层
最后一题,可以这么做么。.1point3acres网
找到最少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了。我也比较困惑。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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]. more info on 1point3acres
这样就是一个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吧。
图,可以有几种方式表达。
[1,2] [2,3] 这种叫edge lists.. visit 1point3acres for more.

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

使用道具 举报

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

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

使用道具 举报

 楼主| jianglilong0225 发表于 2016-1-16 09:46:17 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-15 10:23
lz能具体讲一下,2 3题的解法么

-google 1point3acres1. 最短loop那道题我是生成了所有可能情况的排列,比如有三个点a1,a2,a3,就会有6种排列,对于其中一种排列a1,a2,a3,环是a1,a2,a3,a1,距离是dist(a1,a2) + dist(a2,a3) + dist(a3,a1). from: 1point3acres
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. 一亩-三分-地,独家发布
楼主能不能详细说下第一题的思路呀 包括老鼠这个类里面有哪些变量??谢谢了!!祝Offer!!

补充内容 (20 ...

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

使用道具 举报

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

1. 那找到头部的最大值之后,怎么更快地判断这个值是不是在所有数组里出现了呢?.1point3acres网
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当前头部的最大值?
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-21 05:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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