聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4271|回复: 35
收起左侧

G家实习面经

[复制链接] |试试Instant~ |关注本帖
kelsie 发表于 2016-1-11 11:50:59 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类General 本科 实习@Google - 网上海投 - 技术电面  | Other | 其他

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

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

x
大概一个月前面的吧,现在有空才po上来

两场back to back phone interview. 可能是因为本科,感觉比很多知道的master们面得简单很多。

第一场:. 一亩-三分-地,独家发布
1. 在一串string里把所有的vowel(aeiou) reverse
e.g. howareyou -> huworeyao

2. 跟leetcode: Range Sum Query 2D - Mutable 这题很像,有两个method, 一个是update matrix的某个坐标的值,一个是求从(0,0) 到给定坐标的sum
跟leetcode不一样的地方就是它求sum是从(0,0)开始到给定坐标的
我写了两种,一种是update O(1) 求sum O(n^2); 另一种是update O(n^2) 求sum O(1). 但感觉面试官一直在说万一两个method被call同样的次数,有木有另外的解,是要我写出两个method都是O(n)的情况。但是我当时脑抽,没特别注意到是求从(0,0)开始的sum, 应该很简单能写出来才对。面完就觉得这题砸了。。。


第二场:
1. set difference

.留学论坛-一亩-三分地
2. 求一个 sorted array 里,一个出现了25%以上的数。(如果有多个,只需return 其中一个). 牛人云集,一亩三分地
. more info on 1point3acres
总体觉得偏简单,感觉跪在第一面,第二面挺好的。 来源一亩.三分地论坛.

然后后来圣诞假什么的结果出得很慢,最后要我加面,但因为我有offer deadline在眼前,忍痛withdraw掉了~~~

评分

1

查看全部评分

 楼主| kelsie 发表于 2016-1-11 15:34:02 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-11 12:28. from: 1point3acres
update是o(n),不是直接扫一遍就可以了么?到了对的位置直接update。
sum是o(n),假如开始是[0][0] = 1 ...

额 照你这个思路的话如果我没理解错的话,我有个疑惑:你如何区分 [11][1] 和 [1][11] 呢?因为它们对应的key都是111?

我后来想到的思路是用个2D array存到对应那个点为止的row 的和.本文原创自1point3acres论坛

比如有数据:
1 2 3.留学论坛-一亩-三分地
4 5 6
7 8 9

那那个array里的值就是:
1  3   6
4  9  15
7 15  24

如果要update [1][1] 从5变为10的话,那就把array对应那个坐标及往后的row sum update。最后对应的array就变为
1   3   6
4  14  19
7  15  24

这样子update就是O(n). Waral 博客有更多文章,

如果要求到 [1][1] 的sum的话,那就把array对应那个坐标的那个column在此坐标前的row sum 加起来。即3+14 = 17。这样子求sum就是O(n)
. 1point3acres
楼主不会Fenwick Tree, 所以这是我后来想到比较符合面试官口味的做法~~
回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 12:11:12 | 显示全部楼层
kelsie 发表于 2016-1-11 12:09
并没有到host match... 它后来要我加面,但因为我有offer deadline在眼前,所以withdraw掉了~~~
. 围观我们@1point 3 acres
好可惜,lz题不难,加面肯定过。
回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 11:57:37 | 显示全部楼层
第一面第1题和我一样。
你host match上了么
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 12:00:25 | 显示全部楼层
第2面的set difference。是求2个set里面不同的东西么?你第一场是中国人面的么
回复 支持 反对

使用道具 举报

 楼主| kelsie 发表于 2016-1-11 12:09:17 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-11 11:57
第一面第1题和我一样。
你host match上了么
. 牛人云集,一亩三分地
并没有到host match... 它后来要我加面,但因为我有offer deadline在眼前,所以withdraw掉了~~~
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 12:09:57 | 显示全部楼层
第一面的第2题,如果我理解你的意思了。
他说能call很多次。
那么我就用一个function,把从[0,0]到[x,y]的range里,所有sum算出来,放进map里面。
比如,1-3是range,我在map里面 key=1,value =1; key=2; value = 3; key =3, value =6.
你要是想求从1到2个sum,我直接map.get(2)就ok了?
回复 支持 反对

使用道具 举报

 楼主| kelsie 发表于 2016-1-11 12:12:29 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-11 12:00
第2面的set difference。是求2个set里面不同的东西么?你第一场是中国人面的么

set difference具体题目就是有两个set, set A & set B. 找在A中出现但不在B中出现的数。可以把两个set 看作都是sorted array

第一面听口音应该不是中国人。。。

评分

1

查看全部评分

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

使用道具 举报

 楼主| kelsie 发表于 2016-1-11 12:22:47 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-11 12:09
第一面的第2题,如果我理解你的意思了。
他说能call很多次。
那么我就用一个function,把从[0,0]到[x,y] ...

