Google Interview Questions

 

This is a list of interview puzzles used at Google.

 

You have to get from point A to point B. You don?t know if you can get there. What would you do?Imagine you have a closet full of shirts. It?svery hard to find a shirt. So what can you do to organize your shirts for easy retrieval?What method would you use to look up a word in a dictionary?

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than herhusband has cheated, but does not know when her own husband has. The village has a law that does not allow foradultery.Anywife who can prove thather husband is unfaithful must kill him that very day. The women of the village would neverdisobeythislaw.One day, the queen of the village visits and announce that at least one husband has been unfaithful. What happens?You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?How do youcutarectangular cake into two equal pieces when someone has already taken a rectangular piece from it? The removed piece an be any size or at any place in the cake. You are only allowed one straight cut.

 

How many piano tuners are there in the entire world?

 

What gives you joy?

 

Mike has $20 more than Todd. How much does each have given that combined they have $21 between them. You can?t use fractions in the answer. Hint: This is a trick question, pay close attention to the condition)

 

How many times a day a clock?s hands overlap?

 

Two MIT math graduates bump into each other. They hadn?t seen each other in over 20 years.

 

The first grad says to the second: ?how have you been??

 

Second: ?Great! I got married and I have three daughters now?

 

First: ?Really? how old are they??

 

Second: ?Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..?

 

First: ?Right, ok.. oh wait.. I still don?t know?

 

second: ?Oh sorry, the oldest one just started to play the piano?

 

First: ?Wonderful! my oldest is the same age!?

 

Problem: How old are the daughters?

 

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)

Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it?s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

 

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

 

In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?

 

You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?

 

 

Google interview questions

•The rectangle puzzle has a special case which does allow for an answer. If the rectangular removed piece is smaller than the cake, then the solution is to make a cut which joins the centre of the cake with the centre of the removed piece (if these centres are the same point, then any cut through this one point). However, if the removed piece is the whole cake, then there is no possible cut, since there is no cake. I wonder how many people figured this out (and I include the people who made up the question).

 

•The last question about putting people in a room is the only one related to anything at Google. The solution is simply the Gray code, which is actually something of mild interest in Computer Science, and whose knowledge might actually be useful to future work at a computer company. The other questions are either silly, trivial if you know some math, or just wrong.

 

•the 8 balls question answer is

1)take any 7balls from 8 and keep remaning aside

2)take any 6balls from that 7 keep remaing aside

NOW

CASE:1)

weigh:1)3 and 3 of that 6 if equal then

weigh:2)that 1 and 1 from remaing finish.

 

CASE:2)

weigh:1)same 3 and 3 of that 6 if not equal

weigh:2) 1 and 1 of that odd 3 finish

 

•The ball question is silly because the algorithm works for up to 9 balls. In general, you can find the heavier ball in N weighings if there are at most 3^N balls, so using a non power of 3 misses the point. The general algorithm for 3^N balls is:

Take 2 groups of 3^(N-1) balls. If they weigh the same, then the ball is in the 3rd group, and you can find the ball in a further N-1 steps by recursion. Otherwise, the ball is in the heavier group, and you can again find it in N-1 further steps by recursion.

The adjustment for non powers of 3 is clear.

This is probably the easiest coin problem. The harder ones don?t tell you if the coin is heavier or lighter.

 

•You can also outwit the examiner in the clock quesiton. Normally the answer would be 22, but that is assuming that there are only hour and minute hands. However, you can outwit the examiner by making the formally correct statement ?most clocks have a second hand? and just wait there until he figures it out. Since this would obviously guarantee you wouldn?t get the job, I?m wondering if the real point of these questions is to make sure that you aren?t smarter than the people who made them up.

 

•Anyone felt dumber reading Ilan?s responses?

On the rectangular cake, don?t cut it from up to down. Cut across at mid-height.

The point of asking ?8? balls is to lead people to think to weigh 4 with 4, 2 with 2, 1 with 1, etc. Weighing ?9? balls actually make the question easier.

On the married couples question, use induction and start with the village having only 1 couple, then 2, and so on. Think in terms if you were the wife, and you cheated with someone?s husband, how would you deduce if your husband cheated and whether or not the other wife can deduce.

 

•If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands?

- Degrees per clock cycle or a circle: 360

