18 ms·

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) (frequen

• moomin 13y ago
  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.
• shill 13y ago
  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)
  • untog 13y ago
    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?!?
    • jkrems 13y ago
      It looks like collections is part of the standard library: http://docs.python.org/2/library/collections.html 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.
      • untog 13y ago
        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.
        • cben 13y ago
          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.
          • klipt 13y ago
            > 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.
        • rhizome 13y ago
          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."
          • 13y ago
    • archangel_one 13y ago
      collections isn't an external library. It's part of the Python standard library.
      • deleted 13y ago
        [deleted]
      • cavilling_elite 13y ago
        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?".
    • shill 13y ago
      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]
      • recuter 13y ago
        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.
        • 1wheel 13y ago
          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);
      • deleted 13y ago
        [deleted]
      • spenuke 13y ago
        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.
        • jessedhillon 13y ago
          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)
          • 13y ago
    • tracker1 13y ago
      My first thought after LINQ was a JS or CoffeeScript Map/Reduce/Sort/Splice.
  • mzs 13y ago
    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)
    • jonny_eh 13y ago
      Indent with four spaces for any bits of text you want quoted and monospaced on HN. Like this here
  • carlob 13y ago
    In a similar spirit, but without libraries and with a programming language designed 25 years ago. Commonest[StringSplit[string], 10]
    • mzs 13y ago
      To be fair, Commonest appeared in Mathematica 6.0 about six years ago.
  • Myrth 13y ago
    Pfft <?php function top10($s) { $a = array_count_values(preg_split('/\b\s+/', $s)); arsort($a); return array_slice($a, 0, 10); }
    • tracker1 13y ago
      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...
    • Myrth 13y ago
      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); }
  • sterling312 13y ago
    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]
• mrottenkolber 13y ago
  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?
  • GregWright 13y ago
    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)))
  • deleted 13y ago
    [deleted]
  • prospero 13y ago
    http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html#equals(java.lang.Object) http://docs.oracle.com/javase/6/docs/api/java/lang/Object.ht...
  • nickik 13y ago
    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.9999 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.9...
• colanderman 13y ago
  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.
  • amouat 13y ago
    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-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five http://stackoverflow.com/questions/3482389/how-many-primitiv...).
  • kyllo 13y ago
    So, the line of code in the OP that's missing from the LINQ version of the solution is: Imports System.Linq
  • calibraxis 13y ago
    `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.
  • gngeal 13y ago
    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#.
• aphyr 13y ago
  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))
  • wging 13y ago
    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.
    • JeanPierre 13y ago
      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).
  • moomin 13y ago
    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.)
    • aphyr 13y ago
      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/ 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.
• haakon 13y ago
  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)
  • rybosome 13y ago
    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 } }
    • haakon 13y ago
      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 https://coderwall.com/p/ha-c2w
• louthy 13y ago
  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);
  • cmircea 13y ago
    Though that will result in a lot more calls to Count(). A let would fix that.
    • voltagex_ 13y ago
      I really really really should learn more Linq. Where would I use let, and why?
      • cmircea 13y ago
        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).
    • louthy 13y ago
      Indeed! It wouldn't be quite as concise though, which was kind of my point :)
• mzs 13y ago
  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.
  • stass 13y ago
    This is too complicated... echo $sentence | rs -T | sort | uniq -c | sort -rn|head -10
    • mzs 13y ago
      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.
      • stass 13y ago
        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.
  • kragen 13y ago
    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.
• deleted 13y ago
  [deleted]
• ajanuary 13y ago
  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.
• EpicEng 13y ago
  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.