我很努力在看但我发现我看不懂你的思路 TaT 。。。而且我好久之前面的有点不太记得了,容我再考虑看看lol。。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 12:28:58 | 显示全部楼层
kelsie 发表于 2016-1-11 12:22. from: 1point3acres
我很努力在看但我发现我看不懂你的思路 TaT 。。。而且我好久之前面的有点不太记得了,容我再考虑看看lol ...

update是o(n),不是直接扫一遍就可以了么?到了对的位置直接update。. Waral 博客有更多文章,
sum是o(n),假如开始是[0][0] = 1, [0][1] =3, [1][0]=3, [1][1]=7.
写一个function开始遍历整个2 d array,用map记录sum的值.
以下是map里面的值。
key 00 , value 1 . From 1point 3acres bbs
key 01, value 4  因为 01是从[0][0]到[0][1]的sum。 是1+3 =4. 一亩-三分-地,独家发布
key 10, value 7 因为10是[0][0]到[1][0]的sum。 是1+3 +3=7
key 11, value 14 因为10是[0][0]到[1][1]的sum。 是1+3 +3 +7=14.
比如你想查从[0][0]到[1][0]的sum,你就map.get(10)就可以知道了?
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-11 14:12:13 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-11 12:28
update是o(n),不是直接扫一遍就可以了么?到了对的位置直接update。. From 1point 3acres bbs
sum是o(n),假如开始是[0][0] = 1 ...

请问从(0,0)开始到给定坐标是指的是一条线上的点吧?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 14:17:18 | 显示全部楼层
wtcupup 发表于 2016-1-11 14:12
请问从(0,0)开始到给定坐标是指的是一条线上的点吧?

什么是一条线上的点
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-11 14:22:38 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-11 14:17
什么是一条线上的点

比如说(0,0),(0,1),(1,1),(1,0), 一条线上点的sum就是(0,0)+(1,1)
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-11 14:23:44 | 显示全部楼层
kelsie 发表于 2016-1-11 12:12
set difference具体题目就是有两个set, set A & set B. 找在A中出现但不在B中出现的数。可以把两个set 看 ...

SetB.removeAll(SetA);  ??
回复 支持 反对

使用道具 举报

163 发表于 2016-1-11 14:59:27 | 显示全部楼层
第一题sum range 2D - mutable,是用2D线段树或者Fenwick Tree做,算法复杂度: 初始化 O(n (\log n)^2), 更新坐标点 O( (\log n)^2), 查询 O( (\log n)^2)。

第二题感觉sorted array确实稍微简单,其实可以问你随便一个array里面出现超过25%的数。
回复 支持 反对

使用道具 举报

 楼主| kelsie 发表于 2016-1-11 15:37:55 | 显示全部楼层
163 发表于 2016-1-11 14:59
第一题sum range 2D - mutable,是用2D线段树或者Fenwick Tree做,算法复杂度: 初始化 O(n (\log n)^2), 更 ...

那个sum range 2D - mutable 感觉面试官并没有要我用Fenwick Tree哎。我到最后实在山穷水尽了然后听过一个大神朋友讲起过Fenwick Tree (但自己并不会implement), 我就尝试着问面试官知不知道Fenwick Tree, 然后就感觉面试官并没有让我再讲下去,草草结束了面试。。。lol
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 15:49:32 | 显示全部楼层
kelsie 发表于 2016-1-11 15:34
额 照你这个思路的话如果我没理解错的话,我有个疑惑:你如何区分 [11][1] 和 [1][11] 呢?因为它们对应 ...

区分简单啊,换成string 11 1和1 11. 读取的时候,string.split(" "). 第1个值是空格前的,第2个是空格后的。
回复 支持 反对

使用道具 举报

 楼主| kelsie 发表于 2016-1-11 16:00:29 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-11 15:49
区分简单啊,换成string 11 1和1 11. 读取的时候,string.split(" "). 第1个值是空格前的,第2个是空格后 ...

这样子仿佛跟我后来想的差不多~~那应该就是这样了吧~~
回复 支持 反对

使用道具 举报

jacky841102 发表于 2016-1-11 21:29:39 | 显示全部楼层
请问 2. 求一个 sorted array 里,一个出现了25%以上的数。(如果有多个,只需return 其中一个)怎么做?

我的想法是取第一个element,四分位的element,median,四分之三位的element,最后一个element 做candidates
binary search 每个 candidate 的 range (leetcode 34),如果candidate的range大于array长度的1/4就是答案
有其他解法吗?
回复 支持 反对

使用道具 举报

jacky841102 发表于 2016-1-11 22:01:37 | 显示全部楼层
163 发表于 2016-1-11 14:59
第一题sum range 2D - mutable,是用2D线段树或者Fenwick Tree做,算法复杂度: 初始化 O(n (\log n)^2), 更 ...

请问array求25%数那题怎么做?有不用hashtable额外空间的方法吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-22 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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