4
\$\begingroup\$

This is a challenge question from codeeval.com:

Write a program which reads a file and prints to stdout the specified number of the longest lines that are sorted based on their length in descending order. Input sample:

Your program should accept a path to a file as its first argument. The file contains multiple lines. The first line indicates the number of lines you should output, the other lines are of different length and are presented randomly. You may assume that the input file is formatted correctly and the number in the first line is a valid positive integer.

For Example:

2 
Hello World
CodeEval 
Quick Fox
A
San Francisco

Output sample:

Print out the longest lines limited by specified number and sorted by their length in descending order.

For example:

San Francisco 
Hello World

I think my code is pretty readable.

lines = IO
  .readlines(ARGV.first)

puts lines
  .drop(1)
  .sort_by(&:length)
  .last(lines.first.to_i)
  .reverse
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Reading a file named on the command line is a common task. I suggest making use of the ARGF to accomplish that.

Not all lines of the input are to be treated uniformly. Since the first line is to be treated differently, I suggest defining lines to exclude it.

top_n, *lines = ARGF.to_a
puts lines.sort_by(&:length).last(top_n.to_i).reverse
\$\endgroup\$
1
\$\begingroup\$

Your sort_by + last implementation is simple enough and looks quite good. I know it's probably not the case but, just for fun, let's imagine you had a humongous file to process; it wouldn't have a terribly nice space complexity (O(n)). In this case, I'd use a priority queue (let's say with logarithmic time of insertions/removals):

lines = open(ARGV.first).lines
heap_size = lines.first.to_i
sorted_queue = lines.reduce(PriorityQueue.new) do |queue, line|
  queue.add(line.size, line).limit(heap_size)
end
sorted_queue.values.each { |line| puts(line) }

The final performance would be O(n * log K) time, and constant space K (the size of the heap). The implementation of PriorityQueue is left as an exercise for the reader ;)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.