- Degrees per clock cycle Ticks: 360 / 60 (total minute ticks in a clock) = 6 degrees

- Ticks between two hour digits: 5

- Minute Hand Ticks per Hour Hand Movement: 60/5 = 12

Using above data we can calculate the exact clock hands position & angle for 3:15 Time i.e.

- Minute Hand position will be: 3

- Change in Hour Hand position will be: (5/12) * 15 = 1.25 (exact ticks out of 5 hour ticks between two hour digits & this is also an exact ticks difference from minute hand)

- So, ar there is (360/60) 6 degrees difference between two clock ticks hence thers is 1.25 * 6 = 7.50 exact degrees difference between minute & hour hands in 3:15 clock time :)

 

•The answer to the bridge crossing questions:

I will use following terms.

camper1 - camper who can cross the bridge in 1 minute

camper2 - camper who can cross the bridge in 2 minute

camper5 - camper who can cross the bridge in 5 minute

camper10 - camper who can cross the bridge in 10 minute

1. camper1 and camper2 crosses (2 min)

2. camper1 gets back (1 min)

3. camper5 and camper10 crosses (10 min)

4. camper2 gets back (2 min)

5. camper1 and camper2 crosses (2 min)

Total 17 min.

 

•To CSharp?s question:

?If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands??

The way I thought it was (ends in same result as urs):

The answer is that the hour hand moves 360 degrees in 12 hour. That is 30 degrees each hour - 7.5 degrees each quarter.

Therefore the difference between the hands at 3 and warter is 7.5 degrees !

 

•MIT Math Graduates Problem:-We know that 72?s factor are 2*2*2*3*3.Now we need to calculate all possible combinations of ages from those factors.The Combinations will be:-(2,4,9) and (2,6,6) and (2,3,12) and (3,3,8) and (3,6,4).For every combination the sum of ages will be (15) and (14) and (17) and (14) and (13) respectively.14 is the only digit which comes twice so that is the digit which is written on building that?s why first graduate couldn?t find out their correct ages.So possibly the ages should be (2,6,6) or (3,3,8).Now second graduate says that his oldest daughter just learned piano so this statement indicate that his oldest daughter is not twin so surely there ages will be 3 and 3 and 8.

 

•The Restangular Cake solution:

Whatever be the shape and size of the cut piece.

Just cut the cake horizontally from mid of the height.

thats all!

 

•To explain the cake solution:

1) cutting a whole cake in half, in one strait cut, requires going from one side, through the center of the cake, to the other side (we can chose any angle we like).

2) cutting the empty part in half , using one strait cut, requires going from one side of the empty part, through the center of the empty part, to the other side of the empty part.

- The solution requires both cutting the whole cake in half, and cutting the empty section in half, so we combine (1) and (2) to one striat cut through both centers.

As explained by Ilan.

 

•How many times a day a clock?s hands overlap?

Only 11 times. Overlap exists on or after every hour except after 11'o clock.

Srikanth Bethi

 

•How many times a day a clock?s hands overlap?

Above answer is incomplete?.in a it completes 2 rounds?in the round it gets 11 times and in the second round it gets only 10 times?

so the total is 21 times in a day

 

•What gives you joy?

Word ?YOU? is having letters ?Y? & ?O? and it requires letter ?J? to make ?JOY?. So the answer is ?J?.

 

•Another way of looking at the 3:15 clock problem:

Normally hour hand moves 1/12 of clock each hour.

For 15 mins, it?s 1/4 of that then, or 1/48.

Then 360 degrees / 48 = 7.5 degrees.

Same answer, of course.

 

•For the $20 trick question, i think i just figured it out.

M = 20 + T

M + T = 21

Substitute M: 20 + 2T = 21

T = 0.5

So, Todd has $0.50 and Mike has $20.50.

Oh, and i didn?t use fractions in my answer.

I used decimals.

 

•probability of watching a car is .95 in 30 min

it means probability of watching a car is 95% in 30 min

probability of watching a car per minute is 95/30=1.9%

probability of watching a car in 10 minute is 1.9* 10=19%

 

•To Vimal Garg,

Your answer to the three girls? age is right, but you can?t just verifying 72?s factor which is 2*2*2*3*3, because it is possible that the youngest daughter?s age is 1, for example: 1, 6, 12.

