一亩三分地论坛

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

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

Google intern 1月6日 hangout视频面试(两轮)

[复制链接] |试试Instant~ |关注本帖
VeryEdward 发表于 2016-1-7 12:40:08 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
跪是肯定跪了,还是跟大家分享一下。个人认为两轮问的问题还都挺新鲜的,值得大家看一下。
从地里看Google一般是电话面试,由于本人没有手机耳麦所以选择了视频面试。Google的视频面试用的不是skype是hangout meeting。会在google calendar里给你链接,到点了直接点链接进入会议室就可以了。

第一轮:对面没有开视频,听口音是印度小哥。人很好,很有耐心。直接上题目:.1point3acres缃
给你一部分钱和一些不同价钱的商品,如何在最多买两件商品的情况下尽可能多的花掉手里的钱。
举例:口袋里的钱数: 10;        产品价格: [3, 6, 8, 7, 9]   输出 3, 7


这题我联想不到有什么做过的题,也并没有除了brute force之外的任何思路,就编了一个。过程中bug无数,在提醒下修改了。后面interviewer问如果price list是sorted有没有更好的办法。我提出用binary search,然后实现了一下。还是有bug,也在他提醒下改好了。

因为第一轮就只做了一个题,所以知道已经跪了,第二轮就比较放松。

第二轮:对面开了视频,是个白人小哥,有一点点口音,像是欧洲人。感觉这一轮路子比较野,大家可以参考一下。

首先小哥看到我简历上有操作系统TA的经历,就问了一系列memory allocator的问题,因为是课程project。不难,感觉答得还可以。

然后小哥出了一个程序题,并不是算法题,说要考察我对c++里面pointer的理解。题目是让我把source指针下的一部分内存内容移动到另一个destination地址,给了source地址下需要移动内容的大小length。其实就是两三行的代码,但是考量对pointer的熟悉程度,比如:函数参量的两个pointer都是void*,小哥提醒是不能进行加减操作的,只有在变成一个具体类型的pointer才可以。我一开始用的char*,小哥说如果一次想复制不只一个字节怎么办,我改成int*。接着还问了循环和地址运算的问题,具体记不清了。其中一点要说的是,以前不了解size_t的用法,所以在地址计算的时候还强行把length转换成int型(原本是size_t)计算iterator。实际上是画蛇添足了,size_t能够表示的数字比int大得多,我后来查了一下是一种至少16位的无符号整形数。这里就想来给大家讲一讲。

上面一个题目来回来去纠缠了很久,很多细节记不住了,大概就是综合性的考pointer的用法。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
接着上面一个题,小哥问了下面一个问题:如何用抛硬币产生1-8的随机数。这个简单,抛三次硬币组成的二进制数就可以。然后又问如何用抛硬币产生1-7的随机数。想了很久也没想出来。。。随口答了一个抛6次硬币产生0-6的数然后加一,但是产生的并不是均匀分布的随机数。。。. more info on 1point3acres.com

这个问题之后小哥又跳回到第一个问题。这次引入了cache,他用的特有名词我没有听懂,大致就是像这样的内存复制实际上是会牵扯到cache的,无论是按字节复制还是按每四个字节复制(int*)。如果用到了一个字节,和这个字节的相关的64个字节(举例子)都会被移动到cache的一个“cache line"里面(并不懂这是啥,我理解就是一个cache block里面不止一个字节吧),方便后面的存取。如果复制的内存较大(比如128字节),那么就会涉及到两个cache line。而如果跨cache line 存取的话会有比较高的latency,比我现在在第一个cache linede的第62个字节,而我一次读取4字节,那么我就要跨到下个cache line去读另外两个字节,这样子做的latency会比较大。然后小哥问了,基于以上背景,如何改进方法。我想了一会儿告诉他byte by byte存取就没有这个问题,实际上时间复杂度是一样的。小哥说还可以。

抱歉写了这么多字,主要是第二轮实在不好描述。我在面之前也没想到过会有这样的情况,没有一个算法题,感觉一直在说话。不管怎样我是已经跪了,希望大家能有好运气!. 1point3acres.com/bbs

谢谢!


补充内容 (2016-1-7 13:05):
和同学交流了一下,第一轮是我才疏学浅。array的题没怎么刷过,其实sort了以后可以用two pointer解决。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

wtcupup 发表于 2016-1-7 12:59:31 | 显示全部楼层
第二轮的面试题比较非主流
回复 支持 反对

使用道具 举报

Matcha 发表于 2016-1-7 13:00:22 | 显示全部楼层
第一个面试可以用greedy approach吗?瞎猜的
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-7 13:05:17 | 显示全部楼层
Matcha 发表于 2016-1-7 13:00
第一个面试可以用greedy approach吗?瞎猜的

第一题是dp吧。
暴力解也肯定可以啊,组成所有pair为2个数,然后看哪个pair的sum最接近结果。
回复 支持 反对

