一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 2994|回复: 19
收起左侧

google intern phone interview面经

[复制链接] |试试Instant~ |关注本帖
secretgu 发表于 2012-12-7 06:07:02 | 显示全部楼层 |阅读模式

() @ - -  |

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

您需要 登录 才可以下载或查看,没有帐号?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

查看全部评分

yxyxyx 发表于 2012-12-7 07:26:21 | 显示全部楼层
前两题都是leetcode上见过的
第三题,看起来是做广度优先图遍历?
第四题,除了用c++的rand别的我啥都不知道= =
msallk 发表于 2012-12-7 08:56:24 | 显示全部楼层
我去,你怎么被问了这么多问题。。还是这些是你从别处看来的?
 楼主| secretgu 发表于 2012-12-7 09:01:33 | 显示全部楼层

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),空间不需要任何额外空间,上述数组只是假象的。

我忘了我当初说的什么解法了= =
 楼主| secretgu 发表于 2012-12-7 09:04:09 | 显示全部楼层
msallk 发表于 2012-12-7 08:56
我去,你怎么被问了这么多问题。。还是这些是你从别处看来的?

2个45分钟啊,而且我码的挺快的,所以大概问的多?我被问的不止这几个= =还有几个记不住了
msallk 发表于 2012-12-7 09:45:49 | 显示全部楼层
secretgu 发表于 2012-12-7 09:04
2个45分钟啊,而且我码的挺快的,所以大概问的多?我被问的不止这几个= =还有几个记不住了

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

评分

1

查看全部评分

newlxnewlx 发表于 2012-12-7 13:16:20 | 显示全部楼层
请问这几道都需要programming吗? . 1point3acres.com/bbs
还是部分题目只需说算法?
一个45分钟的面试一般要programming几道呢?. 1point 3acres 璁哄潧
Thanks
 楼主| secretgu 发表于 2012-12-7 13:36:12 | 显示全部楼层
newlxnewlx 发表于 2012-12-7 13:16
请问这几道都需要programming吗?
还是部分题目只需说算法?
一个45分钟的面试一般要programming几道呢? ...
. visit 1point3acres.com for more.
这几个都coding了
做几道每个人code速度有快有慢,我也不太清楚.1point3acres缃
我google这个差不多2个人每个人2-3道题,一直做,他们完全没问我简历的事。

评分

1

查看全部评分

dacongy 发表于 2012-12-8 00:39:11 | 显示全部楼层
弱问,第三题里面按time stamp排好序这个条件有啥用?
 楼主| secretgu 发表于 2012-12-8 01:30:32 | 显示全部楼层
dacongy 发表于 2012-12-8 00:39
弱问,第三题里面按time stamp排好序这个条件有啥用?

没啥用= =就是告诉你不是按send-id排序的大概
Ina217 发表于 2012-12-8 03:52:17 | 显示全部楼层
本帖最后由 Ina217 于 2012-12-8 12:39 编辑


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? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

houqingniao 发表于 2013-1-20 05:18:52 | 显示全部楼层
短信这题 是不是就是dfs啊?
 楼主| secretgu 发表于 2013-1-28 07:28:32 | 显示全部楼层
houqingniao 发表于 2013-1-20 05:18
短信这题 是不是就是dfs啊?

我是bfs 字数字数。。。
jwzxgo 发表于 2013-2-3 06:28:40 | 显示全部楼层
尝试着回答了一下,回答得有错误求指正:

1.       两个sorted array找出整个的中位数
   merge sort until found.  o(n+m)
2.       括号匹配(()()[]) valid ([)] invalid
   linked queue o(n)
3.       一个文件里是一条条短信<time_stamp,senderID, receiverID>记录,按time_stamp排好序了。
   n = len(input)-google 1point3acres
   m = len(members)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
a)        给一个senderID找出所有他发的短信
   时间空间o(n) 跑一次,在内存里存储上短信在文件中的 offset
   如果内存中放不下这么大的数据,就存到文件里
   也可以应用 map reduce
-google 1point3acres
b)        如果A给B发了短信(A->B)那么B是A的1 degree friend,如果B->C,那么C是A的2 degree,给一个N返回所有小于等于degree的friend
     adjacency matrix DFS 空间O(m^2) 时间O(2^degree)
c)        给上面那个写testcase
    no input (adgacency matrix is empty). 1point 3acres 璁哄潧
     unexpected degree value (<0)
     degree value > max_degree_value (n)
     random input

4.       有k个数,排好序的,这些数都是0到N间的,写一个randomnumber generate来generate一个0-N间的数且不能是k里面的。
     同 LZ
     一开始我还想了一个方法: 产生 random(N) 如果这个值在 k 中存在则重新产生随机数,不过这个复杂度貌似比比较高.鐣欏璁哄潧-涓浜-涓夊垎鍦
. From 1point 3acres bbs
产生可用随机数的次数期望 = 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
 楼主| secretgu 发表于 2013-2-5 07:58:27 | 显示全部楼层
jwzxgo 发表于 2013-2-3 06:28
尝试着回答了一下,回答得有错误求指正:-google 1point3acres

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

1. 可以O(log N) ,n和m一个量级,可以google到. 1point3acres.com/bbs
2. 额外空间可以用O(1),不过有限制
3. 这题花头不大~
4. 我只能说论坛不太适合贴公式,哈哈
eallanwong 发表于 2013-3-3 09:24:14 | 显示全部楼层
第二题括号匹配用一个栈就行了吧?
从左到右扫描每一个字符,遇到左括号把这个做括号压入栈,然后遇到右括号就检查左括号,看是否能匹配,不能匹配就是Invalid。扫描完之后如果栈不为空也是Invalid。
chensc 发表于 2013-3-15 08:54:00 | 显示全部楼层
secretgu 发表于 2012-12-7 09:01 .鐣欏璁哄潧-涓浜-涓夊垎鍦
leetcode没玩过= =.鐣欏璁哄潧-涓浜-涓夊垎鍦
第四题我忘了我当初说的什么方法,刚临时想到一个方法是这样:
假设k=3, k_arr[] =  ...

这个方法好像不行吧?就以你的例子来说
k_arr如果是{1, 5, 10}怎么办?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
随出来一个5,然后找到了,返回下标1.. more info on 1point3acres.com
不是还存在么?
sddi 发表于 2013-9-23 22:15:20 | 显示全部楼层
试一试,谢谢楼主分享,我也去leetcode上看看去~
denev2004 发表于 2013-9-26 06:58:47 | 显示全部楼层
问下 电面怎么做这种题?说出来代码么?
pottermarkken 发表于 2013-10-7 06:31:39 | 显示全部楼层
Thanks a lot!

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-17 01:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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