一亩三分地论坛

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

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

热乎乎的 Google 电面 11/13

[复制链接] |试试Instant~ |关注本帖
lcl3356897 发表于 2015-11-14 06:38:29 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完。。然后手抖打完了。。然后手滑了后退就没了。。。求RP啊啊啊

面试官好像是三哥,口音几乎没有,人还挺好,可能也是新手,也有点紧张,而且卡时间卡的特别严,说45分钟就是45分钟
-google 1point3acres
上来没有问Behavior,直接开干
. Waral 鍗氬鏈夋洿澶氭枃绔,
第一题
  现在给你一个list of words (你的 vocabulary), 然后给一个字符串,让你判断这个字符串是不是singleTypo,就是有且仅有一个字符打错了 <=> 也就是替换一个字符能变成list里边的单词. more info on 1point3acres.com
  挺类似 LC 的 One Edit Distance, 小哥为了简便,把  插入一个字符能变成list里边的单词  的这种情况去掉了
Example :
[size=13.3333px]     vocab = ['apple', 'pineapple', 'banana', 'cucumber']
       singleTypo('adple')   # True  把第二位的 d 改成 p 就行
       singleTypo('addle')   # False  有俩不一样
       singleTypo('aple')    # False   缺少字符
       singleTypo(‘apple’) #False     一样也不行

题挺简单
小哥说好,咱们再来一个
然后等了好久。。估计临时找题去了

第二题
  给你一个 infinite 的 2维 space, 实现两个方法
(1) update(x, y, v) : 更新 x,y 这个位置上的值变成v  (暗含两种情况, 如果 x,y 已经有值,就更新  如果 x,y 没值,就是说原来的矩阵大小还没到 x,y 这点,就得往 x,y 这放一个值)
(2) query(x1, y1, x2, y2) : 算出 这两个点之间的所有的值的和

我一看下边的两个方法,我擦,这不面经么!还出现过两次!还 update 和 query
我就说,那就用二维线段树做!
小哥可能没太理解我的解法,因为我题都没理解对。。。 小哥就说 那你写吧,边写边解释
然后我就开始写

刚写完建树,小哥说,你这个感觉不对啊,题目要求的是 infinite 的空间哇
我当时就傻了。。。WTF!!!啊啊啊啊,纯傻X了

然后时间就剩几分钟了,我就按照 LC 的 Range Sum Query 2D - Immutable 的方法实现了 query 方法
刚写完query就到点了

小哥说,到点了,别写了,问问题吧。。。卡时间太严了,其实当时我也没太想好 update 怎么处理

我就大概问了问。。。
然后就Bye-Bye了


哎。。。没仔细审题啊,就一个单词啊啊啊啊

跪求Onsite
. visit 1point3acres.com for more.



鏉ユ簮涓浜.涓夊垎鍦拌鍧.




鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-11-19 04:06):
估计是第二题的原因吧。。。收到HR电话要加面。。

评分

1

查看全部评分

sparksfly 发表于 2015-11-14 07:11:24 | 显示全部楼层
楼主早日拿offer啊

楼主请教一个问题,关于第二题,所为的两个点之间所有值的和是什么意思
. more info on 1point3acres.com比如有一个空间
[1,1,1]
[2,2,2]
[3,3,3]
那么求query(0, 0, 2, 2)那么就是1+2+3=6?
如果是query(0, 0, 2, 1)那么是什么?这个线上不是只有这两个数吗就是1+3=4?
而你说如果不是infinite的空间可以用线段树去解,我不是很理解,能说明一下或者发一个链接吗?

非常感谢~~
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-11-14 07:21:25 | 显示全部楼层
sparksfly 发表于 2015-11-14 07:11
楼主早日拿offer啊. 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主请教一个问题,关于第二题,所为的两个点之间所有值的和是什么意思
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢祝福哈

query(x1, y1, x2, y2) 指的是 (x1, y1) 为左上角,(x2, y2) 为右下角的submatrix的所有元素的和-google 1point3acres

[1,1,1]
[2,2,2] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
[3,3,3]
求query(0, 0, 2, 2) 就是 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 + 3
如果是query(0, 0, 2, 1)那么是什么 1 + 1 + 2 + 2 + 3 + 3

不是infinite 的话,先考虑一维的话,你可以上 LintCode 搜线段树,然后看看类似的题

二维线段树简单的方法就是用线段树数组,还有什么树套树,四叉树之类的方法
回复 支持 反对

使用道具 举报

sparksfly 发表于 2015-11-14 08:04:10 | 显示全部楼层
lcl3356897 发表于 2015-11-14 07:21
-google 1point3acres谢祝福哈. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

query(x1, y1, x2, y2) 指的是 (x1, y1) 为左上角,(x2, y2) 为右下角的submatrix的所有元素 ...

感谢楼主的分享。

我还有一点问题就是关于线段树
对于刚刚我们提到的那个数组,怎样用线段树去实现啊?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

麻烦楼主了~
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-14 08:06:07 | 显示全部楼层
lcl3356897 发表于 2015-11-14 07:21
谢祝福哈

query(x1, y1, x2, y2) 指的是 (x1, y1) 为左上角,(x2, y2) 为右下角的submatrix的所有元素 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Lz, 我没太明白 第二题为什么不能用二维线段树做呢?
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-11-14 12:23:04 | 显示全部楼层
sparksfly 发表于 2015-11-14 08:04
感谢楼主的分享。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我还有一点问题就是关于线段树
. 1point 3acres 璁哄潧
比如有个一维数组
0, 1, 2, 3//index -google 1point3acres
1, 2, 3, 4
                                                  root [0, 3] 10
                 left-child [0,1] 3                                      right-child [2,3] 7
