Complete GLAT Solutions
I used to have an extremely long post containing the full GLAT solutions, but it was on the old blog and I never fully migrated. Well, now’s the time. For those who don’t remember, the GLAT was the Google Labs Aptitude Test that Google mailed to a number of institutions and placed in a lot of magazine ads to try and recruit some bright individuals. I took it, and with my own brains and Google figured out most of the problems. So, either read on, or download the glat solutions (doc)!
- A lot of you have probably already seen the Google Labs Aptitude Test and puzzled over the solution to problem number 1, which reads:
Solve this cryptic equation, realizing of course that values for M and E could be interchanged. No leading zeros are allowed. WWWDOT - GOOGLE = DOTCOM
The obvious solution is to run an exhaustive search of the digit space {0, 9} choosing permutations of 8 digits. That will definitely get you the answer, but is it fun? Nah, not at all. Why not try something a little more … interesting. A little more unique. A little more random!
My solution this problem was coded in C#.NET. It takes random permutations of an array of 8 integers, and tests it until a solution to the equation is found.In theory, this might never terminate, and it doesn't satisfy the problem in a formal sense, but it does allow me to find the answer. And, as time increases, the probability of finding the solution increases, because the chance of not pulling that particular permutation becomes more improbable as you exhaust the rest of the problem space. Here's the C#.NET code:
// Initialize digits array
int [] ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
ArrayList s = new ArrayList();
for(int q = 0; q < ints.Length; q++) {
s.Add(ints[q]);
}// Initialize local variables
System.Random r = new Random();
ArrayList newS = new ArrayList();
int w,d,o,t,g,l,e,c,m;while(true) {
// Get 9 digits randomly
while(newS.Count < 9) {
int index = r.Next(0, s.Count - 1);
newS.Add(s[index]);
s.RemoveAt(index);
}
// See if they match the formula
w = (int) newS[0];
d = (int) newS[1];
o = (int) newS[2];
t = (int) newS[3];
g = (int) newS[4];
l = (int) newS[5];
e = (int) newS[6];
c = (int) newS[7];
m = (int) newS[8];
int wwwdot = System.Int32.Parse(""+w+w+w+d+o+t);
int google = System.Int32.Parse(""+g+o+o+g+l+e);
int dotcom = System.Int32.Parse(""+d+o+t+c+o+m);if(wwwdot - google == dotcom && w != 0 && g != 0 && d != 0) {
Console.WriteLine(wwwdot + "n"+google+"n"+dotcom+"n");
}// Restore the digits container
for(int i = 0; i < newS.Count; i++) {
s.Add(newS[i]); newS.RemoveAt(i);
}
}Which produces the following solution to the Google Labs Aptitude Test (GLAT) problem 1: WWWDOT: 777589 GOOGLE: -188103 DOTCOM: =589486
- GLAT Question 2: "Write a Haiku describing possible methods for predicting search traffic seasonality:"
Summer in Athens, Winter toys for little boys: Whatever… whenever…
- GLAT Question 3: "1, 11, 21, 1211, 111221. What is the next line?"
312211, that is, three ones, two twos, and one one.
- GLAT Question 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 about. What dost thou do?"
- Wander aimlessly, bumping into obstacles until you are eaten by a grue.
- Use the laptop as a digging device to tunnel to the next level.
- Play MPoRPG until the battery dies along with your hopes.
- Use the computer to map the nodes of the maze and and discover an exit path.
- Email your resume to Google, tell the lead gnome you quit and find yourself in a whole different world.
- GLAT Question 5: "What's broken with Unix? How would you fix it?"
As the court case with SCO shows, Unix copyright and licensing is an extremely complicated topic. It is hard for a major consumer to want to use your Unix product on a large scale if they have any doubts about its legality! Therefore, a total code audit and vetting process needs to take place, copyright infringing code, if any, removed, and Unix (whichever flavour) recertified and rebranded under a new name with a solid reputation. Technical and usability considerations can then be improved. You can't fix what no one will touch.
- GLAT Question 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:"
- Fawn obsequiously and ask if you can have an autograph.
- Sit perfectly still and use only soft keystrokes to avoid disturbing her concentration.
- Leave her daily offerings of granola and English toffee from the food bins.
- Quote your favorite formula from the textbook and explain how it's now your mantra.
- Show her how example 17b could have been solved with 34 fewer lines of code.
- GLAT Question 7: "Which of the following expresses Google's over-arching philosophy?"
- "I'm feeling lucky"
- "Don't be evil"
- "Oh, I already fixed that"
- "You should never be more than 50 feet from food"
- All of the above
- GLAT Question 8: "How many ways can you color an icosahedron with one of three colors on each face?"
If this is a classical tiling problem, there are 144 ways to tile an icosahedron (Ball and Coxeter 1987, pp. 239-242). Taking off the restriction for adjacent colorings, there are 58130055 colorings. Of course, if the icosahedron is asymmetric, then there are 3^20 colorings.
"What colors would you choose?"
Sky Blue, #589CFF
Grey-Green, #9EB69F
Dusky Orange, #FFC22E
- GLAT Question 9: "This space intentionally blank. Please fill it with something that improves on emptiness."
While it's tempting to either leave it blank or fill the space with the notes to the E-spanish-gypsy scale, I drew a little schematic of life, the universe.
- GLAT Question 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?"
See this paper and this application of Greene's theorem to the problem to get 4/pi - 1/2.
- GLAT Question 11: "It's 2 PM 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?"
Pack up the car, drive to the beach, and play with the ocean until I get distract by a tidepool's wonders.
- GLAT Question 12: "In your opinion, what is the most beautiful math equation ever derived?"
A^T * A * x'= A^T * b
- GLAT Question 13: "Which of the following is NOT an actual interest group formed by Google employees?"
- Women's basketball
- Buffy fans
- Cricketeers
- Nobel winners
- Wine club
- GLAT Question 14: "What will be the next great improvement in search technology?"
Pervasive real-time portable searching. Any person, in any circumstance–be it a quiet boardroom or a noisy NY avenue–should be able to invoke a WWW search. Once search becomes as deep-rooted as breath it will cease to be an internet service and become a public necessity. When search is a necessity, then anything will possible, as it will moderate invidual access to global information, or route indvidual to individual information exchange. Personal search is the next revolution.
- GLAT Question 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?"
- 1
- 3
- 5 (reference)
- 11
- 24
- GLAT Question 16: "Given a triangle ABC, how would you use only a compass and a straight edge to find a point P such that triangles ABP, ACP, and BCP have equal perimeters? (Assume ABC is constructed so that a solution does exist)"
We are looking for theIsoperimetric (Equal Perimeter) point. Draw a circle around C of radius (a+b-c)/2. This makes it easy to draw circles around A and B which are tangent to C. You have three small circles–now draw a final circle outside and tangent to circles A, B, C. The center of this circle is P. This is also known as Apollonius' problem.
- GLAT Question 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?"
A smart alec would write f(0)=0 due to the loose wording of the problem, but the answer is actually f(199981) = 199981. This can be computed in linear time with the following algorithm (written in C#.NET)
static void Main(string[] args) {
int n = 2;
int cache = 1;
bool found = false;
while(!found){
cache = countOnes(n, cache);
if(cache == n)
found = true;
else
n++;
}Console.WriteLine(n+" has "+n+" ones in decimal.");
Console.ReadLine();
}
public staticint countOnes(int n, int cache) {
int ones = 0;
int temp = n;
while(temp != 0) {
if(temp % 10 == 1)
ones++;
temp = temp / 10;
}
return cache + ones;
}
- GLAT Question 18: "What's the coolest hack you've ever written?"
A special breed of carry-lookahead adder. The CLA block were slower than expected, so I split it into three 16 bit parallel adders and selected the upper 16 bits based on the carry out of the first stage. This got our adder into the 4-5ns range, twice as fast as before.
- GLAT Question 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. 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."
This question starts by stating the binomail coefficient identity (n, k) = (n, n-k). An identity which solves the problem is (n-1, k-1) + (n-1, k) = (n, k). Or, in words, "I pick k-1, you pick k."
- GLAT Question 20: "What number comes next in the sequence: 10, 9, 60, 90, 70, 66, ?"
- 96. This is integer sequence A052196
- 10^100
- Either of the above
- None of the above
- GLAT Question 21: "In 29 words or fewer, describe what you would strive to accomplish if you worked at Google Labs."
To group disparate data from Google's massive services databases into relevant, mixed aggregates. Or, to meld all forms of search together.
| This entry was posted on Thursday, January 20th, 2005 at 12:24 am and is tagged with random permutations, google labs, aptitude test, bright individuals, solution increases, formal sense, problem space, google, exhaustive search, magazine ads, permutation, integers, zeros, digits, brains, probability, array, lt, variables, nbsp. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback. |
25 Responses to “Complete GLAT Solutions”
Leave a Reply
Is answer to first question (WWWDOT - GOOGLE = DOTCOM) correct? You have not tok in consideration that values for E and M could be interchanged. Doesn’t this mean that E = M?
I had a consideration for E and M in some earlier version and found in practice that it didn’t do much to direct the search. It doesn’t mean that E = M, but simply that they can be exchanged without ruining the equation.
I just caught up on COMS482 and I realized that the code I used for the solution to number 17 of the GLAT is an example of Dynamic Programming, to turn what would be an O(n^2) problem into an O(n) problem. Very cool! I am now impressed with myself……
I used plain old fashioned logic to solve #1 and I got two answers. I don’t know too much programming, but I like puzzles.
177104
378274
———
555378
and of course your answer as well
Aristotle would be proud of me!
forgot to leave my name to the above comment!
My answer to question #4 was 5. First of all, this question looks kind of stupid, so I interept it in a different way:
You have a lot of projects/tasks (twisty little passages) in your current job (the maze). Your boss and supervisors (gnomes) are giving you a hard time. So what will you do?
The answer is to say goodbye to your boss and find a new job in Google Lab.
Your answer to number 19 doesn’t actually give the “cooler” bijection, so you haven’t really answered the question. The identity you mention can indeed prove that (n, k) = (n, n-k), but you need to explicitly give the correspondance between subsets of size k and containing subsets of size n-k. Also, the identity you used doesn’t require that k be no more than half of n (as stated in the question).
Let’s see if u geniouses (he he i mispelled that) can figure this out.
————————————————————————————–
I’m thinking of a 6-digit number. The sum of the digits is 43. And only two of the following three statements about the number are true: (1) it’s a square number. (2) it’s a cube number, and (3) the number is under 500000.
Response to Annas
Only Statements 1 and 3 are true.
the number is 499849.
707^2 = 499849
499849<500000
There are actaully 25 “solutions” to #1. Using a rather boring program I substitued numbers for every possible solution. Which one is correct? That I can’t say but here they are:
C,D, E, G, L, M,O, T,W
0, 2, 1, 2, 0, 1, 2, 2, 4
0, 2, 4, 2, 0, 4, 7, 8, 5
0, 4, 2, 4, 0, 2, 4, 4, 8
2, 3, 1, 1, 0, 1, 2, 2, 4
2, 3, 4, 1, 0, 4, 7, 8, 5
2, 5, 2, 3, 0, 2, 4, 4, 8
4, 6, 2, 2, 0, 2, 4, 4, 8
6, 1, 1, 5, 0, 1, 3, 2, 6
6, 1, 4, 5, 0, 4, 8, 8, 7
6, 7, 2, 1, 0, 2, 4, 4, 8
8, 2, 1, 4, 0, 1, 3, 2, 6
8, 2, 4, 4, 0, 4, 8, 8, 7
1, 3, 6, 1, 9, 6, 2, 2, 4
1, 3, 9, 1, 9, 9, 7, 8, 5
1, 5, 7, 3, 9, 7, 4, 4, 8
3, 6, 7, 2, 9, 7, 4, 4, 8
5, 1, 6, 5, 9, 6, 3, 2, 6
5, 1, 9, 5, 9, 9, 8, 8, 7
5, 7, 7, 1, 9, 7, 4, 4, 8
7, 2, 6, 4, 9, 6, 3, 2, 6
7, 2, 9, 4, 9, 9, 8, 8, 7
9, 1, 5, 1, 9, 5, 1, 0, 2
9, 1, 8, 1, 9, 8, 6, 6, 3
9, 3, 6, 3, 9, 6, 3, 2, 6
9, 3, 9, 3, 9, 9, 8, 8, 7
Thank you for posting the GLAT with solutions. I was searching it for many weeks!
On the triangle problem, you left out the crucial step.
How to find the circle that is tangent to the other 3?
Hi There,
We are trying to compile a series of aptitude tests for students (actually most of them are already bankers and investment bankers) in the area of Financial Engineering (see our Financial Engineering Aptitude Test (FEAT) on our web site http://www.risklatte.com - this is our own proprietary name)
We would be grateful if you could contribute some quantiative - math and statistics related - questions to our database of questions. Will highly appreciate it and shall give you the due credit and recognition.
Please let me know.
Regards,
Rahul
HTTP DOWNLOAD of Windows Vista build 5270: http://windows.czweb.org/491_HTTP_DOWNLOAD_of_Windows_Vista_build_5270
[...] It’s really hard to correct my “Error in entering captcha” when there’s not a visible captcha to fill out. I can’t correct this item to submit my comment on their GLAT story because there’s nothing to fix. And so I resort to writing it down here: Interesting. They quote my year-old post (elliottback.com/wp/archives/2005/01/20/complete-glat-solutions/) on that matter at least twice in the article, which is annoying split onto multiple pages. Then again, I like their formatting better ^_^; [...]
Hi Elliot
Just curious to know why dont u appear for GLAT and join Google?
Cheers
Vishal
this is stupid. half of these answers are answers about your personality, if you knew anything about google’s ethos you’d understand that probably 90% of these answers are opinionated and the final ten percent may be right mathematically, I don’t think they’re really the point Google’s trying to get at in making this aptitude test.
All I can say about this solutions thing is that it’s entierely and utterly idiotic and that the GLAT means something completely different from what is mirrored here.
The explanation of the answer to GLAT Question 20 is plain wrong. Its not 96 cos its just an integer sequence but because of the fact that its the largest integer that can be spelt using 9 letters
The answer to question 2 is wrong;
the sequence is a fibonacci sequence where you add up the numbers in each row.
the first row is 1
row 2 is 2
row 3 is 3
row 4 is 5
row 5 is 8
so the next row should sum up to 13; but ur answer does not.
instead the answer is 1212112111
hint* try writing row 2 and row 3 alternativley,. and then reverse it which is row 4;
similarly row 3 and row 4 can be alternativly written and reversed to get row five; so row 4 and row 5 is used alternativly and reversed;
good test,it can shape the trends of interviews in the third world countries where nepotism seems to be an order of the day
[...] Cominciate dalla pagina 1, continuate alla 2 e concludete anche la 3^ parte: e non fate i furbi! Anche se la raccolta completa delle soluzioni è facilmente trovabile online, siate onesti e non copiate! [...]
[...] Thú thật là những câu hỏi này làm tôi “khó chịu” và thú vị hơn so với của Microsoft. Bác nào bí thì có thể tham khảo câu trả lời ở đây hay đây. [...]
its very useful and wonderful
I agree to what circle said that Q3. but the answer shall be “2111121211″
Select the max. no. of digits from right that can be selescted depending on the above values of the series.
Ex
F(1)->11
F(11)->21
F(21)->F(2)+11->12+11 this tells F(2)=12
1211->F(1)+F(2)+F(11) AS 11 APPEARED EARLIER BUT 12 DIDN’T SO BREAK 12 TO 1&2.
F(12)=1112
F(1211)->11+12+21=111221
SO NEXT SHALL BE
F(111221)->F(1112)+F(21)
F(1112)=F(11)+F(12)=211112
THIS GIVES 2111121211 sum 13(also complies with fibonaci)
Also chk the next one
F(2111121211)=F(211112)+F(1211)
F(211112)=F(21)+F(1112)=1211211112
F(2111121211)=1211211112+111221
F(2111121211)=1211211112111221 SUM(21=13+8) (THIS ONE JUST TO PROVE)
and ya thanx to the one who compiled all this solution of glat it is of great help
The answer to #20 is actually C. The reason? 10 to the 100th power is “one googol”, which, coincidentally, has nine letters. However, “googol” isn't a widely used term, so it could also be 96.
Hence, C.