google phone

刚结束的phone一上来面试官找不到google doc连接了。。后来还是我给他发过去的。。。这个浪费了五分钟。。。。
一上来直接做题。
一个行和列分别是升序的二纬数组，把它从小到大输出出来。
比如这样子的
1 3 5
2 5 9
8 10 12
我想的是直接用heap解。。不知道有没有更快的办法。。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

康辛那打过来的，，，但我查他linkedin发现他在弯曲工作，，，

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

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

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



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

william_gong 发表于 2016-9-15 08:33
我觉得是o((m*n)log(m + n)).
我一开始直接说总复杂度在nlgn，，结果面试官说那我拿出来排序复杂度是多 ...

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

william_gong 发表于 2016-9-15 11:03
我是这么做的，面试官也没反对

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

感谢楼主提供面经，首先祝楼主顺利拿到Onsite，其次想问一下关于follow up没有太理解意思，可不可能举个例子描述一下是什么样一个case呢？

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

就是问你， 如果给的数组特别大，而你又恰好有多台机器，这时候你怎么处理

感觉楼主答得不错吧。面试官不说话估计在记录。另外为什么heap的复杂度是O(m+n)？我感觉好像是O(mn)

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

说错了，我觉得是O(mn log(mn))。。。感觉heap里面最多是mn个坐标？

wisconsin办的号码。。。。。

1370786136.1.3 发表于 2016-9-15 10:35
求问LZ， follow up 是不是分两步

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

我是这么做的，面试官也没反对

可以看成merge k sorted list
可以從row看 也可以從column看
所以是 mn*log(m) or mn*log(n)