The point to the question is that, there must be several combinations result in the same summary. Like 2+6+6 = 3+3+8 = 14. And there could be only one who has the oldest age, that is 8

 

•To gaurav khatwani,

your math is wrong in more than one spot.

You can?t merely say probability of seeing a car in one minute is x and therefore in 10 minutes its 10*x. Probabilities don?t add up like that.

Think of tossing a quarter. The probability of seeing a heads in 2 flips is 3/4 not 1/2 + 1/2.

Solution (I think) is the probability of not seeing a car in 30 minutes is 05%.

If the probability of not seeing a car in 10 minutes is x. then for each additional 10 minutes we multiply by x. so x^3 = .05

So the probability of seeing a car in 10 minutes is thus 1 - cuberoot(.05)

 

Google interview questions

 

1.answer to boy and country question:

say there are 100 families, that means there will be exactly 100 boys. Lets figure out how many girls.

50 families will have a girl on their first try,

25 will have a girl on their second try

12.5 on third and so on.

so 1/2 of the population has at least 1 girl, 1/4 has at least 2 and so on.

this reduces to avg # of girls per family = 1/2 + 1/4 + 1/8? = 1

so the proportion is 1 to 1

 

2.FWIW I interviewed there 11 times and didn?t get asked any of these. Indeed, nothing like these. These are just puzzles. The questions I got asked were arguably harder, but certainly more directly related to engineering and computer science.

 

3.Query: How do you cut a rectangular cake into two equal pieces when someone has already taken a rectangular piece from it? The removed piece an be any size or at any place in the cake. You are only allowed one straight cut.Soln. Proposed:

Cake is a three dimentional thing. Irrespective of the size of a rectangular piece cut from it, if we cut the cake horizontally from the middle of its height, it?ll be cut in two equal halves.

 

4.the answer to the clock question is actually 23

the first round starts at midnight when both hands are on 12 overlapping, then an overlap occurs after each hour before noon, so, this is 11 overlaps, + 1 at noon, + 11 more on the second round, making it 23 overlaps per day, and the 24th one will be actually the first overlap of the next day,done

 

5.Cake:

Start from a easy one. A straight line passing through the center of a rectangle will cut the rectangle into two halves with same area.

Now the problem. A line passing through both center will cut the cake into tow halves with same area.

Car:

qbaler is correct I think. but i can not find what?s wrong with following calculation.

If the possibility of seeing 1 car in 10 min is p, then:

1) chance of seeing 1 car in the first 10 min = p*(1-p)^2

2) .. = (1-p)*p*(1-p)

3)so, the chance of seeing 1 car in 30 min is:

3*p*(1-p)^2 = 0.95

=> p = 1.465

 

6.guys

the answer to the car question is

cuberoot 95/ cuberoot 100

the answer is easy.

imagine that you roll a dice. what is the possibility to have a 1? 1/6 right

roll it twice.. it s 1/36

so think that 30 minutes is three times 10 minutes.

to 95/100 (95%) is a cube of three numbers.

which gives the correct result as cuberoot 95/ cuberoot 100

 

7.The probability to have a 1 show up if you roll a 6 sided die is indeed 1/6. You could end up with (1), (2), (3), (4), (5), or (6), and only (1) is a favorable outcome.

With two dice, there are 36 possible outcomes. I won?t list them all, but here are a few:

(1,1), (1,2), (1,3), ?

(2,1), (2,2), ?

(3,1), ?

There are several favorable outcomes where a 1 is present out of the 36 rolls. There are 6 ways for the first die to be any number while the second die is a 1, and there are 6 ways for the second die to be any number while the second die is 1. Having counted (1,1) twice, you end up with 11/36 as the probability of having at least one 1 show up when you roll two dice.

Unless you are asking for (1,1), then the probability is 1/36.

 

8.puttyshell:

The question doesn?t ask ?What is the probability of seeing 1 car in 10 minutes, and no cars in the other 20 minutes??

Also, your final answer of p = 1.465 is not possible because that value is greater than 1!

 

9.For the Mike and Todd problem, it says there is a tricky question. I got a different angle of the problem.

Let T have x, then M has x+20.

They both have to give sth so they have 21 between them.

So x should be 1, so that M gives 20 and T gives 1 to make 21 between them.

 

