谈谈使用过的几款咖啡机

一亩三分地论坛

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

google intern phone interview面经

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

() @ - -   | |

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

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

x
记得的有:
1.       两个sorted array找出整个的中位数
2.       括号匹配(()()[]) valid ([)] invalid
3.       一个文件里是一条条短信<time_stamp,senderID, receiverID>记录,按time_stamp排好序了。
a)        给一个senderID找出所有他发的短信
b)        如果A给B发了短信(A->B)那么B是A的1 degree friend,如果B->C,那么C是A的2 degree,给一个N返回所有小于等于degree的friend
c)        给上面那个写testcase
4.       有k个数,排好序的,这些数都是0到N间的,写一个randomnumber generate来generate一个0-N间的数且不能是k里面的。

评分

参与人数 2大米 +205 收起 理由
nunuh89 + 105
北美农民 + 100

查看全部评分


上一篇:悲剧的amazon面试,放点复习资料给大家用。。
下一篇:Yelp intern三轮phone/skype面经
我的人缘0
yxyxyx 发表于 2012-12-7 07:26:21 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
前两题都是leetcode上见过的
第三题,看起来是做广度优先图遍历?
第四题,除了用c++的rand别的我啥都不知道= =
回复 支持 反对

使用道具 举报

我的人缘0
msallk 发表于 2012-12-7 08:56:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我去,你怎么被问了这么多问题。。还是这些是你从别处看来的?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| secretgu 发表于 2012-12-7 09:01:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

leetcode没玩过= =
第四题我忘了我当初说的什么方法,刚临时想到一个方法是这样:
假设k=3, k_arr[] = {0,5,10}
你现在直接k+rand(N-k),假设出来的值,出来的值比如是5,那么在k_arr里binary search,如果找到就返回下标,5是1。如果rand出来是6,那么没找到,返回原数6。
大概意思就是说假象有个长为N的arr = {0,5,10,   3,4,1,6,7,8,9,2}。
这样时间复杂度是O(logk),空间不需要任何额外空间,上述数组只是假象的。
. from: 1point3acres
我忘了我当初说的什么解法了= =
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| secretgu 发表于 2012-12-7 09:04:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
msallk 发表于 2012-12-7 08:56
我去,你怎么被问了这么多问题。。还是这些是你从别处看来的?
. from: 1point3acres
2个45分钟啊,而且我码的挺快的,所以大概问的多?我被问的不止这几个= =还有几个记不住了
回复 支持 反对

使用道具 举报

我的人缘0
msallk 发表于 2012-12-7 09:45:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
secretgu 发表于 2012-12-7 09:04
2个45分钟啊,而且我码的挺快的,所以大概问的多?我被问的不止这几个= =还有几个记不住了

好吧。。我每轮只被问了一道programming的题,然后follow up一下,就没了。。之前10分钟问简历上的东西,还剩10多分钟的时候就让我问他问题了。。然后聊了很多他们team的事情。。看来不同interviewer风格差别很大啊。. 牛人云集,一亩三分地

评分

参与人数 1大米 +20 收起 理由
nunuh89 + 20

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
newlxnewlx 发表于 2012-12-7 13:16:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问这几道都需要programming吗?
还是部分题目只需说算法?. 1point3acres
一个45分钟的面试一般要programming几道呢?.本文原创自1point3acres论坛
Thanks
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| secretgu 发表于 2012-12-7 13:36:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
newlxnewlx 发表于 2012-12-7 13:16
请问这几道都需要programming吗? .留学论坛-一亩-三分地
还是部分题目只需说算法?
一个45分钟的面试一般要programming几道呢? ...
.留学论坛-一亩-三分地
这几个都coding了
做几道每个人code速度有快有慢,我也不太清楚
.留学论坛-一亩-三分地我google这个差不多2个人每个人2-3道题,一直做,他们完全没问我简历的事。

评分

参与人数 1大米 +10 收起 理由
nunuh89 + 10

查看全部评分

Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
dacongy 发表于 2012-12-8 00:39:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
弱问,第三题里面按time stamp排好序这个条件有啥用?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| secretgu 发表于 2012-12-8 01:30:32 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
dacongy 发表于 2012-12-8 00:39
弱问,第三题里面按time stamp排好序这个条件有啥用?

没啥用= =就是告诉你不是按send-id排序的大概
回复 支持 反对

使用道具 举报

