12 ms·
Can you solve it? The Greplin programming challenge
- tedc 16y ago1-2 hours! Great...now my productivity will be shot for the day.
- jah 16y agoUh ... call a phone number? No thanks. Edit: Excellent! Back to hacking.
- brandon 16y agoYep, decided not to continue when I got to that point. It looks like the number is a landline in the Bay Area. I wonder if some poor soul at Greplin will be taking calls all day.
- deleted 16y ago[deleted]
- deleted 16y ago[deleted]
- whimsy 16y agoPerhaps this is one of those "secret recruitment processes."
- rwalker 16y agoPhone call no longer required. For what it's worth - it's just a Twilio app - we thought it would add to the fun.
- seanstickle 16y agoI'm curious to know why calling a phone number was a deal-breaker. It seemed eminently likely (to me) that it would be an automated system, but, even if it wasn't, talking to someone isn't that big a deal to me. I certainly wasn't concerned about long-distance charges, but I suppose that might be a problem for some. I thought it was a nice little twist in the problem set.
- petercooper 16y agobut, even if it wasn't, talking to someone isn't that big a deal to me. A lot of people struggle with the phone. I certainly have, though I'm getting better at it. I've noticed many people become spookily compliant on the phone, endlessly listening to and being polite to even the most annoying callers instead of just hanging up.
- kbob 16y agoI'm hearing-impaired.
- Deestan 16y agoI live in Norway, so the phone bill is a significant factor. Also, the wife and kids are sleeping in the next room, which would require me to step outside on the porch in the middle of the night with my cellphone. Yet also, I'm so tired I couldn't have englished very well in my phone anyway. :-)
- jlees 16y agoMaybe you don't want them knowing your phone number to call you back with job calls or whatever. (Of course, there are ways around that too.)
- deleted 16y ago[deleted]
- eqdw 16y agoUm, no answer on the phone. I let it ring for over a minute.
- Twisol 16y agoDid you forget the 1 before the area code? I did.
- siglesias 16y agoAnybody else browsing by mobile try to do Level 1 by inspection?
- eqdw 16y agoAfter doing the obvious brute force algorithm, the correct answer is not a real word. So you'll have a tough time getting it on your own
- siglesias 16y agoWell, I was suggesting looking for symmetrical triads (or repeating characters) and then working outward. I'd say the eye is pretty good at picking out symmetries.
- 9ec4c12949a4f3 16y agoWhy aren't you guys just searching for the palindromes? There's more efficient ways than doing every character, or groups of them... What constitutes a palindrome? What does that mean to simplify what we're doing? http://www.w3schools.com/jsref/jsref_obj_string.asp http://www.w3schools.com/jsref/jsref_obj_string.asp
- l0nwlf 16y agoBrute works here because of bad test case. Author could have generated a smart test case and then optimal algorithm could be using suffix array which takes O(n), brute would take O(n!). However a bit smart brute gave the answer in approx 3-4 minutes ( computation + coding time). And yes, Python FTW.
- orangecat 16y agoIsn't brute force just O(n^3)? Loop over each character to start potential palindrome, loop from start character to end, reverse substring and compare. But yeah, the test input should be longer and/or smarter. Ditto on the third problem.
- orangecat 16y agoDone, as usual with these things using Python feels like cheating.
- jasondavies 16y agoThe last problem was really simple in Python. I was all psyched up for a big bad end-level boss! Still, it was fun to play.
- ajstiles 16y ago30 minutes. Would have been less but the IVR response was a little confusing. Took about 40 lines Ruby code to solve.
- Muzza 16y agoThere are only 31 known Fibonacci primes (plus a handful probable primes)...
- droz 16y agotoo easy. about 30mins and 100 lines of C#.
- triangleman83 16y agoWow the G. Address was horribly mutilated. Four score and seven years ago our faathers brought forth on this containent a new nation conceived inz Liberty and dedicated to the proposition that all men are created equal Now we are engaged in a greaht civil war testing whether that naption or any nartion so conceived and so dedicated can long endure We are qmet on a great battlefiemld of tzhat war
- rwalker 16y agoThis was intentional - we had to tie break the longest palindrome and we didn't want a quick diff to be able to see what we changed.
- Cushman 16y agoNever mind that finding the actual text, removing the spaces and caps, and running diff would probably take longer than coding and executing a brute force algorithm :P
- Natsu 16y agoWhy not ask for the rightmost palindrome, then? Just to make it a tiny bit more complex (not that it's very hard to iterate backwards)?
- 1amzave 16y agoSo what languages did everyone use? I decided to try a different one on each level, so I used Python, bash (letting GNU coreutils 'factor' do the hard work), and Haskell, respectively.
- nene 16y agoRuby was my main choice + some command line tools to do bits of extra work, like 'sort' to find the largest palindrome and 'wc' to count the results in last exercise, and even Python command line to just manually sum the primes in second exercise.
- djacobs 16y agoRuby has Array#sort, no command line required.
- nomurrcy 16y agoClojure here.
- djacobs 16y agoMind posting your solution as a Gist? I want to see how to do level 1 without explicit loops or variables.
- nomurrcy 16y agoSure, sorry about the delay. http://gist.github.com/621130 http://gist.github.com/621130 I can't take credit for the solution I posted though. I originally wrote a naive O(N^2) complexity solution (which was much shorter and was fine for the length of the input) I had this palindrome code in my 'toolbox' of code I've come across though, I'm afraid I don't know the orig author. I just tweaked it as this is more in line with the type of example you're looking for.
- djacobs 16y ago
- zmitri 16y agoThe last question isn't that difficult if you brute force it and have loads of memory. I tried to do it in python using itertools on my work thinclient and got a memoryerror. If you however break up your combinations.. you're good to go! Fun, made my day. Good idea greplin dudes!
- tbrownaw 16y agoNot sure what you'd need the loads of memory for? int[] nums = {...} for i = 1 to (2^length(nums) - 1) int[] possibility = { nums[x] where (2^x bitand i) > 0 } test possibility and perhaps increment hit counter
- zmitri 16y agoI was at work on a crappy thin client and first tried to run list(itertools.combinations(sequence)), which was crapping out. After I switched it to itertools.combinations(sequence,i) and put that right into my for loop it was fine.
- bd 16y ago"Even if you're not looking for a job, we'd love to hear what you thought about the challenge." I would be curious how many people did you lose because of phonecall requirement (before you changed it). Also CSV for just a list of 22 numbers wasn't really necessary. If you do web puzzle, the best is to keep everything self-contained, no downloads, no using external channels, just copy and paste. FYI another Python cheater here (+Wolfram Alpha & Wikipedia, I'm lazy :).
- dschoon 16y agoI don't think trivializing the combinations with Python's builtins, looking up the fib primes with OEIS, or computing factors with Alpha is cheating. I hope, in fact, it's the whole point of the exercise: choose the right tools for the job. If you're writing code to test primeness or generate Fibonacci numbers, I sure as hell don't want to hire you.
- zmitri 16y agoCode to generate fibs is literally one line. Remember eigenvalues :)?
- shiven 16y agoSorry, couldn't help myself!! That approach is just so damn elegant. int((1/math.sqrt(5))*(math.pow(((1+math.sqrt(5))/2),fibonacci)-math.pow(((1-math.sqrt(5))/2),fibonacci))) Reference here: http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci-sequence.html http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...
- btilly 16y agoElegant, but inefficient if you want to get exact values for large n. You're much better off using doubling operations. If you forget those, you can remember them from the matrix version. If fib(0) = 0. fib(1) = 1. etc. Then n [0 1] = [fib(n) fib(n+1)] [1 1] [fib(n+1) fib(n+2)] With repeated squarings, you can efficiently generate any Fibonacci number you want.
- nene 16y agoI'm usually pretty bad at these kind of challenges (lately I tried registering at one mind-challenges site, but I couldn't even get past the five entry-level questions, which would have allowed me to even register), but this was surprisingly easy. Simple brute-force methods worked for each of the three tasks. I was totally surprised that the first time I entered the answer for each of the tasks, it was indeed the correct one. But then again... these are all pretty standard computer science problems, nothing that I hadn't in some way done before. On a side-note: Interestingly I used recursion for each of the three problems. Well... actually for the primes-problem I got stack overflow and rewrote it to not use recursion, but still, at least in principle :=)
- danielsoneg 16y agoAgreed - I was laughing as I was writing some of my code because it was so bad. These sort of questions are designed around algorithm design, but a one-off problem with these small of sample sets doesn't need an elegant solution - a hatchet job does just fine. I'm not a CS grad and my math skills are a bit iffy, but I was able to solve all three challenges in a pretty reasonable amount of time.
- Natsu 16y agoDamn, I have to go in to work early today or I could continue this. The first one only took a minute or two of coding to solve in Perl. The search string was several times longer than my code, even with use warnings & use strict in there. I'd write a bit of code to memoize the function before I'd do the Fibonacci numbers, though, and I just don't have time to continue right now, even though it's pretty easy. Are the rest of the tests like that? Do they force you to use more efficient code, rather than simpler brute force tests so that your code has a decent runtime?
- Tichy 16y agobrute force seems to be sufficient
- leif 16y agoyou also probably don't want to memoize, you aren't going to re-use, so why waste the memory?
- Natsu 16y agoI wrote that right before leaving for work, so I hadn't spent any time thinking about the problem. Coming back, I see that I really don't need to be very efficient for any of these problems, which I honestly find a little disappointing.
- cperciva 16y agoDo I get bonus marks for solving this without writing any code?
- rpbertp13 16y agoI didn't know that was within the extent of your powers cperciva
- cosgroveb 16y agoI immediately went to Wikipedia, found out what type of CS problem the first challenge was, then followed the external links at the bottom of the page to find the Perl module I needed and installed it from CPAN. I quit because this seemed like cheating but now I'm thinking... Maybe it was the point? To see if I would try to find something off-the-shelf to solve the problem quickly. Still not sure it was, because if so the challenge certainly doesn't demonstrate that I have any CS chops. :-\ Spoiler alert: I believe this module will do the trick http://search.cpan.org/~gray/Tree-Suffix-0.21/lib/Tree/Suffix.pm http://search.cpan.org/~gray/Tree-Suffix-0.21/lib/Tree/Suffi...
- cperciva 16y agoI didn't solve the problems using existing code either. All three are entirely solvable by pencil and paper (or just inspection in the first case).
- deleted 16y ago[deleted]
- riffraff 16y agodamn it had a typo in the fib generation for the second number and lost a lot of time trying to factor a _massive_ number that was obviously the wrong one :)
- rpbertp13 16y ago35 mins, but in less than 40 lines of ruby
- djacobs 16y agoI used Ruby, too. Nothing else required. I think Clojure might've made things a tad easier (given all its sequence functions), but I'm just learning it, so Ruby all the way. That said, finding the palindromes in Ruby took me about 12 lines of code (less if I didn't structure it using methods).
- joe_the_user 16y agoI've generally done well on job-interview programming challenges and gotten interviews afterwards. But looking on these quiz things, I'm still frustrated by them. You see, all the "ordinary" question involved in job-fitting still have to be asked and answered so sometimes I've done great in ability part only to have really basic "culture" or requirements issue hit later when they could have been caught immediate. And so, even though I've enjoyed and learned something on these quizzes, the employer who begins a relationship with a quiz seems to be saying they can demand some piece of my time without any investment on their part and this isn't setting a tone reciprocity, something I'd look for in a future employer.
- grogers 16y agoThat was fun, good waste of time while my code was compiling. I just used C++ and hacked up a prime seive for #2 and for #3 used a combination generator I had previously used before - http://photon.poly.edu/~hbr/boost/combinations.html http://photon.poly.edu/~hbr/boost/combinations.html
- cperciva 16y agofor #3 used a combination generator Congratulations, you just used an exponential-time algorithm for a polynomial-time problem.
- Deestan 16y agoCongratulations are in order, he sacrificed 400ms CPU time to save at least a few minutes of coding time.
- dsc 16y agoNot always is "exponential" a bad thing. For small sets, the expo algorithm is actually faster than the polynomial one. Although yeah, generally speaking, it's a bad idea.
- ay 16y agoI tried on #3 the most inefficient algorithm I could come up with - blindly going through all possible combinations and checking if their biggest member is equal to the sum of the rest. Time of the execution: 0.6s I am not sure if this step of allowing the "shortcuts" was part of the game or not. All that would had to be done is to give 128 elements of the array to exclude at least the most blatant brute-forcing.
- bradly 16y agoSpoiler alert. Here is my Part 1 implemented in Ruby. http://gist.github.com/617566 http://gist.github.com/617566
- csmajorfive 16y agoI think this would've been a better filter for hiring if the magnitude were larger (e.g. huge string, more numbers for the combination, etc) or if there was a strict time limit. As it is right now, I don't think the hardcore hackers you're looking for will be that enticed.
- cakeface 16y agoI think that you'd be surprised at the sheer number of applicants a very basic programming challenge can weed out. The company that I work at has a simple test to parse a csv file and a surprising amount of people who appear to be good candidates bomb it.
- koblas 16y agoWhat about a puzzle system system -- Companies can post/host questions and then review the answers. I've drafted a quick blog post if anybody wants to comment more directly... Maybe I'll make it this weekends projects (since my frid.ge clone was killed by Facebooks new groups). http://bit.ly/b6GC6F http://bit.ly/b6GC6F
- sahillavingia 16y agoAny points for solving part 1 just scanning the text for something that stood out? Seriously though, this is awesome. I'd love to know how you guys do in terms of # of applicants and the end-result (any hires?).
- deleted 16y ago[deleted]
- btilly 16y agoTook < 10 minutes. The problems were very, very easy. If they expect people to take 1-2 hours and have trouble with this, then the message that I would take away from this is that their hiring bar is quite low.
- JesseAldridge 16y agohttp://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html http://www.codinghorror.com/blog/2007/02/why-cant-programmer...
- temugen 16y agoPython powerset() with max(), list.remove(), and sum() builtins made the last problem's solution ~5 lines long :)
- brandon 16y agoI don't know about powerset(), but challenge 3 was pretty trivial using Python's itertools module: http://gist.github.com/617663 http://gist.github.com/617663 (warning: spoilers)
- tylrdotorg 16y agoThis really doesn't reflect a programmers skills in anyway. I managed to write ruby to solve the problems, but I approached it to do for fun. Brain teasers aren't going to weed out the good from bad. Also, considering the instructions explicitly say "write code to..." I would say using tools that give you the answers is in fact cheating. It's like math test where you have to show your work.
- dann 16y agowhat did you put as answer for the first level?
- dann 16y agowhat did you put as answer for the first level?
- dann 16y agowhat did you put as answer for the first level?
- zaius 16y agoMy solutions, in ruby: http://gist.github.com/617672 http://gist.github.com/617672 Any improvements welcome! (warning - contains the answers!)
- gmaster1440 16y agoNice and short Haskell solution to #3: http://gist.github.com/617675 http://gist.github.com/617675 Ruby solutions to #1 and #2: http://gist.github.com/617676 http://gist.github.com/617676 http://gist.github.com/617678 http://gist.github.com/617678
- thomie 16y agoNice, but don't compute the length of a list if you don't have to. (not . null) instead of (\x -> length x > 1) is shorter, and works on infinite lists also. Edit: well, in case you would test for x>0.
- jiaaro 16y agosolutions in python http://gist.github.com/617686 http://gist.github.com/617686 about 30 lines of code in the tersest style, 40ish in the readability-obsesssive style I prefer
- cube 16y agoThanks for sharing! Love the style and it's readability. My newbie python code did the trick, but is way harder to read - your code really showed me room for improvement!
- Natsu 16y agoI see that you did brute force primality testing, too. Am I the only one who at least only divided by odd numbers (and two) in their brute-force is_prime function? Technically, you only need to test divide by all primes less than or equal to sqrt(n), after all. I guess I could have used a faster primality test, but I didn't feel like writing anything that complex. I know there's a website out there that has a test that works for anything under about 10 billion, if memory serves, by using the probabalistic tests and doing a special check for the only exception. Heck, it even gives you the factors for the largest number in its range...
- jiaaro 16y agothis code solved the problem in under 1 second. I would say for code that is executed one time ever, even including the sqrt(n) part is premature optimization (though I did include it)
- jewbacca 16y agoOh my god, Haskell is so pretty. This is the first time I've used it to solve math problems. Is it kosher to share solutions?
- brandon 16y agoI gist'd one because I saw others sharing. I'd be curious to see how you did things in Haskell.
- lisper 16y agoToo easy to solve by brute force. I'd suggest looking at Project Euler for inspiration.
- dkarl 16y agoI'm a little bored with Project Euler after solving the first 40+ problems with brute force or near-brute force algorithms. If I wasn't using it to learn a new language, I would have quit already. As it is, after solving one problem I usually quit for the day instead of moving on to the next. When do the problems pick up?
- lisper 16y agoWell that depends on your level of expertise :-) I start to have unsolved problems around #60, but found I had to start getting pretty clever long before that. The highest number I've solved is 112, and the one before that is 102. YMMV.
- Tichy 16y agoOr better, Google Code Jam problems.
- lamnk 16y agoDifficult level is about the same as Project Euler's problems 1x
- dasil003 16y agoHere's better-than-brute-force solution to Q1 http://gist.github.com/617715 http://gist.github.com/617715 Is there a better algorithm? Dynamic programming of some sort? I guess we'd need a longer string to tell the difference.
- leif 16y agoI can't read ruby, but here's something a little smarter than brute force in C (on its way to DP, but I couldn't be arsed to work out the recurrence so I just iterated until it stabilized): http://gist.github.com/617854 http://gist.github.com/617854
- dasil003 16y agoIt looks similar to mine, but you got lucky (or unlucky depending on how you look at it) that the longest palindrome had an odd character count. The confusing bits in the Ruby are actually just the definition of an even and odd palindrome finder, which are the same except for two seed values for where the first comparison is conducted and it's length.
- leif 16y agooh whoops nice catch thx
- ody 16y agosuckers ... no really, you are.
- deleted 16y ago[deleted]
- deleted 16y ago[deleted]
- _prototype_ 16y agoI did the naive implementation for problem 1. (double loop, O(n2)), in Javascript. Took chrome about 1 minute to compute the comparisons of all strings. I'm so lazy.
- shiven 16y agoSeems like I may be the only person to have used a bioinformatics approach to the first problem! bl2seq to the rescue!! I'll explain my approach if anyone seems interested... as I am not sure if posting solutions is acceptable here. Edit: As others seem to be posting gist/snips etc. so I guess it is OK. Step 0 - Copied parent string to file: p1.txt Step 1 - Used python to reverse the entire string and copy to second file: cat p1.txt | python -c "print raw_input()[::-1]" > p2.txt Step 2 - Formatted the two files, so as to be parsed as FASTA, by adding sequence name headers. Step 3 - Use bl2seq (blastp) locally or online to align the two "sequences". Final alignment shows only one major chunk of identity, i.e. the answer. So, in essence, a dynamic programming algo would work.
- stygianguest 16y agoIf bl2seq gets the longest common subsequence I did exactly the same thing. In haskell it just seems the right thing to do. Actually it would be damn interesting to see if there are patterns in the solutions for every programming language.
- olalonde 16y agoI thought the challenge was to solve everything with "grep" because of the "Greplin" title.
- badsquare 16y agonumbers ="3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97].split() numbers = [int(i) for i in numbers] def sum_eq(lst,k): total = sum(lst) if total == k or k==0:return 1 elif total < k or len(lst)==1:return 0 else: n1,nr = lst[0],lst[1:] return sum_eq(nr,k-n1) + sum_eq(nr,k) def sum_all_eq(lst): total = 0 for k in range(1,len(lst)): total += sum_eq(lst[0:k],lst[k]) return total
- hammerdr 16y agoAnyone else read Q2 as (sum of the prime factors of X) + 1? Confused me for a good 10 minutes :(
- stelfer 16y agoHere's mine: http://gist.github.com/618459 http://gist.github.com/618459 I didn't see the point in doing this in anything but C. I tried it without cheating, and to make it as interesting to myself as possible. Also did it after a week of writing briefs, so that was a nice way to unwind from that! Pretty Fun. Anyway, if I'm applying for a job (which I wasn't), the last thing I'm going to do is send in a bunch of one-liners.
- mace 16y agoIMHO, these contrived puzzles, while fun, are really unrealistic and don't map well to problems you'll encounter on the job which requires knowledge, experience and creativity and do not have just one answer. Of all of the jobs-page challenges, thesixyone's is probably the most practical and I've seen: http://www.thesixtyone.com/static/jobs http://www.thesixtyone.com/static/jobs
- LordLandon 16y agoMy C is terribly rusty, so I decided to not cheat with python: http://sprunge.us/GiDD http://sprunge.us/GiDD How terrible is it?
- hackermom 16y agoProblem 1: 2 minutes for 5 lines of PHP code. Problem 2: 1 minute of Google and Google (why reinvent the wheel?). Problem 3: half a minute of brainwork, 15 minutes worth of tedious PHP snippet. I got the impression that this particular test was not a good one for finding apt programmers. The questions and the solutions were just so very "off".
- g0 16y agohttp://codepad.org/rdSirAkD http://codepad.org/rdSirAkD -- Solution to third problem in 26 lines of ruby _without_ using combinations. It's pretty fast too, gives the answer in 0.020s.
- tta 16y agoAnyone know other 'challenges' like this one?