10.For the boy girl ratio problem, the number of girls is a taylors series:

probability of having a boy in the first try is 0.5

and the second is 0.25 etc. assuming no kids die then

the number of girls would follow:

x * (0.5 + 0.25 + 0.125 + ?) or Sum(1/(2^i), i=1..infinity) which is equal to 2.

So on average there should be 1 boy to 2 girls.

 

11.for the cake problem?. if the cut is made horizontally in the middle

of the depth of the cake it will be 2 equal pieces, no matter what the

size or shape or place of the cut?

And for the clock? answer is 22?this can be found easily , as each overlap of the 2 hands occur at 12/11th of an hour?

 

12.For the searching the words in dictionary.. I feel the binary search as the best method. As the search will be reduced to half after each iteration.

 

13.For the cake problem. As the original cake and removed piece are rectangles. If you think these in 3dimensional view. Any line passing throug their centroid( I mean center of gravity) will be the single straight cut. If you cut in any other ways you can be proved false with some case.

 

14.qbaler, you?re right that 1/2 + 1/4 + 1/8? = 1. however, the chance of having a boy is still 1/2. So the proportion is 1 to 1/2 (or 2 to 1)

 

15.Assuming it?s an analogue clock, the clock is probably built with one skrew in the middle which hold the two hands in place. Since it is most always one skrew for both hands, the two hands overlap in the middle all day and night. So the answer is that the hands overlap all day and night.

 

16.Regarding the clock angle prob:

Solution:-

We need to identify two things:

1. Angle movement per hour :- 360/12 = 30 degree

3. Angle movement per minute corresponding to per hour :- 0.5 (1 hour = 30 degree; 60 minute = 30 degree; 1 minute = 30/60 = 0.5 degree)

So, 15 minute movement will create angle of 7.5 degree (.5 * 15) between hour and minute hand.

 

17.1. by colour

2. buy some dictionary first

3. nothing queen doesnt live in the city and her husband was unfaithful

4. take 6 then take 2

5. find the man with the missing piece and get it

6. less then pianos

7. joy is to read this and know some questions so u can talk to yourself you are not dump

8. $20 and $1

9. dont understand my english poor, dont know when they achieve their mit and the sentence with 72

10. if its not 0 so its 360

11. 1&2 then 1 come back then 5&10 then 2 come back then 1&2

12. 0.95

13. girls > boys cause they want boys

14. hmm again my english poor dont understand the sentence

 

18.Maybe I am wrong, but I see people made the clock question over complicated. The Way I see it is that for each hour the minute hand makes a full circle, so for each hour they over lap only once and therefore for 12 hours its gonna be 12 times.

 

19.The boy girl problem is simple (once you get past the implicit assumption that boys/girls are each born 50% of the time, which technically isn?t exactly true).

No matter what strategy people use, every time someone gets pregnant, there is a 50/50 chance of boy/girl. The final ratio is 1:1.

A better formed problem would be a room full of coin flippers. If everyone flipped until they got a Head, in the end, you would expect a total of 50% heads and 50% tails. Figure out a different answer, then take it to Vegas and try to beat a roullette wheel :)

 

20.Actually the ?8 ball? question is much more interesting when we do not know that odd ball is lighter or heavier others. We will need one more weighing though, but we can increase number of balls to 12.

 

21. ques: You have to get from point A to point B. You don?t know if you can get there. What would you do?

 

Ans: I will start searching for Point B moving on a spiral path starting from point B.

 

22. ques:  Imagine you have a closet full of shirts. It?s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

 

Ans. separate shirts on the basis of color and then arrange according to company?s name in alphabetical order.

 

23.2. Imagine you have a closet full of shirts. It?s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

I would first ask myself what criteria I normally use when looking for a shirt. I would then sort sort them according to those criteria, pretty much like a DBA does when indexing tables to optimize them most frequent queries.

 

24.Dingo, you are right. I was actually thinking the flawed way, until I tried to right a Python script to simulate the problem (I?m a good programmer, but terrible at calculus). You don?t even have to run to see that the result will always be 0.5 (assuming random() is really random :)

import random

boysCount = 0

girlsCount = 0

for a in xrange(10000000):

isGirl = random.random()

while isGirl

 

25.Q: You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?

A: Yes.

