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

原帖地址:一亩三分地

跪是肯定跪了,还是跟大家分享一下。个人认为两轮问的问题还都挺新鲜的,值得大家看一下。
从地里看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位的无符号整形数。这里就想来给大家讲一讲。

上面一个题目来回来去纠缠了很久,很多细节记不住了,大概就是综合性的考pointer的用法。

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

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

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

谢谢!

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