Google's profit increased seven-fold. Do you want to work there? Well here are 2 questions that they asked a friend of mine. What would you answer?
1. You have been shrunk down to the size of a nickel and tossed into a blender. You are told that the blender blades will start in 60 seconds.What would you do to save your life?
2. Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests.These are the particulars.
* You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC's)
* The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line.
* You can use only custom written applications or available free open-source software.
Subscribe to:
Post Comments (Atom)
41 comments:
Dude,
You broke their NDA by publishing this question. But I care less for Google, I am looking at interview questions and I got one.
Thanks a lot...
He's not breaking their NDA, his friend did.
(1) is easy, lie down.
1. Lay low
2. split file btw all computers, have each tally the number of queries, combine all results.
(2) sounds like an application of MapReduce...
There's no NDA for interview questions.
For all the people who said lay low, put a blueberry in a blender and look what happens. My friend answered that he would pull out his hair and take off his clothes and would try to jam the motor with that
As for the NDA, unless you sign something you are not breaking anything. Since I did not interview with Google and thus did not sign anything I am not breaking their NDA
I would grab on to one of the blades and hold on for dear life. As long as I'm attached to the blade, it can't chop me!
1. Go to the center of the axle to which the blades are attached and hold tight. Centrifugal force is 0 in the center of rotation, so you'll just get a bit dizzy :)
2. sounds like a work for an on-disk hash table. calculate MD5 of each search term, xor-fold it twice to 32 bits and use it as the hash function key. The search query is the key. Distribute the hash table across 12 servers by the (e.g.) most significant 4 bits of the hash function. Each machine is both a client and server (just sends the data to the appropriate machine). Use BerkeleyDB for the hash table. When done, each server chooses its own top million records, then simple merging of 12 sorted sequences should produce the answer.
But how long can you hold on for?
I think they are inspired from the "Saw" movies in the first question. :) (http://www.imdb.com/title/tt0387564/)
Zvrba,
If each computer only communicates its top 1,000,000 records, your final list might not be the top 1,000,000 records.
Take the case where the top 1,000,000 records of all computers are distinct and have only one hit.
But lets say that the 1,000,001st record on each computer was the same item with one hit. So, using your algorithm on this data could result in the most frequent keyword never landing in your top 1,000,000.
David: OK, I'm guilty for too vague explanation. Each item has unique hash, so its count is stored on exactly one computer (that is chosen depending on the hash value). So your example canot happen.
sounds like a work for an on-disk hash table
That's overkill. The files may be huge, but the number of distinct queries will not be. For example, you can store all valid English words about a megabyte...the number of phrases people type in to Google is not that many orders of magnitudes greater, so just use an independent hash table in RAM and combine the results at the end.
At 1/2 inch high, if your bodily proportions were not altered, you would be immensely string. Seriously ant-style 'carry 50 times your weight' strong. There's a serious likelyhood you could lift the blades off the bottom... they detach anyway for cleaning in most blenders.
If I couldn't do it in 60 seconds, I'd do what another poster said... grab onto the shaft. With my itsy-bitsy Sampson strength, I might even be able to hold on for the giant torturing me to give up.
*cough* Strong. Immensely strong.
I'd unscrew the blade assembly with my thin edge.
Hash idea sounds cool, might be a good idea to first do the count of each item on each individual machine, and then send the local count to each aggregating machine (determined by hash bits). Might be a lot less network traffic than sending each item individually.
Love the "thin edge" comment :)
Easy, jump out.
Muscle strength is proportional to area, so shrinking to 1/100 size I would be 10,000th as strong. But mass is proportional to volume so I would be a millionth as heavy. Therefore relative to my weight, I would be 100 times stronger. Since I can jump about a tenth of my height when I am ~2m tall, I would be able to jump 20cm when shrunk. -- So I could jump clear out.
Abusing the physics further...
I always have a Photon-MicroLight in my pocket. Being 1/100th the size the density of photon emittance is 10,000 times greater (being proportional to area). That could probably burn through the wall of the container, allowing my egress.
More speculatively...
My voice would by hypersonic at that size. With some shouts and whistles I could irritate a nearby cat or dog into knocking over the blender. I then escape, with my super jumping power and pocket light laser weapon of course.
Idiots all of you. All you have to do is walk away from the center of the blender out of the range of the blade. The length of most blender blades is no more than 1/2 the raidus of the blender itself easily leaving enough room for someone the size of a nickel to chill by the glass wall and laugh.
Well sounds more like the trick question in Spike Lee's latest movie "Inside Man"...
At least the one with the blender ;-)
Easy peeze
Text help I left my diamond ring in your blender to the dude
Micro Mike
If I were shrunk down to the size of a nickle my density would be so high I could probably bend steel or punch through the flimsy glass wall.
stupid non-work related interview questions.
1) I tell who shrunked down me that he has 59 seconds to stop the blades or he will waste a nickel
2) ...do you really think I work for free? Hire me first and then you will know how!
1. the first question is not complete. The question says that your weight and dimensions are reduced proportionately to keep your density un-changed.
2. in secind question i think hasing or watever method you use we shold keep in mind that we do have 4GB of RAM avaiable on each machine so we should try to do manipulations in the chunk of 4GB. Also since each server has 2 processors we distribute the work on each of them equally to speed things up.
1) As mentioned above, at the size of a nickel (assuming that they mean that your height has been reduced to the diameter of a nickle) then all you have to do is press yourself to the edge of the blender. A typical blender's blades can't reach the sides and there'll be TONS of space in between. Then again, most blender jugs are cone-shaped at the bottom to direct food towards the center, so you'd have to fight slippage somehow. Other then that, go right to the center and embrace the spindle (also mentioned above).
2) This is deffinately a job for MapReduce. It's exactly what they (google) built it for. I'm guessing this is to make sure you've done your homework about the company rather than to test your skills.
An NDA for an interview? _Must_ destroy...
When they size me down to the size of a nickle, I became the NickledMe. Now, there would be atleast over a 100,000 nickles in a box made to fit me. So the compression ration for compressing me to that size would be 1:100000. And hence, the NickledMe would be hard enough not to be affected by the blades.
And hence my friends, I would not have to do anything.
But to think about this in a minute is kind of difficult. (It took me under a minute to click with this idea and another minutes to come up with the over 100000 number without a calculator... which I think would have been nice to have in the blender thrown along with me....) So I will try my best to hide out somewhere where I think I can get the least injury depending on the structure of the balde. And hope that I come out alive without my legs or something if at all. But as soon as the blender starts, I will find out that all I did was of no use, as I am strong enough to beat the blades. And so am I to break this interview @ Google.
I got the answer to the nikel question. Essentially, since your mass will be proportianally reduced with respect to height, you can say.. assuming my weight is 215 lbs 6 feet tall... and if a nickel is half an inch tall, that would make me 1.5 lbs. Blenders are no more than 4 lbs, so you represent almost 40% of the weight, thats quite a lot!. Now, within the 60 seconds, you need to climb up to the highest notch of measuring and try to topple over the blender by rocking back and forth... if you are 1.5lbs in a 4 lb blender... this is totally possible.. once it has toppled, walk out of the blender... bam!
i would run headlong into a blade and skewer myself on it. then, when the blades started up, i would go flying off and splatter all over the wall of the blender in a spectacular fashion. if i was really lucky, maybe i'd get flung out of the blender and then the giant running it has to deal with a nickel sized lump of goo mess on their rug.
Yer all hired!
Cool questions!
(1) My weight is 78 kg, and assuming no atoms are "lost" in the shrinking process, I would still weigh 78 kgs. Simply walk to the side of the container and make it fall over and walk out.
(2) I would use random sampling here.
First I would write a small program that calculates how many loglines I need to randomly sample to get X percent accuracy of the Y top searches. Now I can control the tradeoff between accuracy and time spent parsing (i.e. the number of loglines to parse).
I would now try this on a small set, e.g. get a 95% accuracy of the top 10 searches out of 1 millino loglines. I would probably use C or C++ for the random reading, or just some scripting language. I would also probably just use mysql or something like that to store the hits.
If the results look promising, I would start crunching on the real data.
Cheers,
Christian Stigen Larsen
As with all good theories I think some practical testing is in order...
Clearly we cant shrink anyone, so, lets reverse engineer the question.
Someone go make a massive blender, and then you guys can all throws yourselves in - I'll sit on the outside and watch..
:D
I Wud probably let the blender take its own course.
After all what use is being a Nickel and living life like a fish out of water.
without my PC and my GF it wud suck bigtime ;-)
~Frederick
Thank you for this post. I have not gone through an interview with Google but I came across this site which have some sample questions
http://www.technical-interview.com
1 is really easy, just sit down and relax in a corner, coz the question no where specifies that there is liquid also filled in the blender.
ITs just you and the blades and no matter how hard the air is blended it wont affect you anyway :)
Cheers.
1 is pretty straightforward.
jump right to the centre of blender-rotar. tie urself up to the sentre rod/shaft and then sit tight for a "trip to hell"
as for 2 computing is no more my area.
Post a Comment