See if you notice the pattern (0 = outside, 1 = inside):

000000

000001

000011

000010

000110

000111

000101

000100

001100

001101

001111

001011

001001

001000

011000

011100

011110

011111

010111

010011

010001

010000

This pattern will cover every possible combination and can be repeated for any number of bits (people). Other valid patterns may exist.

 

26.Q: You have to get from point A to point B. You don?t know if you can get there. What would you do?

A:

I?d start by googling ?A B?, gathering as much information as possible;

Then, I?d try to talk to someone in the team knowledgeable on those points;

Next, I?d go back to my lead and make sure I?ve understood what A and B are;

Hopefully, this should give me enough information start the journey;

 

27.Clock hands will overlap 22 times (All times approximate):

00:00, 01:05, 02:10, 03:15, 04:20, 05:25, 06:30, 07:35, 08:40, 09:45, 10:50,

12:00, 13:05, 14:10, 15:15, 16:20, 17:25, 18:30, 19:35, 20:40, 21:45, 22:50

 

28.Q: How many piano tuners are there in the entire world?

Assuming:

* World population 6 billion

* One in 10000 people own a piano

* One tuner will tune, on average, 2 pianos a day

* A piano needs tuning once every year

There are 600000 pianos;

They will require 600000 tuning every year

One single tuner can tune 520 pianos a year (2 tunes x 260 week days in the year)

Approximately 1153 piano tuners are required.

In questions like this, they are not really interested in the answer you give, but how did you get to it. Stating your assumptions as clearly as possible helps. Also, you may want to get to your answer using two or rationales. In this case, you may want to guess the number of pianos by the number of house holds in the world and the ratio of those with enough money to own a piano, etc.

 

29.Clock hands - 24 times per day. For those of you who stated that at the end of the day (midnight), it is actually the next day - if you use this assumption, then you must count that as the first time they cross on that day. You can simplify the question by asking ?How many revolutions does the minute hand make in a day?? 24

Unfaithful husband - the only woman who isn?t aware of the infidelity immediatelly kills her husband (everyone else already knows he did it, including the Queen - how much more proof do you need?).

 

30.If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)

360/(12*4)= 7.5 degree is the angle ?where 4 comes from (60/15)

 

31.The cake: It?s not possible, in practical terms, to cut any cake equally. Cutting it horizontally ignores the roundness at the top of the cake, to say nothing of the extra frosting on top, or who gets the rose decoration. Even if one rules those things out, there will always be something to quarrel about, no matter how the cake is divided. That?s why in a case like this, you ask one recipient to cut it, and the other recipient to have first choice re which piece he wants. Trust me, I have twin boys.

 

32.Two MIT math graduates bump into each other. They hadn?t seen each other in over 20 years.

The first grad says to the second: ?how have you been??

Second: ?Great! I got married and I have three daughters now?

First: ?Really? how old are they??

Second: ?Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..?

First: ?Right, ok.. oh wait.. I still don?t know?

second: ?Oh sorry, the oldest one just started to play the piano?

First: ?Wonderful! my oldest is the same age!? Problem: How old are the daughters?

? The answer: Unknown.

The solution makes false assumptions:

1.) The guy knew that two possible combinations had the sum 14

2.) The guy could see the building number

3.) Two children cannot be the same age.

Key #3 is the most important. It is possible to have two six year olds and a two year old. Twins. With twins, there is ALWAYS an older child. So, it is perfectly legit to say that you have two six year olds, one two year old, and the oldest began playing piano.

 

33.Jay Jay? What about 11:55 and 23:55?

Cake? Horizontal cut answers assume the rectangle removed is the same height as the cake.

As pointed out by Jay Jay, if I asked you any questions like these it is your thinking process that I care about. Are you easily discouraged by a tough situation? Do you find negatives or solutions? Can you venture a solution even if it might be wrong?

 

Google Placement Paper and Sample Paper

 

GLAT (Google Labs Aptitude Test)

 

1. Solve this cryptic equation, realizing of course that values for M and E could be interchanged. No leading zeros are allowed.

 

WWWDOT - GOOGLE = DOTCOM

 

This can be solved through systematic application of logic. For example, cannot be equal to 0, since . That would make , but , which is not possible.

 

Here is a slow brute-force method of solution that takes a few minutes on a relatively fast machine:

 