left-child [0,0] 1      right-child[1,1] 2       left-child[2,2] 3         right-child[3,3] 4.1point3acres缃

如果是二维的话,用一个数组保存每行的根
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-11-14 12:25:58 | 显示全部楼层
queeniejing 发表于 2015-11-14 08:06
Lz, 我没太明白 第二题为什么不能用二维线段树做呢?

比如现在只有两个点, (0, 0) 的值是1, (10^6, 10^6) 的值是1
这样的话,时间和空间都太大
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果是固定的大小 M * N 的话就好办
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-14 12:40:23 | 显示全部楼层
第二题,直接x,y两个方向都上tree是不是就成了。map<int, map<int, int>> -- x, <y, v>
回复 支持 反对

使用道具 举报

QueenieLi 发表于 2015-11-17 13:19:17 | 显示全部楼层
想了好半天只能想出一个brute force的O(n*n)方法解决怎么比较两个字符串只有一个字符不相等,楼主能给个提示更好地方法吗?
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-11-17 14:05:06 | 显示全部楼层
QueenieLi 发表于 2015-11-17 13:19
想了好半天只能想出一个brute force的O(n*n)方法解决怎么比较两个字符串只有一个字符不相等,楼主能给个提 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一题的话.1point3acres缃
我当时的解法是,因为没有长度不等的情况,所以每次都过一遍vocabulary,然后拿出和查询单词长度相等的字符串进行比对。比对的时候,从头到尾扫一遍,看有多少个字符是不一样的, 这个是 O(n * k), n是多少个长度相等的,k是要查找的字符串的长度.1point3acres缃
还有一种解法是替换每个位置上的字符,看能不能成功,复杂度是 O(26 * k), k 是要查找的字符串的长度
另外一种是字典树,如果没有匹配成功,用别的替换看行不行
回复 支持 反对

使用道具 举报

QueenieLi 发表于 2015-11-18 03:16:07 | 显示全部楼层
lcl3356897 发表于 2015-11-17 14:05
第一题的话 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我当时的解法是,因为没有长度不等的情况,所以每次都过一遍vocabulary,然后拿出和查询单词 ...

感谢楼主~最近是不是很多都在考字典树,觉得好多面经里出现了这个呢
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-11-18 05:20:23 | 显示全部楼层
QueenieLi 发表于 2015-11-18 03:16. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
感谢楼主~最近是不是很多都在考字典树,觉得好多面经里出现了这个呢

啊,这个母鸡啊
不过prefix tree挺常用的吧,也算是基本功?
回复 支持 反对

使用道具 举报

cyan_lin 发表于 2015-11-18 05:58:12 | 显示全部楼层
感觉第二问需要存两个arraylist,每个链表的元素是<x,y,v>.第一个是以x大小递增排列,x大小相同则以y大小递增排列。第二个相反,以y大小递增排列,y大小相同则以x大小递增排列。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

update的时候可以binary search,分别往两个链表里插入新元素。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
算range的时候现在两个表里分别找出相应的点的位置,然后把两个点之间共有的元素加起来...

不好意思我算是大半个外行...听起来解法有点蠢...
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-11-18 06:34:37 | 显示全部楼层
cyan_lin 发表于 2015-11-18 05:58
感觉第二问需要存两个arraylist,每个链表的元素是.第一个是以x大小递增排列,x大小相同则以y大小递增排列 ...
. from: 1point3acres.com/bbs
嗯嗯,你这个解法很好了。就是一开始我没看到无限的空间,就直接想到要O(1)的方式来取query了。。. 鍥磋鎴戜滑@1point 3 acres
.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果用ArrayList, BinarySearch寻点的目的是为了O(logN)时间复杂度,JAVA里边有个TreeMap,这个就能直接实现了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-6 23:23:02 | 显示全部楼层
这个题Infinite是不是实现O(m) query, O(n)update就行了?
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-12-7 08:56:46 | 显示全部楼层
bobzhang2004 发表于 2015-12-6 23:23
这个题Infinite是不是实现O(m) query, O(n)update就行了?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
其实没有要求.鐣欏璁哄潧-涓浜-涓夊垎鍦
query多,update少
query少,update多
query,update一样多
这三种可以当follow up
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 23:46:28 | 显示全部楼层
请问楼主这道类似 LC 的 One Edit Distance的题,是拿出每一个单词和词典里面的单词比较?这样的话,如果词典很大的话,时间复杂度是很高的啊,为什么不将词典放在hashmap中,然后用两个for循环,一个一个的替代现在这个单词,比如adple,然后再hashmap中找呢,既然总过只有26个字母,且每个单词的长度都是比较短的,这样就会使contant的时间复杂度了啊?
回复 支持 反对

使用道具 举报

starcroce 发表于 2015-12-10 07:11:10 | 显示全部楼层
cyan_lin 发表于 2015-11-18 05:58
感觉第二问需要存两个arraylist,每个链表的元素是.第一个是以x大小递增排列,x大小相同则以y大小递增排列 ...

不熟悉java,不太清楚java的arraylist的实现。。。不过想问下,arraylist可以做到既满足sorted array那样的binary search,又满足linked list那样在指定位置的O(1)插入么?按照我的理解,在binary search插入之后,插入位置之后的所有元素的index都要随之改变,那么总的来说插入其实是O(n)的复杂度?
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-12-10 12:42:11 | 显示全部楼层
starcroce 发表于 2015-12-10 07:11-google 1point3acres
不熟悉java,不太清楚java的arraylist的实现。。。不过想问下,arraylist可以做到既满足sorted array那样 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
java里边List是借口
可以用ArrayList来实现,查找是O(1), 插入是O(N)
也可以用LinkedList实现,查找是O(N), 插入是O(1)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 14:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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