Log in

No account? Create an account
Working at Google Labs - brad's life — LiveJournal [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Working at Google Labs [Jul. 16th, 2004|11:56 am]
Brad Fitzpatrick
[Tags|, ]

There was an ad in the latest Linux Journal for GoogleLabs, with a puzzle involving a vending machine. The bottom of the page said if you submit the answer with a resume, your resume goes to the front of the queue. I solved it with a few lines of Perl and submitted the answer that day:
Date: Fri, 16 Jul 2004 11:54:34 -0700
From: labjobs@google.com
To: Brad Fitzpatrick <brad@danga.com>
Subject: Re: [#12106644] vending machine problem

Dear Problem Solver,

Thanks for taking the time to play with our little brain-teaser and for sending us your solution. While you won't find a confirmation of the answer in this email, we did want to let you know that your message was received and that we'll be taking a look at it. If you submitted a resume, we'll be spending some time with that as well. If it seems like there might be a fit with a position we have open, we'll contact you within the next few days.

And as for the answer to the puzzle, we'll post the ads and the solution on our site within a couple of months, after those who are a little slower than you have had a chance to work on it a bit longer. Thanks again for your interest in Google.

The Google Labs Engineering Team
Heh... too bad I didn't send them a resume.

[User Picture]From: lisa
2004-07-16 11:58 am (UTC)
i know you just asked evan for the answer
(Reply) (Thread)
[User Picture]From: brad
2004-07-16 12:05 pm (UTC)
Nuh-uh. I gots the ugly Perl to prove it!
(Reply) (Parent) (Thread)
[User Picture]From: bostonsteamer
2004-07-16 12:33 pm (UTC)
what was the problem? did you see a picture of their billboard? that's a fun problem too.
(Reply) (Parent) (Thread)
[User Picture]From: brad
2004-07-16 02:13 pm (UTC)
Just solved the billboard:
"Congratulations. You've made it to level 2. Go to XXXXXXXXXX.org and enter XXXXXXXXXXXXX as the login and the answer to this equation as the password.

f(1)= xxxxxx
f(2)= xxxxxx
f(3)= xxxxxx
f(4)= xxxxxx
f(5)= __________"
(Reply) (Parent) (Thread)
[User Picture]From: scosol
2004-07-16 02:34 pm (UTC)
thats been solved too, and ironically the answer can be found with google :D
(Reply) (Parent) (Thread)
[User Picture]From: brad
2004-07-16 02:37 pm (UTC)
Just posted the answer below, well with the answer xxxxx'ed out.

That's annoying people posted it on google. Kinda kills the point.
(Reply) (Parent) (Thread)
(Deleted comment)
From: (Anonymous)
2004-07-16 05:04 pm (UTC)
Are you aware that you just posted the solution to part 1? ;)

(Posted anonymously so it'll be screened)
(Reply) (Parent) (Thread)
[User Picture]From: brad
2004-07-17 05:00 pm (UTC)
Whoops. Thanks! Now blotted out:

Part 2:

bradfitz@bini:~/proj/google-prime$ ./part-2.pl | head -10
  0   1   2  1: 718xxxxxxx
  4   5   6  2: 8182845904
 22  23  24  3: 8747135266
 98  99 100  4: 7427466391
126 127 128  5: xxxxxxxxxx

(Reply) (Parent) (Thread)
[User Picture]From: mart
2004-07-16 02:50 pm (UTC)

Just out of interest (although the answers are all over the web) I decided to see how hard it would be to brute-force this. My dumb script just tries all possible sets of ten after a bit of sanity checking, and then uses LWP to try the request with a short timeout. After 20 attempts it found it. It would have been less effective if people owned some of the other answers!

The second part is harder to brute force, but I imagine a few people still tried it anyway. I kinda wonder whether Google are more interested in people who were able to figure out the nature of the sequence or people who find creative ways (completely dumb brute force doesn't count) to solve the problem without figuring out the pattern separately first…

(Reply) (Parent) (Thread)
[User Picture]From: brad
2004-07-16 02:57 pm (UTC)
Hah. It was only at position 20? My script didn't output the position for round 1.

Nice problem solving, sir.
(Reply) (Parent) (Thread)
[User Picture]From: mart
2004-07-16 03:05 pm (UTC)

Not quite. I did some quick checks on the numbers before doing the requests. For example, if it starts with zero it is out (less than ten digits) and also a quick loop to test dividing between everything between 1 and some constant (I forget what it was now, and I've destroyed the program to solve the second problem!) to see if any of them give a whole number. Only then does it make the HTTP request.

I think it was somewhere above the 30th position although I can't remember exactly where it was and I'm too lazy to write the one line of code it'd take to find out, too.

(Reply) (Parent) (Thread)
[User Picture]From: brad
2004-07-16 03:34 pm (UTC)
Primes can only end in 1, 3, 7, or 9, so that helps filter it a bit, if you're doing some really slow HTTP check. :-)
(Reply) (Parent) (Thread)
[User Picture]From: mart
2004-07-16 03:48 pm (UTC)

Aha… I knew there was some other prime rule I was forgetting. It's been a while since I did anything particularly mathematical. I should “practice” more.

(Reply) (Parent) (Thread)
[User Picture]From: bostonsteamer
2004-07-16 04:27 pm (UTC)
I think they're also looking for people with the motivation to actually solve the problem. I bet most people (me included) just look at it and say, yeah that's trivial, but never really solve it.
(Reply) (Parent) (Thread)
[User Picture]From: erik
2004-07-16 01:05 pm (UTC)
Remember when we 0wn3d (or, rather, you 0wn3d) that floor word competition in Terry by writing some Perl? It was something about finding all of the words in the dictionary that have at least 3 pairs of letters, or how many other words could be formed from some word.

What was the nature of this question, anyway?
(Reply) (Parent) (Thread)
[User Picture]From: czircon
2004-07-16 01:04 pm (UTC)
It must have been a pretty tricky puzzle if you had to use more than one line of Perl to solve it.
(Reply) (Thread)
[User Picture]From: mpnolan
2004-07-16 06:40 pm (UTC)
I wrote a post about this recently, actually! If anyone hasn't seen the ad and would like to, I scanned in the images.

(Reply) (Thread)
[User Picture]From: brad
2004-07-16 06:47 pm (UTC)
(Reply) (Parent) (Thread)