This gives the two solutions

 

777589 - 188106 == 589483

777589 - 188103 == 589486

 

Here is another solution using Mathematica's Reduce command:

 

A faster (but slightly more obscure) piece of code is the following:

 

Faster still using the same approach (and requiring ~300 MB of memory):

 

Even faster using the same approach (that does not exclude leading zeros in the solution, but that can easily be weeded out at the end):

 

Here is an independent solution method that uses branch-and-prune techniques:

 

And the winner for overall fastest:

 

2. Write a haiku describing possible methods for predicting search traffic seasonality.

 

MathWorld's search engine

seemed slowed this May. Undergrads

prepping for finals.

 

3.

 

1

1 1

2 1

1 2 1 1

1 1 1 2 2 1

What's the next line?

 

312211. This is the "look and say" sequence in which each term after the first describes the previous term: one 1 (11); two 1s (21); one 2 and one 1 (1211); one 1, one 2, and two 1's (111221); and so on. See the look and say sequence entry on MathWorld for a complete write-up and the algebraic form of a fascinating related quantity known as Conway's constant.

 

4. You are in a maze of twisty little passages, all alike. There is a dusty laptop here with a weak wireless connection. There are dull, lifeless gnomes strolling around. What dost thou do?

 

A) Wander aimlessly, bumping into obstacles until you are eaten by a grue.

B) Use the laptop as a digging device to tunnel to the next level.

C) Play MPoRPG until the battery dies along with your hopes.

D) Use the computer to map the nodes of the maze and discover an exit path.

E) Email your resume to Google, tell the lead gnome you quit and find yourself in whole different world [sic].

 

In general, make a state diagram . However, this method would not work in certain pathological cases such as, say, a fractal maze. For an example of this and commentary, see Ed Pegg's column about state diagrams and mazes .

 

5. What's broken with Unix?

 

Their reproductive capabilities.

 

How would you fix it?

 

[This exercise is left to the reader.]

 

6. On your first day at Google, you discover that your cubicle mate wrote the textbook you used as a primary resource in your first year of graduate school. Do you:

 

A) Fawn obsequiously and ask if you can have an autograph.

B) Sit perfectly still and use only soft keystrokes to avoid disturbing her concentration

C) Leave her daily offerings of granola and English toffee from the food bins.

D) Quote your favorite formula from the textbook and explain how it's now your mantra.

E) Show her how example 17b could have been solved with 34 fewer lines of code.

 

[This exercise is left to the reader.]

 

7. Which of the following expresses Google's over-arching philosophy?

 

A) "I'm feeling lucky"

B) "Don't be evil"

C) "Oh, I already fixed that"

D) "You should never be more than 50 feet from food"

E) All of the above

 

[This exercise is left to the reader.]

 

8. How many different ways can you color an icosahedron with one of three colors on each face?

 

For an asymmetric 20-sided solid, there are possible 3-colorings . For a symmetric 20-sided object, the Polya enumeration theorem can be used to obtain the number of distinct colorings. Here is a concise Mathematica implementation:

 

What colors would you choose?

 

[This exercise is left to the reader.]

 

9. This space left intentionally blank. Please fill it with something that improves upon emptiness.

 

For nearly 10,000 images of mathematical functions, see The Wolfram Functions Site visualization gallery .

 

10. On an infinite, two-dimensional, rectangular lattice of 1-ohm resistors, what is the resistance between two nodes that are a knight's move away?

 

This problem is discussed in J. Cserti's 1999 arXiv preprint . It is also discussed in The Mathematica GuideBook for Symbolics, the forthcoming fourth volume in Michael Trott's GuideBook series, the first two of which were published just last week by Springer-Verlag. The contents for all four GuideBooks, including the two not yet published, are available on the DVD distributed with the first two GuideBooks.

 

11. It's 2PM on a sunny Sunday afternoon in the Bay Area. You're minutes from the Pacific Ocean, redwood forest hiking trails and world class cultural attractions. What do you do?

 

[This exercise is left to the reader.]

 

12. In your opinion, what is the most beautiful math equation ever derived?

 

There are obviously many candidates. The following list gives ten of the authors' favorites:

 

1. Archimedes' recurrence formula : , , ,

2. Euler formula :

