谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3868|回复: 18
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
VeryEdward 发表于 2016-1-7 12:40:08 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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

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

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

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

第二轮:对面开了视频,是个白人小哥,有一点点口音,像是欧洲人。感觉这一轮路子比较野,大家可以参考一下。
.1point3acres网
首先小哥看到我简历上有操作系统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位的无符号整形数。这里就想来给大家讲一讲。
. visit 1point3acres for more.
上面一个题目来回来去纠缠了很久,很多细节记不住了,大概就是综合性的考pointer的用法。. From 1point 3acres bbs

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

这个问题之后小哥又跳回到第一个问题。这次引入了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解决。

评分

参与人数 3大米 +41 收起 理由
aznfy + 30
Jeremian1990 + 10 感谢分享!
guixi107 + 1 感谢分享!

查看全部评分


上一篇:请问谷歌家的onsite之前的coaching hangout是个什么东西,有谁做过??
下一篇:Facebook Production Engender Intern

本帖被以下淘专辑推荐:

我的人缘0
wtcupup 发表于 2016-1-7 12:59:31 | 显示全部楼层
  此人我要顶:
 
18% (1) 【我投】
  此人我要踩:
 
82% (10) 【我投】
第二轮的面试题比较非主流
回复 支持 反对

使用道具 举报

我的人缘0
Matcha 发表于 2016-1-7 13:00:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一个面试可以用greedy approach吗?瞎猜的
回复 支持 反对

使用道具 举报

我的人缘0
xiaozhuxiaozhu 发表于 2016-1-7 13:05:17 | 显示全部楼层
  此人我要顶:
 
33% (5) 【我投】
  此人我要踩:
 
67% (13) 【我投】
Matcha 发表于 2016-1-7 13:00. from: 1point3acres
第一个面试可以用greedy approach吗?瞎猜的

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

使用道具 举报

我的人缘0
 楼主| VeryEdward 发表于 2016-1-7 13:09:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xiaozhuxiaozhu 发表于 2016-1-7 13:05
第一题是dp吧。
暴力解也肯定可以啊,组成所有pair为2个数,然后看哪个pair的sum最接近结果。

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

使用道具 举报

我的人缘0
 楼主| VeryEdward 发表于 2016-1-7 13:10:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xiaozhuxiaozhu 发表于 2016-1-7 13:05. from: 1point3acres
第一题是dp吧。
暴力解也肯定可以啊,组成所有pair为2个数,然后看哪个pair的sum最接近结果。

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

使用道具 举报

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

使用道具 举报

我的人缘0
kazi16 发表于 2016-1-8 04:11:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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?. 1point 3acres 论坛
4. How can write operations be handled by the memory system?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
Matcha 发表于 2016-1-9 04:19:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题用DP bottom up的话 在哪里可以加限制条件(最多买2个商品)呢?比较困惑……
回复 支持 反对

使用道具 举报

我的人缘0
dengke 发表于 2016-1-9 06:22:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一先sort以后,扫一遍找到小于钱数的最大数值,存起来。
然后放两个指针在开头和这个位置上,相互靠近移动,每次check sum,第一次小于等于钱数的时候跳出循环。比较一下这个sum和之前的单个数大小就行了。
因为要sort,所以是Onlog(n)算法。。

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

使用道具 举报

我的人缘0
 楼主| VeryEdward 发表于 2016-1-9 06:22:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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的理解。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| VeryEdward 发表于 2016-1-9 06:31:46 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
dengke 发表于 2016-1-9 06:22. from: 1point3acres
第一先sort以后,扫一遍找到小于钱数的最大数值,存起来。
然后放两个指针在开头和这个位置上,相互靠近移 ...

嗯我觉得你给的做法应该是最好的。

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

使用道具 举报

我的人缘0
dengke 发表于 2016-1-9 06:42:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
那个随机数问题。。如果已经有生成1-8的方法了,那生成1-7是不是把输出8的情况discard掉就好了?。。这样剩下7个数也是等概率的
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| VeryEdward 发表于 2016-1-9 06:51:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
dengke 发表于 2016-1-9 06:42
那个随机数问题。。如果已经有生成1-8的方法了,那生成1-7是不是把输出8的情况discard掉就好了?。。这样剩 ...
. 留学申请论坛-一亩三分地
是的。。。是我太笨了。。
回复 支持 反对

使用道具 举报

我的人缘0
galaxy321 发表于 2016-1-10 05:03:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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.
回复 支持 反对

使用道具 举报

我的人缘0
JohnsonMS 发表于 2016-1-11 05:40:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题 觉得是多重背包问题, 有人同意吗?
回复 支持 反对

使用道具 举报

我的人缘0
杰西Jesse 发表于 2016-1-14 04:02:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
1- 7 应该就是用前面1-8 然后如果是8 就重新扔3次。
回复 支持 反对

使用道具 举报

我的人缘0
bobzhang2004 发表于 2016-1-25 10:58:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题应该就是sort,然后两个指针一头一尾向中间靠就行了吧,时间复杂度是O(nlgn)
回复 支持 反对

使用道具 举报

我的人缘0
aaa18918 发表于 2016-1-27 02:22:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一期quick sort+two points,再拿一个constant space记录距离目标最接近的值,如果扫的过程从大于目标扫到了小于目标且距离超过最接近的值,则直接return。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-6-25 18:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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