News for hackers. Stuff that matters.
Re:LINQ Ruined My Favorite Interview Question by kyllo on Thursday July 11, 2013 @06:46PM (#6029786)
Ooh, this is fun!

In Ruby, without imports/requires:

    def toptenwords(str)
    	words = str.split
	words.sort_by{|word| words.count(word)}.uniq.reverse.take(10)
    end
or as a one-liner, without any variable declarations in the function scope:

    def toptenwords(str) str.split.sort_by{|word| str.split.count(word)}.uniq.reverse.take(10) end
Re:LINQ Ruined My Favorite Interview Question by kragen on Friday July 12, 2013 @01:27AM (#6031083)
I think this version and spenuke's version are impractically slow, but yours is actually O(N²). If you give it an 824 000 word input, it will do 0.6 quadrillion word comparisons, which you will probably not be willing to wait for. A more practical solution:

    counts = Hash.new { 0 }
    IO.read('bible-pg10.txt').split.each { |w| counts[w] += 1; }
    counts.keys.sort_by { |w| -counts[w] }.take 10
This is still O(N lg N) instead of O(N lg 10) like the Python version, but it's good enough this time; it still gave me ["the", "and", "of", "to", "And", "that", "in", "shall", "he", "unto"] reasonably quickly.

I'd be interested to see if there's a way to do this in a single expression in Ruby.

Re:LINQ Ruined My Favorite Interview Question by kyllo on Friday July 12, 2013 @02:30AM (#6031244)
I actually was working on a hash-based solution first, using group_by, but I switched to using just array after seeing the Python version. I didn't really think about the time complexity of the count operation inside the sort_by operation, thanks for pointing that out.

You definitely can do a hash-based solution in a single expression in Ruby. Here's a very ugly and kludgy example that you could probably improve on if you wanted to. I don't think it's n^2 because the group_by just counts the occurrences of each word and returns a hash where the count is the key:

str.split.group_by{|w| str.split.count(w)}.sort_by{|k,v| k}.reverse.flatten.uniq.keep_if{|w| w.is_a?(String)}.take(10)

I'm also trying to work out a better way to do this using "chunk" because although hashes are fast to access, they are not fundamentally sortable, and sort_by returns a 2d array just like chunk does anyway.