doStuff = require("doStuff");
var result = doStuff(theString);
I would expect a good candidate to:
1. know that a heap is optimal here (remembering whether Counter uses it is optional)
2. express reluctance to implement it from scratch because surely the stdlib can do it better.
So IMHO using libraries like this ruins the question only in the sense of showing its not a challenge for the candidate. Something so simple should not take a page of code.
Creating a heap is O(n) if I remember correctly, so that may well be the most efficient solution.
Just like math homework back in the day, the teacher didn't do it to check your answer, they did it to check how you arrived at your answer.
Therefore, I am unlikely to take the job.
Just to give another example, our consulting company still gets requests for projects to be deployed against Java 1.4!
d = {}
for word in s1.split(' '):
try:
d[word] += 1
except KeyError:
d[word] = 1
print [(x, d[x]) for x in sorted(d, key=d.get, reverse=True)][:10] d3.entries((s.split(" ").reduce(function(p, v){
v in p ? p[v]++ : p[v] = 1;
return p;}, {})))
.sort(function(a, b){ return a.value > b.value; })
.map(function(d){ return d.key;})
.slice(-10); def top_ten(s):
words = s.split(' ')
word_list = set(words)
return sorted(word_list, key=lambda x: words.count(x))[:10]
But I like the readability of this solution and there's a strong argument to be made for it on that basis, especially if the string is short. If this were a job interview, this would be a totally acceptable solution, though it'd be important to be able to discuss why other solutions might be faster and why you prefer this one anyway.
I thought the whole point of Big O / asymptotic analysis is that you can ignore lower-order terms and constant factors because they are insignificant for any appreciably large input size. And also because the lower order terms and constant factors vary too much depending on the programming language, the compiler or VM, the hardware, etc.
At any rate, I wanted to test this out, so I made a naive benchmark for running these functions. The dict solution was ten times faster (0.0011s vs 0.015s) than the list version with ~1350 words. The dict solution ran in 0.13s at ~162,000 words, while I waited a couple minutes before killing the list version on that input.
def top_ten(s):
words = s.split()
return sorted(set(words), key=words.count, reverse=True)[:10]
You should always compare your results to what is expected. For a problem like this, use a small set of test data that can easily be counted and sorted in your head or on paper.
You forgot reverse=True and your results show the 10 least common words. ;)
This kind of error happens to all of us. That's why we have unit tests and QA teams. If you made this mistake during an interview I wouldn't give it much importance and we would have a good laugh about it.
In Ruby, without imports/requires:
def toptenwords(str)
words = str.split
words.sort_by{|word| words.count(word)}.uniq.reverse.take(10)
end
def toptenwords(str) str.split.sort_by{|word| str.split.count(word)}.uniq.reverse.take(10) end counts = Hash.new { 0 }
IO.read('bible-pg10.txt').split.each { |w| counts[w] += 1; }
counts.keys.sort_by { |w| -counts[w] }.take 10
I'd be interested to see if there's a way to do this in a single expression in Ruby.
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.
d[word] = d.get(word,0) + 1
dictionary.get is quite useful.
Also, I'd consider s.split(None), instead of s.split(' '). It will group whitespace, so that any double space or other whitespace is collapsed into one delimiter.