一亩三分地论坛

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

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

google phone

[复制链接] |试试Instant~ |关注本帖
william_gong 发表于 2016-9-15 03:53:48 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚结束的phone一上来面试官找不到google doc连接了。。后来还是我给他发过去的。。。这个浪费了五分钟。。。。
一上来直接做题。
一个行和列分别是升序的二纬数组,把它从小到大输出出来。
比如这样子的
1 3 5
2 5 9. more info on 1point3acres.com
8 10 12
我想的是直接用heap解。。不知道有没有更快的办法。。
然后follow up问如何在多台 机器上进行。
我用的是分割数组然后多路merge的办法
要求写出merge的函数, 要求写split的函数
中间问了各个方法的时间复杂度。 我觉得heap解第一问的复杂度应该是O(n + m) 吧,nm分别是长宽。
这三个函数写了我35min, 加上开头耽误五分钟,最后留了五分钟让我问问题。
这次面的不太好,感觉跟面试官交流不畅,他有点心不在焉, 经常是我在说的不停那边一片沉默。。。(不知道是不是我口语太烂了。。) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
还是求一下onsite吧,想去google总部看看

. 1point3acres.com/bbs
补充内容 (2016-9-15 03:56): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
有点奇怪的是电话是从威斯康辛那打过来的,,,但我查他linkedin发现他在弯曲工作,,,. visit 1point3acres.com for more.

补充内容 (2016-9-17 01:54):
刚接到电话,过了

评分

5

查看全部评分

WhatsFLAG 发表于 2016-9-15 05:53:06 | 显示全部楼层
感谢楼主提供面经,首先祝楼主顺利拿到Onsite,其次想问一下关于follow up没有太理解意思,可不可能举个例子描述一下是什么样一个case呢?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| william_gong 发表于 2016-9-15 06:03:59 | 显示全部楼层
WhatsFLAG 发表于 2016-9-15 05:53
感谢楼主提供面经,首先祝楼主顺利拿到Onsite,其次想问一下关于follow up没有太理解意思,可不可能举个例 ...

就是问你, 如果给的数组特别大,而你又恰好有多台机器,这时候你怎么处理
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-15 08:28:57 | 显示全部楼层
感觉楼主答得不错吧。面试官不说话估计在记录。另外为什么heap的复杂度是O(m+n)?我感觉好像是O(mn)
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-15 08:30:33 | 显示全部楼层
Josh 发表于 2016-9-15 08:28
感觉楼主答得不错吧。面试官不说话估计在记录。另外为什么heap的复杂度是O(m+n)?我感觉好像是O(mn)

说错了,我觉得是O(mn log(mn))。。。感觉heap里面最多是mn个坐标?
回复 支持 反对

使用道具 举报

 楼主| william_gong 发表于 2016-9-15 08:33:52 | 显示全部楼层
Josh 发表于 2016-9-15 08:28
感觉楼主答得不错吧。面试官不说话估计在记录。另外为什么heap的复杂度是O(m+n)?我感觉好像是O(mn)

我觉得是o((m*n)log(m + n)).
我一开始直接说总复杂度在nlgn,,结果面试官说那我拿出来排序复杂度是多少呢。。?如果直接拿出来全排序的话就是nlgn复杂度。
我想了下,因为在heap里面的元素总数应该是“对角线”形状的,所以差不多应该是m+n个元素,mn是边长
. more info on 1point3acres.com


补充内容 (2016-9-15 08:35):
不过这里我很不确定。。当时随口说的m+n,面试官也没反驳,就让我用heap把代码写了。思路跟lc378很像
回复 支持 反对

使用道具 举报

Onedayw 发表于 2016-9-15 08:48:05 | 显示全部楼层
wisconsin办的号码。。。。。
回复 支持 反对

使用道具 举报

1370786136.1.3 发表于 2016-9-15 10:35:17 | 显示全部楼层
求问LZ, follow up 是不是分两步

1. split the matrix -> 分别用之前的方法得到n个sorted list;
2. merge sorted lists.
回复 支持 反对

使用道具 举报

 楼主| william_gong 发表于 2016-9-15 11:03:36 | 显示全部楼层
1370786136.1.3 发表于 2016-9-15 10:35
求问LZ, follow up 是不是分两步

1. split the matrix -> 分别用之前的方法得到n个sorted list;

我是这么做的,面试官也没反对
回复 支持 反对

使用道具 举报

tommy1122337 发表于 2016-9-15 12:45:54 | 显示全部楼层
可以看成merge k sorted list
可以從row看 也可以從column看
所以是 mn*log(m) or mn*log(n)
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-15 14:31:15 | 显示全部楼层
要是面试官用自己手机打电话的话显示是哪儿都有可能。一般人都不换号的,手机显示只是当年开号的地点。
回复 支持 反对

使用道具 举报

 楼主| william_gong 发表于 2016-9-15 21:02:12 | 显示全部楼层
确实,楼上的比我的快
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-29 10:25:34 | 显示全部楼层
为啥你2天就收到onsite了..我怎么还在坐等...
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-3 05:52:29 | 显示全部楼层
如果是大数据是不是可以直接把这个2D MATRIX看成N个1D SORTED ARRAY,然后跟求MERGE K SORTED LIST一样解决大数据问题
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-3 05:54:44 | 显示全部楼层
william_gong 发表于 2016-9-15 08:33
我觉得是o((m*n)log(m + n)).
我一开始直接说总复杂度在nlgn,,结果面试官说那我拿出来排序复杂度是多 ...

我怎么感觉这个题大数据在多机上也不好做,还不如这个数组存在磁盘上,然后看行或者列那个数量比较小,设置小的为k,然后建一个k大小的HEAP,第一次在所有行读取第一个进入HEAP,然后POP出最小的,然后把最小的所在行/列下一个元素读入HEAP
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-3 05:56:54 | 显示全部楼层
Josh 发表于 2016-9-15 08:30-google 1point3acres
说错了,我觉得是O(mn log(mn))。。。感觉heap里面最多是mn个坐标?

heap里最多放K个就行了,放那么多干嘛,把所有的行或者所有的列看成一维数组,保持每个一维数组最多一个在heap里,复杂度是o(mnlogk)
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-3 05:58:20 | 显示全部楼层
william_gong 发表于 2016-9-15 11:03
. From 1point 3acres bbs我是这么做的,面试官也没反对

求问多机怎么merge sorted list,他这每一行都排好序了,你分开放到其他机器里意义也不大啊,难道就是为了放到其他机器内存里,然后一个一个往这个机器读?网络带宽可能也很慢,那LATENCY感觉存N个文件,每一行一个文件,然后本机往内存读也差不多
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 22:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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