我的人缘0
Ina217 发表于 2012-12-8 03:52:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
本帖最后由 Ina217 于 2012-12-8 12:39 编辑

. more info on 1point3acres
something like:
1. what's the signal that tail command send?
2. what's the information stored in inode?
3. what is running time?
4. what is the quick sort?

回复 支持 反对

使用道具 举报

我的人缘0
houqingniao 发表于 2013-1-20 05:18:52 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
短信这题 是不是就是dfs啊?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| secretgu 发表于 2013-1-28 07:28:32 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
houqingniao 发表于 2013-1-20 05:18
短信这题 是不是就是dfs啊?

我是bfs 字数字数。。。
回复 支持 反对

使用道具 举报

我的人缘0
jwzxgo 发表于 2013-2-3 06:28:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
尝试着回答了一下,回答得有错误求指正:

1.       两个sorted array找出整个的中位数
   merge sort until found.  o(n+m)
. From 1point 3acres bbs2.       括号匹配(()()[]) valid ([)] invalid
   linked queue o(n)
3.       一个文件里是一条条短信<time_stamp,senderID, receiverID>记录,按time_stamp排好序了。.1point3acres网
   n = len(input)
   m = len(members)

a)        给一个senderID找出所有他发的短信
   时间空间o(n) 跑一次,在内存里存储上短信在文件中的 offset
   如果内存中放不下这么大的数据,就存到文件里
   也可以应用 map reduce

b)        如果A给B发了短信(A->B)那么B是A的1 degree friend,如果B->C,那么C是A的2 degree,给一个N返回所有小于等于degree的friend. From 1point 3acres bbs
     adjacency matrix DFS 空间O(m^2) 时间O(2^degree)
c)        给上面那个写testcase
    no input (adgacency matrix is empty)
     unexpected degree value (<0). 围观我们@1point 3 acres
     degree value > max_degree_value (n)
     random input

4.       有k个数,排好序的,这些数都是0到N间的,写一个randomnumber generate来generate一个0-N间的数且不能是k里面的。
     同 LZ
     一开始我还想了一个方法: 产生 random(N) 如果这个值在 k 中存在则重新产生随机数,不过这个复杂度貌似比比较高. 围观我们@1point 3 acres

产生可用随机数的次数期望 = 1*(n-k)/n + 2*k/n*(n-k)/n + 3*(k/n)^2 * (n-k)/n + ...
> (n-k)/n + k/n*(n-k)/n + (k/n)^2 * (n-k)/n + ...
= (n-k)/n * (1 - (k/n)^(inf)) / (1 - k/n)
= 1
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| secretgu 发表于 2013-2-5 07:58:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
jwzxgo 发表于 2013-2-3 06:28
尝试着回答了一下,回答得有错误求指正:. 1point3acres

1.       两个sorted array找出整个的中位数

1. 可以O(log N) ,n和m一个量级,可以google到
2. 额外空间可以用O(1),不过有限制
3. 这题花头不大~
4. 我只能说论坛不太适合贴公式,哈哈
回复 支持 反对

使用道具 举报

我的人缘0
eallanwong 发表于 2013-3-3 09:24:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第二题括号匹配用一个栈就行了吧?
从左到右扫描每一个字符,遇到左括号把这个做括号压入栈,然后遇到右括号就检查左括号,看是否能匹配,不能匹配就是Invalid。扫描完之后如果栈不为空也是Invalid。
回复 支持 反对

使用道具 举报

我的人缘0
chensc 发表于 2013-3-15 08:54:00 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
secretgu 发表于 2012-12-7 09:01
leetcode没玩过= =
第四题我忘了我当初说的什么方法,刚临时想到一个方法是这样:
假设k=3, k_arr[] =  ...

这个方法好像不行吧?就以你的例子来说
k_arr如果是{1, 5, 10}怎么办?
随出来一个5,然后找到了,返回下标1.
不是还存在么?
回复 支持 反对

使用道具 举报

我的人缘0
sddi 发表于 2013-9-23 22:15:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
试一试,谢谢楼主分享,我也去leetcode上看看去~
回复 支持 反对

使用道具 举报

我的人缘0
denev2004 发表于 2013-9-26 06:58:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
问下 电面怎么做这种题?说出来代码么?
回复 支持 反对

使用道具 举报

我的人缘0
pottermarkken 发表于 2013-10-7 06:31:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Thanks a lot!
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-6-24 09:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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