一个python的面试题

要求read a file 然后writes the _X_ longest lines 到different file去。请问这个 “_X_” 是第几长的意思吗？
Don't use sort()/sorted().
顺便推荐一个mac上run code的软件——coderunner 非！常！好！用！

不是“第几长”，而是“最长的几个”

kinslayer 发表于 2014-1-21 09:58
应该是吧
btw 什么是“Don't use sort()”？

就是python built in function sort 或者 sorted 不让用

marine 发表于 2014-1-21 10:09
不是“第几长”，而是“最长的几个”

嗯嗯 是最长的几个

a naive method using Xn iterations - just do X scans over the file and take max each time while masking out the previous identified maxes.

co89757 发表于 2014-1-21 19:55
a naive method using Xn iterations - just do X scans over the file and take max each time while mask ...

正解 每次取出最长的那一行 然后取x次

假如用楼上的算法，那么如果文件里有N行的话，每次找最长的那行，那么最差的情况是，要read X次file，每次scan N行，所以时间复杂度是O(XN)。

可以用一个大小为X的min heap维护结果，只需要read一次文件，一开始建一个空的min heap，然后先扫描X行，然后根据行的长度的比较结果存入min heap中；之后每读入一行，比较当前行s的长度跟min heap的top中存的行t的长度，如果s的长度比t短，说明s比当前min heap中已经存入的X行都要短，因为这是个min heap，top元素的长度肯定是最短的，那么直接忽略s；如果s长度比t要长，那么说明t不是前X长的行，因为至少有s还有min heap中其他的X-1行要比t长，那么pop掉t，然后将s push入min heap中。这样，总共read 1次file，scan N行，每次操作min heap的时间复杂度是O(log X)，所以总共的时间复杂度是O(N log X)。

BTW，编辑任何源代码，一个vi就够了，编译任何一门语言，一个compiler + 一个Makefile就够了。

RickyYe 发表于 2014-2-18 09:12
假如用楼上的算法，那么如果文件里有N行的话，每次找最长的那行，那么最差的情况是，要read X次file，每次s ...

经提醒我才发现卧槽这个题目的状况不就是这不就是我刚上过的课上的一个原题么结果我当时做出来了这次都没反应过来…看来活用算法没那么简单啊…

良心题。