On Friday, Embedly offered Hacker News a coding challenge. Apply.embed.ly asked developers to solve 3 different problems and submit their solutions. We didn’t force people to apply for 1 of the 3 positions that we have open, just nerd out on some problems. We are going to talk about the results and the answers.
Here is a quick funnel of users to apply.embed.ly
1. Sum of Digits
Based on a question from Project Euler given the formula:
R(n) is the the sum of the digits for n!.
For example, 10! = 3628800
R(10) = 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
We loved this question for the golf aspect. In python R(n) it can be written:
R = lambda x: sum(map(int, str(math.factorial(x))))
To actually solve it, almost everyone used a a brute force algorithm. Like so:
min([i for i in range(1000) if R(i) == 8001])
We got a total of 1008 distinct answers for this question. 758 were seen less than 2 times (some people tried to brute force the value)
The top three answers:
- 787 (992)
- 0 (384)
- 802 (105)
2. Standard Deviation of P tags
This one was a mess, when the problem was first put up we had a very large and invalid, random-generated HTML file. If you used the Chrome console, lxml, nokogiri or ran the html through Tidy you got the ‘correct’ answer. If you used a sax parser, the answers were much different.
After a few confused tweets, we allowed any answer between 0.5 and 2.0. We then simplified the html greatly. This allowed people to manually count the depths of each p tag or use the white space to determine the depth. This may have defeated the purpose, but ok internet, you win.
We got a total of 242 distinct answers for this question. 117 were seen less than 2 times.
The top 3 answers:
- 1.4 (335)
- 0.767 (164)
- 1.253 (101)
3. Zipf’s Law.
We simplified Zipf’s law to:
Z(x) = [x, x/2, x/3, x/4...]
This described the frequency distribution for words in a random body of text. Given that x = 2520 and a text of 900 unique words, how many words make up half the text?
This one got a little confusing too.
We can get the word count by using:
words = [2520/float(i) for i in range(1, 901)]
word_count = sum(words)
We can then iterate over the words till they are greater than 50% of the total word count.
min([i for i in range(30) if sum(words[:i]) > sum(words)/2.0])
It got a bit hairy when it came to rounding. We were in the wrong here by using float instead of integer because it doesn’t make sense to have fractional word counts. We should have accepted 21 instead of 22.
The top 3 answers:
- 22 (450)
- 21 (204)
- 20 (120)
We intentionally made it easy to hack apply.embed.ly. The url paths were /1 /2 /3 and every time you got a question right, we just added a cookie ‘au_embedly_1=true’ for the problem you solved. Only Will Pearson used this to his advantage and skipped a problem.
Some notable examples of different ways people solved this.
- A couple people solved it in the Chrome console, no text editor needed.
- 6 minutes. The total time it took one college sophomore to solve it.
- Ruby one liners for all: https://gist.github.com/1792968/cbb3f5c22ff2e7d174734c780df87e8b9e85153e
- All in Mathematica: https://gist.github.com/1797321
- You can solve the first problem in J in 27 chars: “(+/ “1 f”0 !i.1000x) i.8001”
- A number of people used excel to solve a majority of the problems. There seems to be a lot of finance nerds lurking on HN.
If you are interested in seeing the solutions everyone posted here you go. I embedded a gist of gists because I cannot for the life of me figure out how to get Posterous not to embed them.