一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1961|回复: 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里给你链接,到点了直接点链接进入会议室就可以了。

第一轮:对面没有开视频,听口音是印度小哥。人很好,很有耐心。直接上题目:
给你一部分钱和一些不同价钱的商品,如何在最多买两件商品的情况下尽可能多的花掉手里的钱。
举例:口袋里的钱数: 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位的无符号整形数。这里就想来给大家讲一讲。. Waral 鍗氬鏈夋洿澶氭枃绔,

上面一个题目来回来去纠缠了很久,很多细节记不住了,大概就是综合性的考pointer的用法。. 鍥磋鎴戜滑@1point 3 acres

接着上面一个题,小哥问了下面一个问题:如何用抛硬币产生1-8的随机数。这个简单,抛三次硬币组成的二进制数就可以。然后又问如何用抛硬币产生1-7的随机数。想了很久也没想出来。。。随口答了一个抛6次硬币产生0-6的数然后加一,但是产生的并不是均匀分布的随机数。。。

这个问题之后小哥又跳回到第一个问题。这次引入了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存取就没有这个问题,实际上时间复杂度是一样的。小哥说还可以。. 1point 3acres 璁哄潧

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

谢谢!. Waral 鍗氬鏈夋洿澶氭枃绔,


补充内容 (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?
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和之前的单个数大小就行了。
因为要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以后,扫一遍找到小于钱数的最大数值,存起来。
然后放两个指针在开头和这个位置上,相互靠近移 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
嗯我觉得你给的做法应该是最好的。

我当时用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, 2016-12-9 06:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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