News for hackers. Stuff that matters.
Re:LINQ Ruined My Favorite Interview Question by llambda on Thursday July 11, 2013 @10:35AM (#6026248)
I hate to be the bearer of bad news, but I think there may be even simpler solutions to this problem:

    (take 10 (reverse (sort-by (comp first rest) (frequencies (string/split ... #"\+s"))))

The above is a Clojure one-liner example that I believe satisfies the original problem. So while LINQ may have simplified from the C-language family solutions he had seen, it's clearly possible to take it one step further with the expressivity of modern languages like Clojure...

Edit: remember to sort! (Forgot my coffee this morning...)

Edit again: and aphyr's solution is even more concise and idiomatic, where `s` is the first paragraph of the blog post:

    => (->> (string/split s #"\s+") frequencies (sort-by val) reverse (take 10))
    (["I" 7] ["to" 6] ["the" 5] ["a" 5] ["of" 4] ["candidates" 3] ["is" 3] ["question" 3] ["in" 3] ["their" 2])
Re:LINQ Ruined My Favorite Interview Question by louthy on Thursday July 11, 2013 @01:57PM (#6027768)
The OP blog-post doesn't really represent it succinctly in C#. This is the most succinct way I could think of:

  var top = (from w in text.Split(' ') 
             group w by w into g 
             orderby g.Count() descending 
             select g.Key).Take(10);
Re:LINQ Ruined My Favorite Interview Question by cmircea on Thursday July 11, 2013 @07:05PM (#6029873)
Though that will result in a lot more calls to Count(). A let would fix that.
Re:LINQ Ruined My Favorite Interview Question by voltagex_ on Friday July 12, 2013 @01:24AM (#6031074)
I really really really should learn more Linq. Where would I use let, and why?
Re:LINQ Ruined My Favorite Interview Question by cmircea on Friday July 12, 2013 @02:48AM (#6031270)

    from word in text.Split(' ') 
    group word by word into g
    let count = g.Count()
    orderby count descending 
    select g.Key
Under the covers when it is compiled it's turned into a select. That way it it only does N counts, not potentially N log N (for each comparison in the orderby), where N is the number of items you enumerate (so if you .Take() just 10 it doesn't really matter).
Re:LINQ Ruined My Favorite Interview Question by louthy on Friday July 12, 2013 @07:43AM (#6032066)
Indeed! It wouldn't be quite as concise though, which was kind of my point :)
Re:LINQ Ruined My Favorite Interview Question by aphyr on Thursday July 11, 2013 @11:16AM (#6026534)
While we're golfing, (comp first rest) is equivalent to the stdlib function called second, or, perhaps more idiomatic for map entries, val. We can also flatten deeply nested chains of computation using the -> and ->> macros, like so:

  (->> (string/split ... #"\s+")
       frequencies
       (sort-by val)
       reverse
       (take 10))
Re:LINQ Ruined My Favorite Interview Question by moomin on Thursday July 11, 2013 @03:48PM (#6028685)
Think you also need a (map key) there to be equivalent to the C# code. At which point it's starting to look very similar to well written C# code solving the same problem.

Much as I love Clojure, it's worth pointing out that Clojure's lazy sequences (include intermediate sequences) get cached, while LINQ evaluates more like Clojure's reducers. (You can even get it to do so in parallel.)

Re:LINQ Ruined My Favorite Interview Question by aphyr on Thursday July 11, 2013 @04:14PM (#6028880)
You're right; it does need a (map key) line to be equivalent. I was thinking of http://www.leancrew.com/all-this/2011/12/more-shell-less-egg..., which wants the counts too. :)

On a side note, I'd like to point out a key difference between this Clojure example and corresponding variants in C#, Python, &c: the Clojure variant has no variables. This isn't just a matter of concision: coming up with descriptive names is hard, and usually means duplicated information, either in the name or the type declaration. Often, those names are re-used over and over again with subtly different meanings, for each stage in a pipeline--forcing the reader to reason carefully about the declaring scope at each use.

Consider, for example:

  Swimmer swimmer = new Swimmer("foo");
  swimmer.setStyle("butterfly");
  swimmer.swim();
  return swimmer;

  (doto (Swimmer. foo)
        (.setStyle "butterfly")
        .swim)
Same operation--but with (doto), four uses of a variable and one type declaration have been cleared away. Consider the original post:

  var words = s.Split(' ');
  var wordCounts = words.GroupBy(x => x).Select(x => new { Name = x.Key, Count = x.Count() }).OrderByDescending(x => x.Count);  
  var countedWords = wordCounts.Select(x => x.Name).Take(10).ToList();
  return ExtractTopTen(countedWords);
Six uses of three formal variables, including the bewilderingly confusable countedWords and wordCounts, plus nine uses of the delightfully generic "x". Even in the more compact C# example from this thread, consider:

  var top = (from w in text.Split(' ') 
             group w by w into g 
             orderby g.Count() descending 
             select g.Key).Take(10);
This variant refers to the temporary variables w (for "words") and g (for "groups"?) six times. Both authors felt the need to reduce the repetition of variables, but the best they could do was to choose single-character names.

This is the real power of ->, .., ->>, doto, and friends: eliminating names for things. By thinking about the composition of transformations, instead of the intermediate results, you can make an algorithm easier to understand and change.

Re:LINQ Ruined My Favorite Interview Question by mistermann on Friday July 12, 2013 @02:27AM (#6031236)
> Six uses of three formal variables, including the bewilderingly confusable countedWords and wordCounts, plus nine uses of the delightfully generic "x".

I totally agree with you on this.

>Even in the more compact C# example from this thread, consider: var top = (from w in text.Split(' ') group w by w into g orderby g.Count() descending select g.Key).Take(10);

> This variant refers to the temporary variables w (for "words") and g (for "groups"?) six times. Both authors felt the need to reduce the repetition of variables, but the best they could do was to choose single-character names.

> This is the real power of ->, .., ->>, doto, and friends: eliminating names for things. By thinking about the composition of transformations, instead of the intermediate results, you can make an algorithm easier to understand and change.

You lost me somewhere along the way....are you saying the "from w in text"... snippet is bad, and something more along the lines of "This is the real power of ->, .., ->>" is more appropriate?

I ask because that code seems extremely readable to me. Personally, I don't give a shit if it's 30% more verbose or runs 50% slower, for 99% of code (written in the world), optimum performance doesn't matter. Maintainability does matter though. All of this software being written today has to be either maintained by someone, or replaced by something else. And the top ~2% of programmers like you sure as hell aren't going to be taking maintenance jobs any time soon.

I'm curious what the thoughts of a technically smart person such as yourself are on the subject of what companies will be left with 5 to 10 years down the road when consultants have come through and implemented using the currently most optimum platform/language/algorithms?

And I honestly don't mean for this question to be disrespectful. I'm just coming from a situation where I'm a former developer but on a project where I'm not coding, and I ask for features and the developers say they can't do it, or it will be a performance problem. And I know these guys are far more like you than me intelligence/education wise, but the things I ask for I've done tons of times in the past with 10 to 1000 times the data size, without a problem, on far older hardware.

I'm just curious what kind of a support problem you ultra smart people are leaving behind, or if you ever think about the idea that almost no on else is as smart as you?

Re:LINQ Ruined My Favorite Interview Question by aphyr on Friday July 12, 2013 @11:14AM (#6033007)
Over the last ten years, I've read a lot of code. I maintain my own code, and I maintain others' code. Because I am not that smart, I try to simplify everything--to make large problems tractable for my little brain to reason about. In this process, I've come to the conclusion that good, maintainable code is:

1. As simple as humanly possible, so that the algorithm is easy to understand and change. Each component is isolated and can be understood and modified in isolation. Boundaries between component and environment are clearly thought-out.

2. As simply expressed as possible: broken up into distinct, well-organized functions, with descriptive, regular names for functions and variables, in context.

3. Well-documented; each function and each namespace come with contextual docs explaining their motivation, arguments, consequences, invariants, etc., with examples.

4. As short as possible, because humans have trouble holding large amounts of context in their head. Minimize the amount of scrolling or jumping between files necessary to understand the algorithm.

5. Well-tested, so that changes can be made freely. The test suite needs to be fast, so one can get feedback within seconds of making a change to the file; ideally a few milliseconds. A balance of typechecking, logical tests with mocks, integration tests, and full stress tests provides a continuum of safety.

I don't see these goals as particularly constrained to any language, but I will say that I feel best able to achieve them in a Lisp. Dunno whether that helps you project your problems at work onto me personally, though. ;-)

Re:LINQ Ruined My Favorite Interview Question by Pxtl on Thursday July 11, 2013 @10:44PM (#6030616)
Yeah, I tend to prefer the lambda notation over the sqlish notation, but either way the lambda form of your solution would be similarly terse. The select call that constructed an anonymous-typed object was unnecessary, as were all the temporary variables... C# coders should never be afraid to embrace the Rubyish leading dot approach.

  return s.Split(' ')
    .GroupBy(word => word)
    .OrderByDescending(wordGroup => wordGroup.Count())
    .Select(wordGroup => wordGroup.Key)
    .Take(10).ToList();
Re:LINQ Ruined My Favorite Interview Question by tel on Thursday July 11, 2013 @10:21PM (#6030530)
Pointless style gets a bad rap, but the idea that you're thinking of just the transformations instead of the data is a powerful mindset to have.
Re:LINQ Ruined My Favorite Interview Question by Someone on Friday July 12, 2013 @02:55AM (#6031287)
In C# that could be:

  return new Swimmer("foo")
  { Style = "butterfly"}
  .swim();
It is unidiomatic to have Swimmer.swim return 'this', though.

  var result = new Swimmer("foo")
  { Style = "butterfly"};
  result.swim();
  return result;
Re:LINQ Ruined My Favorite Interview Question by moomin on Friday July 12, 2013 @03:13PM (#6034518)
The thing being that C# has a feature for a whole bunch of idioms, but none of them are extensible and writing new ones requires a new version of the language. The Clojure reducers, doto, ->>, go macro could all have been implemented in 1.0. (And two of them were.)

I speak as someone who codes in C# for work and Clojure as a hobby. There's lots of things that just aren't quite possible in C#, and _everything_ is possible in Clojure.

Pointfree is beautiful to read and grok. It's a little trickier to debug, since pretty much every debugger on earth needs points to inspect values.

Re:LINQ Ruined My Favorite Interview Question by wging on Thursday July 11, 2013 @11:53AM (#6026827)
If the aim is golf, it's probably best to keep #" ". If the aim is accuracy, we might get better results by using #"[^\w]+". Though that does nasty things to words like "it's".

Edit: Actually, we can also get rid of the 'reverse' by replacing (sort-by val) with (sort-by (comp - val)). Not going to be shorter in terms of character count, though we win on line count.

Re:LINQ Ruined My Favorite Interview Question by JeanPierre on Thursday July 11, 2013 @02:20PM (#6027992)
sort-by takes an optional comparator, so doing (comp - val) is a bit unneeded. Just add in > as an argument to sort-by:

  (->> (string/split s #"\s+")
       frequencies
       (sort-by val >)
       (take 10))
Just mentioning it here because I find it vastly more readable than (comp - val).
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]

Re:LINQ Ruined My Favorite Interview Question by colanderman on Thursday July 11, 2013 @11:13AM (#6026513)
expressivity of modern languages like Clojure

Uh, no. Your solution just uses a bunch of standard library functions (at least, I hope they're not syntactic forms… and why a function as specific as "frequencies" not in some namespace boggles my mind). I could write that in C with an appropriate standard library.

Ironically, expressing this in something like SQL actually speaks to the expressivity of the language because the solution was produced entirely with syntactic forms.

Re:LINQ Ruined My Favorite Interview Question by amouat on Thursday July 11, 2013 @11:31AM (#6026664)
That may be true, but it's still a pretty idiomatic Clojure solution. Ask 10 Clojure programmers to solve this problem and most of them will come up with something similar. Ask 10 C programmers and they will likely come back with a program much more similar to the one in the post.

The fact that such functions are at a Clojure programmer's fingertips is exceptionally important. If you strip out the core functions (and macros) from any lisp or Clojure you are left with almost nothing( see http://stackoverflow.com/questions/3482389/how-many-primitiv...).

Re:LINQ Ruined My Favorite Interview Question by calibraxis on Thursday July 11, 2013 @02:42PM (#6028200)
`frequencies` is surprisingly useful, enough to justify its inclusion into core. I once pondered why.

Consider that in Clojure, a common act transforming one datastructure into another. Typically only a few kinds: maps, sets, and some kind of sequence.

What is a highly common generic transformation of a sequence to a map? `frequencies`. Particularly since you'd only be doing this with pretty finite sequences, given the finite nature of the built-in maps. Finite here means countable. What generic, domain-independent thing would you be counting? Often, the items themselves.

Re:LINQ Ruined My Favorite Interview Question by gngeal on Thursday July 11, 2013 @05:11PM (#6029253)
Ironically, expressing this in something like SQL actually speaks to the expressivity of the language because the solution was produced entirely with syntactic forms.

What? Pure untyped lambda calculus does things "only with syntactic forms". Don't tell me that your solution wouldn't use some basic operators other than rudimentary syntax. Keep in mind that in Lisp-family languages, many things that are a part of syntax in other languages are actually simple functions - arithmetic operations being a case in point - so you really can't avoid using library functions.

I believe that the major point of Clojure etc. is that they provide concise basic operations that you can use everywhere to compose complex operations better than you can do with, say, C#.

Re:LINQ Ruined My Favorite Interview Question by kyllo on Thursday July 11, 2013 @01:45PM (#6027680)
So, the line of code in the OP that's missing from the LINQ version of the solution is:

    Imports System.Linq
Re:LINQ Ruined My Favorite Interview Question by ajanuary on Thursday July 11, 2013 @04:01PM (#6028770)

  s.Split(' ').GroupBy(x => x).OrderByDescending(x => x.Count()).Select(x => x.Key).Take(10).ToList();
I'd say 13 characters isn't really a huge differentiator. They're both using exactly the same algorithm, almost exactly the same built-in library functions, and have exactly the same flexibility for programmers to add their own (C# is using extension methods which lets you add methods that look like they belong to the class, but are actually static methods defined elsewhere).

There's a lot of benefits to Clojure over C#, but the ability to chain functional list operators really isn't one of them.

Re:LINQ Ruined My Favorite Interview Question by mzs on Thursday July 11, 2013 @02:43PM (#6028209)
For a sys-admin job:

tr 'a-z' 'A-Z' | sed 's/[^A-Z][^A-Z]*/\ /g' | grep -v '^$' | sort | uniq -c | sort -nrk1 | head -10

edit: I don't know enough about HN,there should be a newline after the backslash in the sed command.

Re:LINQ Ruined My Favorite Interview Question by kragen on Friday July 12, 2013 @01:35AM (#6031101)
You can use tr instead of sed and grep, too. Also -k1 and -n 10 are default for sort and head:

    $ < bible-pg10.txt tr -cs a-zA-Z '\n' | sort | uniq -c | sort -nr | head
      62265 the
      38915 and
      34588 of
      13474 to
      12846 And
      12589 that
      12387 in
       9762 shall
       9668 he
       8942 unto
I have a `bins` script that is just `sort | uniq -c | sort -nr`, so that reduces to `tr -cs a-zA-Z '\n' | bins | head`.

Unix for Poets, man. It's the shit.

Re:LINQ Ruined My Favorite Interview Question by mzs on Friday July 12, 2013 @09:17AM (#6032391)
I ALWAYS forget about squeeze, thanks!
Re:LINQ Ruined My Favorite Interview Question by stass on Thursday July 11, 2013 @05:18PM (#6029295)
This is too complicated...

echo $sentence | rs -T | sort | uniq -c | sort -rn|head -10

Re:LINQ Ruined My Favorite Interview Question by mzs on Thursday July 11, 2013 @05:55PM (#6029523)
Ooh that's a clever use of reshape, but wrong sadly. Yet you're right I could make it simpler, it was just what came first to mind, I did not even check it. Imagine typical sentences:

  $ echo Foo foo foo. | rs -T
  Foo
  foo
  foo.

  $ echo Foo foo foo. | tr 'a-z' 'A-Z' | sed 's/[^A-Z]/\
  /g' | grep -v '^$'
  FOO
  FOO
  FOO
Also the link mentioned using wiki articles for testing, so they would have paragraphs and that's where reshape shines for things like emails, but fails here:

  $ cat foo
  Foo
  
  foo

  foo.
  $ <foo rs -T
  Foo   foo   foo.  
  $ <foo tr 'a-z' 'A-Z' | sed 's/[^A-Z]/\
  /g' | grep -v '^$'
  FOO
  FOO
  FOO
That that's though makes me think, should I treat contractions special? What about plurals? It's starting to get silly now.
Re:LINQ Ruined My Favorite Interview Question by stass on Thursday July 11, 2013 @08:14PM (#6030120)
I think it goes beyond the original question now. :) If one wants to do proper thing, then definitely contractions, word variations, etc should be considered. For this, I guess something like OpenNLP can be used.

What's interesting though is how UNIX shell, being essentially a symbolic FP language, allows one to solve the problem in a clear and concise way. And if one desires, the program can be easily modified to read sentences, say, from network from ssh tunneled via HTTPS. That kind of flexibility can rarely be achieved in languages like C# with tight coupling between the units of abstraction.

Re:LINQ Ruined My Favorite Interview Question by EpicEng on Thursday July 11, 2013 @04:17PM (#6028900)
I like how you snuck in "modern languages (like Closure)", as if C# is not a "modern language". Both languages have their place, but let's not pretend that Closure is somehow superior for all applications.
Re:LINQ Ruined My Favorite Interview Question by moomin on Thursday July 11, 2013 @10:46AM (#6026322)
You'll need to sort the result of frequencies: it's an unordered map.

In practice, if you use ->> and write neater LINQ, the code is very close. Although LINQ only has group and sum/reduce, no dedicated frequencies function.

Re:LINQ Ruined My Favorite Interview Question by mrottenkolber on Thursday July 11, 2013 @10:51AM (#6026360)
how does FREQUENCIES know how to compare strings?

In Common Lisp you'd usually supply a TEST keyword parameter (#'STRING= or #'EQUAL in this case). Does Clojure use Java's type system to infer?

Re:LINQ Ruined My Favorite Interview Question by GregWright on Thursday July 11, 2013 @11:19AM (#6026556)
No expert, but from the source it looks like it just uses whatever a 'map' uses to match keys:

  (defn frequencies
    "Returns a map from distinct items in coll to the number of times
    they appear."
    {:added "1.2"
     :static true}
    [coll]
    (persistent!
     (reduce (fn [counts x]
               (assoc! counts x (inc (get counts x 0))))
             (transient {}) coll)))
Re:LINQ Ruined My Favorite Interview Question by nickik on Thursday July 11, 2013 @03:28PM (#6028553)
Clojure uses a unified compare test, sometimes called equiv. I think its passed on this paper, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.9...
Re:LINQ Ruined My Favorite Interview Question by prospero on Thursday July 11, 2013 @12:02PM (#6026895)
Re:LINQ Ruined My Favorite Interview Question by haakon on Thursday July 11, 2013 @01:48PM (#6027702)
Since we're already on the JVM, here's my solution for Scala:

def top10(s: String) = s.split(' ').groupBy(identity).mapValues(_.size).toList.sortBy(-_._2).take(10).map(_._1)

Re:LINQ Ruined My Favorite Interview Question by rybosome on Friday July 12, 2013 @01:56AM (#6031164)
That's almost identical to what I came up with, but yours is better...I didn't know about the mapValues function.

def mostCommon(str: String, num: Int) = { str.split(" ").groupBy { s => s} .map { case (k,v) => k -> v.length }.toList .sortBy { _._2 }.reverse.take(num).map { _._1 } }

Re:LINQ Ruined My Favorite Interview Question by haakon on Friday July 12, 2013 @03:33AM (#6031367)
That works as well. On the other hand, I'm not a fan of these huge one-liners (including the one I posted). I split mine up a bit and posted it here: https://coderwall.com/p/ha-c2w