Friday, September 24, 2004

GLAT

If you subscribe to "Physics Today" or MIT's "Technology Review" you would have seen that Google started an innovative way to recruit people for their lab jobs.They issued a booklet containing questions.Think you have the brains to work with these super smart people working on cutting edge technologies.Try wrestlingwith these questions :

1. Solve this cryptic equation, realizing of course that values for M andE could be interchanged. No leading zeroes are allowed.WWWDOT - GOOGLE = DOTCOM

2.Write a haiku describing possible methods for predicting searchtraffic seasonality.
(A haiku is a short poem, usually having three lines and seventeen syllables (five syllables on line 1, seven on line 2, and five on line 3)

3.What's the next line?
1 1
1 2
1 1 2 1
1 1 1 1 2 2 1

4.You are in a maze of twisty little passages, all alike. There is adusty laptop here with a weak wireless connection. There are dull,lifeless gnomes strolling about. 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 findyourself in a whole different world

5.What's broken with Unix? How would you fix it?

6.On your first day at Google, you discover that your cubicle mate wrotethe textbook you used as a primary resource in your first year ofgraduate school. Do you:
A) Fawn obsequiously and ask if you can have an autograph.
B) Sit perfectly still and use only soft keystrokes to avoiddisturbing 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'snow your mantra.
E) Show her how example 17b could have been solved with 34 fewer lines of code.

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

8.How many different ways can you color an icosahedron with one of three colors on each face?
(ote: "An icosahedron is not-necessarily a regular 20-facedpolyhedron! Examples include the regular icosahedron, Jessen'sorthogonal icosahedron, rhombic icosahedron, 18-sided prism, 19-sidedpyramid, or 10-sided dipyramid..." am I a geek?.)
What colors would you choose?

9.This space is intentionally blank. Please fill it with something thatimproves upon emptiness.
-------------------------------------------------



--------------------------------------------------

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

11.It's 2pm on a sunny Sunday afternoon in the Bay Area. You're minutesfrom the Pacific Ocean, redwood forest hiking trails and world classcultural attractions. What do you do?

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

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

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

15. What is the optimal size of a project team, above which additionalmembers do not contribute productivity equivalent to the percentageincrease in the staff size?
A) 1
B) 3
C) 5
D) 11
E) 24

16.Given a triangle ABC, how would you use only a compass and straightedge to find a point P such that triangles ABP, ACP, and BCP haveequal perimeters? (Assume that ABC is constructed so that a solutiondoes exist.)

17.What's the coolest hack you've ever written?

18.'Tis known in refined company, that choosing K things out of N can bedone in ways as many as choosing N minus K from N: I pick K, you the remaining.
Find through 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.

19.What number comes next in the sequence: 10, 9, 60, 90, 70, 66, ?
A) 96
B) 10 to the 100th power
C) Either of the above
D) None of the above

20.In 29 words or fewer, describe what you would strive to accomplish ifyou worked at Google Labs.
--------------------------

If you do answer this then you can expect an email in the following format :

"Dear Problem Solver,

Thanks for taking the time to play with our little brain-teaser and forsending us your solution. While you won't find a confirmation of theanswer in this email, we did want to let you know that your message wasreceived 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 theremight be a fit with a position we have open, we'll contact you within thenext few days.

And as for the answer to the puzzle, we'll post the ads and the solutionon our site within a couple of months, after those who are a little slowerthan you have had a chance to work on it a bit longer.

Thanks again foryour interest in Google.

The Google Labs Engineering Team"

6 comments:

Anonymous said...

To the questions of interest to me.

> Solve this cryptic equation, realizing of course that values for M and
> E could be interchanged. No leading zeroes are allowed.
> WWWDOT - GOOGLE = DOTCOM

777589 - 188103 = 589486

>
> What's the next line?
> 1
> 1 1
> 2 1
> 1 2 1 1
> 1 1 1 2 2 1

3 1 2 2 1 1

> How many different ways can you color an icosahedron with one of three
> colors on each face?
>
> (editor's note: "An icosahedron is not-necessarily a regular 20-faced
> polyhedron! Examples include the regular icosahedron, Jessen's
> orthogonal icosahedron, rhombic icosahedron, 18-sided prism, 19-sided
> pyramid, or 10-sided dipyramid..." Jiminy crickets, am I a geek...)

Hell. Yet to find.


> 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?

Infinite.

> 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.)