使用道具 举报

 楼主| VeryEdward 发表于 2016-1-7 13:09:30 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-7 13:05
第一题是dp吧。
暴力解也肯定可以啊,组成所有pair为2个数,然后看哪个pair的sum最接近结果。

我第一反应也是dp,但是看了一眼最多买两个,就不知道怎么分析了。
回复 支持 反对

使用道具 举报

 楼主| VeryEdward 发表于 2016-1-7 13:10:44 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-7 13:05
第一题是dp吧。
暴力解也肯定可以啊,组成所有pair为2个数,然后看哪个pair的sum最接近结果。

需要注意的是最好的办法不一定是pair,也可能是买一个就可以。我在编的时候也犯了这个错误。
回复 支持 反对

使用道具 举报

头像被屏蔽
q19890217 发表于 2016-1-7 21:32:57 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

kazi16 发表于 2016-1-8 04:11:44 | 显示全部楼层
1. When we copy a block of data from main memory to the cache, where exactly should we put it?
2. How can we tell if a word is already in the cache, or if it has to be fetched from main memory first?
3. Eventually, the small cache memory might fill up. To load a new block from main RAM, we’d have to replace one of the existing blocks in the cache... which one?. from: 1point3acres.com/bbs
4. How can write operations be handled by the memory system?
回复 支持 反对

使用道具 举报

Matcha 发表于 2016-1-9 04:19:05 | 显示全部楼层
第一题用DP bottom up的话 在哪里可以加限制条件(最多买2个商品)呢?比较困惑……
回复 支持 反对

使用道具 举报

dengke 发表于 2016-1-9 06:22:14 | 显示全部楼层
第一先sort以后,扫一遍找到小于钱数的最大数值,存起来。
然后放两个指针在开头和这个位置上,相互靠近移动,每次check sum,第一次小于等于钱数的时候跳出循环。比较一下这个sum和之前的单个数大小就行了。. 1point 3acres 璁哄潧
因为要sort,所以是Onlog(n)算法。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

请问binary search是怎么做啊?还能有O(logn)算法吗?
回复 支持 反对

使用道具 举报

 楼主| VeryEdward 发表于 2016-1-9 06:22:49 | 显示全部楼层
kazi16 发表于 2016-1-8 04:11
1. When we copy a block of data from main memory to the cache, where exactly should we put it?
2. H ...

恕我用中文了~
其实他没问这么细,就是给了这么一个setup看我怎么应变。我觉得并不是考对cache的理解。
回复 支持 反对

使用道具 举报

 楼主| VeryEdward 发表于 2016-1-9 06:31:46 | 显示全部楼层
dengke 发表于 2016-1-9 06:22
第一先sort以后,扫一遍找到小于钱数的最大数值,存起来。
然后放两个指针在开头和这个位置上,相互靠近移 ...
. 鍥磋鎴戜滑@1point 3 acres
嗯我觉得你给的做法应该是最好的。

我当时用binary search写的还是遍历整个数组所以还是O(nlogn)的算法。
回复 支持 反对

使用道具 举报

dengke 发表于 2016-1-9 06:42:29 | 显示全部楼层
那个随机数问题。。如果已经有生成1-8的方法了,那生成1-7是不是把输出8的情况discard掉就好了?。。这样剩下7个数也是等概率的
回复 支持 反对

使用道具 举报

 楼主| VeryEdward 发表于 2016-1-9 06:51:17 | 显示全部楼层
dengke 发表于 2016-1-9 06:42
那个随机数问题。。如果已经有生成1-8的方法了,那生成1-7是不是把输出8的情况discard掉就好了?。。这样剩 ...

是的。。。是我太笨了。。
回复 支持 反对

使用道具 举报

galaxy321 发表于 2016-1-10 05:03:08 | 显示全部楼层
To generate 1 ~ 7 with probability of each number being 1/7, we can apply the results of generating 1 ~ 8 except that we simply rethrow the coins when we get 8. With geometric series, it can be proved that the probability is exactly 1/7.
回复 支持 反对

使用道具 举报

JohnsonMS 发表于 2016-1-11 05:40:31 | 显示全部楼层
第一题 觉得是多重背包问题, 有人同意吗?
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2016-1-14 04:02:53 | 显示全部楼层
1- 7 应该就是用前面1-8 然后如果是8 就重新扔3次。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-25 10:58:49 | 显示全部楼层
第一题应该就是sort,然后两个指针一头一尾向中间靠就行了吧,时间复杂度是O(nlgn)
回复 支持 反对

使用道具 举报

aaa18918 发表于 2016-1-27 02:22:42 | 显示全部楼层
第一期quick sort+two points,再拿一个constant space记录距离目标最接近的值,如果扫的过程从大于目标扫到了小于目标且距离超过最接近的值,则直接return。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-22 16:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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