google phone

要是面试官用自己手机打电话的话显示是哪儿都有可能。一般人都不换号的，手机显示只是当年开号的地点。

确实，楼上的比我的快

为啥你2天就收到onsite了..我怎么还在坐等...

如果是大数据是不是可以直接把这个2D MATRIX看成N个1D SORTED ARRAY，然后跟求MERGE K SORTED LIST一样解决大数据问题

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

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

Josh 发表于 2016-9-15 08:30
说错了，我觉得是O(mn log(mn))。。。感觉heap里面最多是mn个坐标？

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

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

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