Find the mid points of each side, by joining the intersecting points
of the arcs drawn with lengths as of the side from both end points of
that side on both sides of the side. Join the vertices with the mid
point of opposite sides to get the center of the triangle. That is P.
I strongly doubt if it works for obtuse angle triangle and lazy enough
to verify it.

>
> 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?

I dont think there is one.

> '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.
>
> Find though a cooler bijection, where you show a knack uncanny, of
> making your choises contain all K of mine. Oh, for pedantry: let K be
> no more than half N.

Damn it! Only if I could understand the question.

>
> What number comes next in the sequence: 10, 9, 60, 90, 70, 66, ?
> A) 96
> B) 10 to the 100th power
> C) Either of the above
> D) None of the above

A) 96

Anonymous said...

Correction to f(n) = n problem. Ofcourse this is the very question that appeared in your mail but surprisingly dropped out from this post.

Anyway, I came to a hasty conclusion that it doesn't have a solution. But a rough analysis showed that there is a number less than 10^10 that satisfies this equation. And driven by easy patterns, I made a wild guess that the answer is 987654321.

There seemed something wrong with that. After a while, a closer look, when I picked up a detail that I missed earlier, showed that there is a number less than 2*(10^5) that satisfes this equation. A little more effort revealed that the number is 199981. Now I can wipe out any guilt of doing injustice to this problem from my mind, until someone points out that it still is not right.

Anonymous said...

Damn it. Forgot, one more correction to the triangle ABC problem. The solution should read.

Draw perpendicular lines for each side through their mid points, by joining the intersecting points of the arcs drawn with lengths of the side from both end points of that side on both sides of the side. The intersection point of the three perpendiculars is the center of the triangle. That is P.

Anonymous said...

Aha! After a three day struggle finally I hope I found the solution to the icosahedron problem.

The answer is 174342216 different colored icosaherons.

I think its right. Even otherwise I am fucking orgasmic right now, which can only happen in an intercourse with mathematics.

Anonymous said...

Damn! That was a premature ejaculation. I was chasing flat landers while I should have raised to sphere land.

The answer for icosahedron problem is not 174342216 as was mentioned in the earlier post (This is the answer for a fixed polygon with 20 vertices).

The correct answer for icosahedron is 9099.

I should be careful in my future copulations with math.

Anonymous said...

An apology for yet another mistake in the series of errors made by me against the icosahedron. The correct answer is 58130055, as was rightly pointed out by my friend, incidentally who happens to be the poster of this post. The earlier answer 9099 is correct only if you are short of paint and painting only the vertices and not the faces of the icosahedron.

Any way, coming to the picks of the refined company;

A raw explanation:

Given, (N-K) > K
(N)c(K) = (N)c(N-K)

Number of your choices = (N)c(K)
Number of my choices = (N)c(N-K)

Number of elements in each of your choices is K.
Number of elements in each of my choices is (N-K).

Part A (For each of your choice how many of mine have same elements)
----------------------------------------------------------------------
Take one element from your set of choices, Say X.
Fix the first K elements of my choices with the elements of X,
There are (N-K-K) slots to be filled with the remaining (N-K) elements, which can be filled in (N-K)c(N-K-K) ways.
Hence (N-K)c(N-2K) of my choices have the same elements as each choice, X of yours.

Part B (How many of your choices are made up of subsets of each of my chioces)
-----------------------------------------------------------------------------
Take one element from my set of choices, Say Y.
K elements can be choosen from the (N-K) elements of Y in (N-K)c(K) ways.
Hence (N-K)c(K) of your choices are made up of subsets of each choice, Y of mine.

Summary
-------
Each of your choice is a subset of (N-K)c(N-2K) choices of mine.
Each of my choice is a superset of (N-K)c(K) choices of yours.

Since (N-K)c(N-2K) = (N-K)c(K),
Each of your choices maps to as many choices of mine as each of mine maps to that of yours. Also as (N-K) > K each of my choice will contain all elements of your mapped choice. A one-one mapping between your and my choices can hence be established.