News for hackers. Stuff that matters.
Re:LINQ Ruined My Favorite Interview Question by shill on Thursday July 11, 2013 @10:49AM (#6026346)
Oh, we can use our favorite language in our new job? Here is a Python solution.

    from collections import Counter
    Counter(s1.split(' ')).most_common(10)
Re:LINQ Ruined My Favorite Interview Question by untog on Thursday July 11, 2013 @10:51AM (#6026357)
Well, sure, once you're allowed to use external libraries anything is a one line solution. In JS:

   doStuff = require("doStuff");
   var result = doStuff(theString);
isn't JS so efficient?!?
Re:LINQ Ruined My Favorite Interview Question by jkrems on Thursday July 11, 2013 @10:55AM (#6026382)
It looks like collections is part of the standard library: http://docs.python.org/2/library/collections.html. I think this disqualifies your JS solution, as long as doStuff isn't some fancy nodejs core module I missed.
Re:LINQ Ruined My Favorite Interview Question by untog on Thursday July 11, 2013 @11:13AM (#6026511)
I think the point still stands though, when you think of it as an interview question. The point is to get to the bottom of how the candidate would process such a query themselves, not to test their knowledge of the core libraries of their favourite language. I feel like that's what the post author meant when he said that LINQ had "ruined" the question- because it kind of does the same thing.
Re:LINQ Ruined My Favorite Interview Question by rhizome on Thursday July 11, 2013 @02:11PM (#6027897)
Isn't it kind of axiomatic that any question that provides for a concise and measurable solution will eventually be refactored into a library? It seems like kind of a weakness in these kinds of "programmer" questions, that they all regress to trivia. Why not an open-ended business problem and/or deliverables-type question? I'm sure that would speak more to the daily job, where I've never heard of someone being tasked with "OK, find the top 10 words by frequency in a random Wikipedia article."
Re:LINQ Ruined My Favorite Interview Question by untog on Thursday July 11, 2013 @02:56PM (#6028316)
Surely the 'trivia' in this instance is knowing the names of libraries, as opposed to be able to think through programming concepts?

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.

Re:LINQ Ruined My Favorite Interview Question by rhizome on Thursday July 11, 2013 @04:33PM (#6029015)
My memory of the math homework you describe brings up two images: geometry proofs and story problems. Never did I have to explain multiplication when doing my times tables, nor quadratics.
Re:LINQ Ruined My Favorite Interview Question by cben on Thursday July 11, 2013 @01:33PM (#6027578)
collections.Counter.most_common() uses heapq.nlargest() which is slightly more efficient than a full n*log n sort. But implementing a heap correctly from scratch is I guess outside the scope the OP intends for the interview question.

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.

Re:LINQ Ruined My Favorite Interview Question by klipt on Thursday July 11, 2013 @04:39PM (#6029067)
> collections.Counter.most_common() uses heapq.nlargest() which is slightly more efficient than a full n*log n sort.

Creating a heap is O(n) if I remember correctly, so that may well be the most efficient solution.

Re:LINQ Ruined My Favorite Interview Question by CanSpice on Thursday July 11, 2013 @03:29PM (#6028555)
"Sorry, we're stuck with Python 2.3.7 and collections isn't part of the standard library."
Re:LINQ Ruined My Favorite Interview Question by wiredfool on Thursday July 11, 2013 @04:32PM (#6029013)
"""Thank you, I think I've heard enough. I don't think continuing the interview would be a productive use of time."""
Re:LINQ Ruined My Favorite Interview Question by yen223 on Thursday July 11, 2013 @10:25PM (#6030544)
I like the fact that you triple-quoted that statement.
Re:LINQ Ruined My Favorite Interview Question by kenko on Thursday July 11, 2013 @05:12PM (#6029260)
Because of an older version of python?!
Re:LINQ Ruined My Favorite Interview Question by wiredfool on Thursday July 11, 2013 @05:26PM (#6029335)
If they're stuck on a version of software that hasn't been supported in 5 years for bugs or security with a set of features that was originally released nearly 10 years ago, it means that there are some culture issues in the workplace that will most likely drive me insane.

Therefore, I am unlikely to take the job.

Re:LINQ Ruined My Favorite Interview Question by pjmlp on Friday July 12, 2013 @03:40AM (#6031388)
Most companies are not startups, installing software as soon as new releases get available.

Just to give another example, our consulting company still gets requests for projects to be deployed against Java 1.4!

Re:LINQ Ruined My Favorite Interview Question by shill on Thursday July 11, 2013 @11:03AM (#6026434)
Without imports:

    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]
Re:LINQ Ruined My Favorite Interview Question by wiredfool on Thursday July 11, 2013 @02:23PM (#6028030)
Or, use a defaultdict(int), or more in line with yours:

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.

Re:LINQ Ruined My Favorite Interview Question by bereft_orange on Thursday July 11, 2013 @06:42PM (#6029763)
or just `s.split()`
Re:LINQ Ruined My Favorite Interview Question by shill on Thursday July 11, 2013 @02:43PM (#6028207)
I didn't know about split(None). Thanks!
Re:LINQ Ruined My Favorite Interview Question by spenuke on Thursday July 11, 2013 @12:11PM (#6026955)
I'm a newbie, but the question seemed approachable so I went for it. This is what I came up with. (Python, btw.)

  def top_ten(s): 
    words = s.split(' ') 
    word_list = set(words) 
    return sorted(word_list, key=lambda x: words.count(x))[:10]
The question didn't ask for word counts, so I didn't see the need for a dictionary. I'd appreciate any advice on my solution. I'd be thrilled if I'm not too far off from being capable of starting to apply for jobs.
Re:LINQ Ruined My Favorite Interview Question by abecedarius on Thursday July 11, 2013 @01:55PM (#6027751)
Nice. Just a little fixing and polishing:

    def top_ten(s):
        words = s.split()
        return sorted(set(words), key=words.count, reverse=True)[:10]
(to get the most common words instead of the least).
Re:LINQ Ruined My Favorite Interview Question by matchu on Thursday July 11, 2013 @01:37PM (#6027613)
The need for the dictionary shows up when your text gets significantly large. Each call to `words.count` is going to re-examine each word of the text to count 'em up, so, if n is the number of words in the text, and m is the number of distinct words in the text, then this solution is at least O(mn + nlog(n)) whereas the dictionary-based solution is O(nlog(n)). That is, we're re-reading the word list over and over, whereas the dict-based solution only reads it once. It's therefore more likely to be more efficient.

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.

Re:LINQ Ruined My Favorite Interview Question by kyllo on Friday July 12, 2013 @12:34AM (#6030934)
Isn't the difference between O(mn + nlog(n)) vs O(nlog(n)) running time going to get less significant as the value of n gets larger?

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.

Re:LINQ Ruined My Favorite Interview Question by spenuke on Friday July 12, 2013 @09:11AM (#6032369)
I'd never heard of Big O until this thread, but from what I can tell it'll only be when a solution is in the O(logn) that "running time will get less significant as n gets larger". This is simply the way you describe logarithmic growth, so maybe that's where you got confused. Also, wouldn't it be fair to say that a logarithm (nlogn) is a lower order term than mn? In which case your definition stands.

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.

Re:LINQ Ruined My Favorite Interview Question by kyllo on Friday July 12, 2013 @09:56AM (#6032574)
Oh, you're right, m is not a constant but also varies somewhat independently of n, so you can't exclude it from the big O notation. And whether mn or nlogn is the lower order of the two terms depends highly on the value of m, which is the number of unique words in the text. A really long text that's just the same word over and over will have a big n but a small m.
Re:LINQ Ruined My Favorite Interview Question by matchu on Friday July 12, 2013 @04:07PM (#6034880)
Worst-case big-O runtime is therefore O(n^2), and best case is O(n log(n)) :)
Re:LINQ Ruined My Favorite Interview Question by spenuke on Thursday July 11, 2013 @02:39PM (#6028179)
Hey, thanks much! I'm going to have to spend some time with these logarithmic evaluations to really get what you're saying, but I dig the basic concept. Very helpful.
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.

Re:LINQ Ruined My Favorite Interview Question by shill on Thursday July 11, 2013 @02:19PM (#6027967)
> I'd appreciate any advice on my solution.

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.

Re:LINQ Ruined My Favorite Interview Question by spenuke on Thursday July 11, 2013 @02:37PM (#6028154)
Ha, nice! Funny you should mention that. I did exactly that when tooling around in the repl and forgot the reverse kw, saw something fishy, and fixed it. Promptly forgot it again when I typed it in this comment. :)
Re:LINQ Ruined My Favorite Interview Question by jessedhillon on Thursday July 11, 2013 @01:22PM (#6027482)
This is a great approach. Even better because you carefully examined the requirements and found an interpretation which allowed you to make an optimization (words only, not counts, therefore sets are useful)
Re:LINQ Ruined My Favorite Interview Question by jules on Thursday July 11, 2013 @09:07PM (#6030276)
This isn't an optimization. He turned a O(n) algorithm into a O(n^2) one.
Re:LINQ Ruined My Favorite Interview Question by recuter on Thursday July 11, 2013 @11:56AM (#6026850)
In case anybody was wondering for a second when JS got so awesome -- it didn't, this is a snippet of Python. D'oh. Sigh.
Re:LINQ Ruined My Favorite Interview Question by 1wheel on Thursday July 11, 2013 @06:08PM (#6029582)
JS isn't that bad if w/ underscore or d3:

    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);
Re:LINQ Ruined My Favorite Interview Question by archangel_one on Thursday July 11, 2013 @10:56AM (#6026387)
collections isn't an external library. It's part of the Python standard library.
Re:LINQ Ruined My Favorite Interview Question by cavilling_elite on Thursday July 11, 2013 @11:13AM (#6026510)
Agreed, if I was looking for a candidate that will always "reinvent the wheel" then I would want them to implement from scratch. I find it perfectly valid for the interviewee to say "Hey! I wrote a module for <language> for this exact purpose! Want to check out my github page?".
Re:LINQ Ruined My Favorite Interview Question by tracker1 on Thursday July 11, 2013 @06:43PM (#6029770)
My first thought after LINQ was a JS or CoffeeScript Map/Reduce/Sort/Splice.
Re:LINQ Ruined My Favorite Interview Question by Myrth on Thursday July 11, 2013 @05:53PM (#6029504)
Pfft <?php function top10($s) { $a = array_count_values(preg_split('/\b\s+/', $s)); arsort($a); return array_slice($a, 0, 10); }
Re:LINQ Ruined My Favorite Interview Question by tracker1 on Thursday July 11, 2013 @06:54PM (#6029824)
You managed to create an example of why I don't care for PHP...

    array_count_values(...)
    arsort(...)
    array_slice(...)
Thinking.. two of these things belong together, two of these things are kind of the same.. but one of these things is doing his own thing...

Seriously built in method naming and argument ordering don't follow any consistent convention in PHP, that's always been the most irksome thing to me...

Re:LINQ Ruined My Favorite Interview Question by Myrth on Thursday July 11, 2013 @08:10PM (#6030108)
Welp oops: <?php function top10($s) { $a = array_count_values(preg_split('/\b\s+/', $s)); rsort($a); return array_slice(array_keys($a), 0, 10); }
Re:LINQ Ruined My Favorite Interview Question by mzs on Thursday July 11, 2013 @03:04PM (#6028384)
I find it silly everyone arguing below but when:

s1 = 'a a a a a a a a a a a a a a a a A A A A A A A A A A A A A a. a. a. a. a. a. a. a. a.'

those two lines give:

[('a', 16), ('A', 13), ('a.', 9), ('', 1)

(HN might collapse the double space in s1)

Re:LINQ Ruined My Favorite Interview Question by jonny_eh on Thursday July 11, 2013 @05:43PM (#6029438)
Indent with four spaces for any bits of text you want quoted and monospaced on HN.

    Like      this      here
Re:LINQ Ruined My Favorite Interview Question by carlob on Thursday July 11, 2013 @04:24PM (#6028961)
In a similar spirit, but without libraries and with a programming language designed 25 years ago.

    Commonest[StringSplit[string], 10]
Re:LINQ Ruined My Favorite Interview Question by mzs on Thursday July 11, 2013 @05:35PM (#6029384)
To be fair, Commonest appeared in Mathematica 6.0 about six years ago.
Re:LINQ Ruined My Favorite Interview Question by sterling312 on Friday July 12, 2013 @01:22AM (#6031064)
meh, just use sum instead of counter

sorted([(i,sum([i==j for j in s.split()])) for i in list(set(s.split()))],key=lambda x:x[1],reverse=True)[:10]