3. Euler-Mascheroni constant :

4. Riemann hypothesis: and implies

5. Gaussian integral :

6. Ramanujan's prime product formula:

7. Zeta-regularized product :

8. Mandelbrot set recursion:

9. BBP formula :

10. Cauchy integral formula:

 

An excellent paper discussing the most beautiful equations in physics is Daniel Z. Freedman's " Some beautiful equations of mathematical physics ." Note that the physics view on beauty in equations is less uniform than the mathematical one. To quote the not-necessarily-standard view of theoretical physicist P.A.M. Dirac, "It is more important to have beauty in one's equations than to have them fit experiment."

 

13. Which of the following is NOT an actual interest group formed by Google employees?

 

A. Women's basketball

B. Buffy fans

C. Cricketeers

D. Nobel winners

E. Wine club

 

[This exercise is left to the reader.]

 

14. What will be the next great improvement in search technology?

 

Semantic searching of mathematical formulas. See http://functions.wolfram.com/About/ourvision.html for work currently underway at Wolfram Research that will be made available in the near future.

 

15. What is the optimal size of a project team, above which additional members do not contribute productivity equivalent to the percentage increase in the staff size?

 

A) 1

B) 3

C) 5

D) 11

E) 24

 

[This exercise is left to the reader.]

 

16. Given a triangle ABC, how would you use only a compass and straight edge to find a point P such that triangles ABP, ACP and BCP have equal perimeters? (Assume that ABC is constructed so that a solution does exist.)

 

This is the isoperimetric point , which is at the center of the larger Soddy circle. It is related to Apollonius' problem . The three tangent circles are easy to construct: The circle around has diameter , which gives the other two circles. A summary of compass and straightedge constructions for the outer Soddy circle can be found in " Apollonius' Problem: A Study of Solutions and Their Connections" by David Gisch and Jason M. Ribando.

 

17. Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.

For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

 

The following Mathematica code computes the difference between [the cumulative number of 1s in the positive integers up to n] and [the value of n itself] as n ranges from 1 to 500,000:

 

The solution to the problem is then the first position greater than the first at which data equals 0:

 

which are the first few terms of sequence A014778 in the On-Line Encyclopedia of Integer Sequences.

 

Checking by hand confirms that the numbers from 1 to 199981 contain a total of 199981 1s:

 

18. What is the coolest hack you've ever written?

 

While there is no "correct" answer, a nice hack for solving the first problem in the SIAM hundred-dollar, hundred-digit challenge can be achieved by converting the limit into the strongly divergent series:

 

and then using Mathematica's numerical function SequenceLimit to trivially get the correct answer (to six digits),

 

You must tweak parameters a bit or write your own sequence limit to get all 10 digits.

 

[Other hacks are left to the reader.]

 

19. 'Tis known in refined company, that choosing K things out of N can be done in ways as many as choosing N minus K from N: I pick K, you the remaining.

 

This simply states the binomial coefficient identity .

 

Find though a cooler bijection, where you show a knack uncanny, of making your choices contain all K of mine. Oh, for pedantry: let K be no more than half N.

 

'Tis more problematic to disentangle semantic meaning precise from the this paragraph of verbiage peculiar.

 

20. What number comes next in the sequence: 10, 9, 60, 90, 70, 66, ?

 

A) 96

B) 1000000000000000000000000000000000\

0000000000000000000000000000000000\

000000000000000000000000000000000

C) Either of the above

D) None of the above

 

This can be looked up and found to be sequence A052196 in the On-Line Encyclopedia of Integer Sequences, which gives the largest positive integer whose English name has n letters. For example, the first few terms are ten, nine, sixty, ninety, seventy, sixty-six, ninety-six, ?. A more correct sequence might be ten, nine, sixty, googol, seventy, sixty-six, ninety-six, googolplex. And also note, incidentally, that the correct spelling of the mathematical term " googol" differs from the name of the company that made up this aptitude test.

 

The first few can be computed using the NumberName function in Eric Weisstein's MathWorld packages:

 

A mathematical solution could also be found by fitting a Lagrange interpolating polynomial to the six known terms and extrapolating:

 

21. In 29 words or fewer, describe what you would strive to accomplish if you worked at Google Labs.

 

[This exercise is left to the reader.]

 Click to download more papers