一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2694|回复: 35
收起左侧

G家实习面经

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

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

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

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

x
大概一个月前面的吧,现在有空才po上来
-google 1point3acres
两场back to back phone interview. 可能是因为本科,感觉比很多知道的master们面得简单很多。
. From 1point 3acres bbs
第一场:
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 其中一个)

总体觉得偏简单,感觉跪在第一面,第二面挺好的。

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

评分

1

查看全部评分

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

额 照你这个思路的话如果我没理解错的话,我有个疑惑:你如何区分 [11][1] 和 [1][11] 呢?因为它们对应的key都是111?.1point3acres缃
. 1point3acres.com/bbs
我后来想到的思路是用个2D array存到对应那个点为止的row 的和

比如有数据:
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.鏈枃鍘熷垱鑷1point3acres璁哄潧
7  15  24

这样子update就是O(n)

如果要求到 [1][1] 的sum的话,那就把array对应那个坐标的那个column在此坐标前的row sum 加起来。即3+14 = 17。这样子求sum就是O(n)

楼主不会Fenwick Tree, 所以这是我后来想到比较符合面试官口味的做法~~
回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 12:11:12 | 显示全部楼层
kelsie 发表于 2016-1-11 12:09
并没有到host match... 它后来要我加面,但因为我有offer deadline在眼前,所以withdraw掉了~~~

好可惜,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. from: 1point3acres.com/bbs
第一面第1题和我一样。-google 1point3acres
你host match上了么

并没有到host match... 它后来要我加面,但因为我有offer deadline在眼前,所以withdraw掉了~~~
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-11 12:09:57 | 显示全部楼层
第一面的第2题,如果我理解你的意思了。
他说能call很多次。. 1point3acres.com/bbs
那么我就用一个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. Waral 鍗氬鏈夋洿澶氭枃绔,
. visit 1point3acres.com for more.
第一面听口音应该不是中国人。。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 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
我很努力在看但我发现我看不懂你的思路 TaT 。。。而且我好久之前面的有点不太记得了,容我再考虑看看lol ...

update是o(n),不是直接扫一遍就可以了么?到了对的位置直接update。
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
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。. 鍥磋鎴戜滑@1point 3 acres
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)。. visit 1point3acres.com for more.

第二题感觉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. 1point 3acres 璁哄潧
区分简单啊,换成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. From 1point 3acres bbs
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), 更 ...
. 鍥磋鎴戜滑@1point 3 acres
请问array求25%数那题怎么做?有不用hashtable额外空间的方法吗?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 10:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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