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

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

2. GLAT Question 2: "Write a Haiku describing possible methods for predicting search traffic seasonality:"

       Summer in Athens, Winter toys for little boys: Whatever… whenever…
    

3. GLAT Question 3: "1, 11, 21, 1211, 111221. What is the next line?"

       312211, that is, three ones, two twos, and one one.
    

4. 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?"
    
   1. Wander aimlessly, bumping into obstacles until you are eaten by a grue.
   2. Use the laptop as a digging device to tunnel to the next level.
   3. Play MPoRPG until the battery dies along with your hopes.
   4. Use the computer to map the nodes of the maze and and discover an exit path.
   5. Email your resume to Google, tell the lead gnome you quit and find yourself in a whole different world.

    

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

6. 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:"
    
   1. Fawn obsequiously and ask if you can have an autograph.
   2. Sit perfectly still and use only soft keystrokes to avoid disturbing her concentration.
   3. Leave her daily offerings of granola and English toffee from the food bins.
   4. Quote your favorite formula from the textbook and explain how it's now your mantra.
   5. Show her how example 17b could have been solved with 34 fewer lines of code.
       
7. GLAT Question 7: "Which of the following expresses Google's over-arching philosophy?"
    
   1. "I'm feeling lucky"
   2. "Don't be evil"
   3. "Oh, I already fixed that"
   4. "You should never be more than 50 feet from food"
   5. All of the above
       
8. 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
    

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

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

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

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

    A^T * A * x'= A^T * b
     

13. GLAT Question 13: "Which of the following is NOT an actual interest group formed by Google employees?"
     
    1. Women's basketball
    2. Buffy fans
    3. Cricketeers
    4. Nobel winners
    5. Wine club
        
14. 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.
     

15. 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. 1
    2. 3
    3. 5 (reference)
    4. 11
    5. 24
        
16. 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.
     

17. 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;
    }
     

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

19. 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."
     

20. GLAT Question 20: "What number comes next in the sequence: 10, 9, 60, 90, 70, 66, ?"
     
    1. 96. This is integer sequence A052196
    2. 10^100
    3. Either of the above
    4. None of the above
        
21. 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.

27 Responses to “Complete GLAT Solutions”

1. Tarun Agrawal says:

   6/26/2010 at 2:39 am

   Hi

   Just curious to know why dont u appear for GLAT and join Google?

   Reply