My Google Interview, Part 1

Google has a famous (infamous?) hiring process: long waits, weird questions, or so I heard. My experience was markedly different. Someone put me in touch with Google HR, I sent my CV, and I almost immediately heard back. Later that week I had my initial phone screen, which went really well. The following day she asked when I would be available for a phone interview. I gave her some inconvenient times this week, and said anytime next week. From this point onward, I was actually putting them off. I knew it was going to be a tough technical interview, and I wanted time to study.

Some of the books I studied:

The Art of Computer Programming (Knuth), volume 1, sections 1.1-1.3, working all the exercises, for a math and algorithm refresher.

Introduction to Algorithms, the canonical college textbook.

The Practice of Programming (Kernighan and Pike), an excellent book.

Sun Certification guides for Java and JEE.

Design Patterns in Java, Core J2EE Patterns, and the Gang of Four book.

Effective Java, if you are a Java programmer and have not read this book, read it now.

The "Fielding Dissertation" on the REST interface and other ACM/IEEE technical papers.

...and many others! For the next 2 weeks it looked like a library exploded in my house.

Phone interview came and went great. It was given by a Dutch engineer who's job at Google is to classify pornography. The questions were challenging and tested my knowledge of algorithms, Java, and problem-solving. Mostly centered around search, sort, and general programming practice, he seemed impressed when I answered one question with an "except when..." and pulled out a bit of trivia on how the JVM deals with pointers to arrays of primitive types in a pass-by-value scenario. Ha! The guy is quizzing me and he had to look something up.

Two days later I was invited for an on-site interview.

Again, I gave them the, "Well this week is booked but how about next week" stall to give me still more time to study. They were merciful and scheduled it for Friday.

About this time, I'm feeling really special. I sent an email to my friends, one of whom had already interviewed at Google, which led to the following exchange.

From: Tom Wilson to Charles, Elana, Lori, Alex

Sep 19

I got an on-site interview (with Google) scheduled for next Friday.

Yay!

-tom
---

From: Elana Silver

Sep 19

Make sure to figure how how many pandas can fit on a cruise liner before you get there. Also, how many prime numbers there are between 17 and 775.

Congrats!

From: Tom Wilson to Elana

7:55 PM

Good idea!

1.
google search: cruise liner deadweight tonnage
10,000 tons at 100 cu ft/ton = 1,000,000 cu ft of cargo space.

google search: panda transport cage size
45cm x 40 cm x 45 cm (red panda)
= 1.48ft x 1.31ft x 1.48ft = 2.87 cu ft

1,000,000 cu ft / 2.87 cu ft

= 348,000 pandas.


2.
That would be 131 prime numbers. Algorithm follows.

static public ArrayList getPrimes(Integer lowerBound, 
      Integer upperBound) {
   int i, j, notPrime;
   int[] n = new int[upperBound - lowerBound + 1];
   // list all numbers
   for (i = lowerBound; i <= upperBound; i++) { 
      n[i - lowerBound] = i; 
   } 
   // remove non-primes 
   for (i = 2; i <= upperBound / 2; i++) { 
      j = 2; 
      while ((notPrime = i * j++) <= upperBound) { 
         if (notPrime >= lowerBound)
            n[notPrime - lowerBound] = 0;
      }
   }
   // put remaining numbers in a list
   ArrayList primeNumbers = new ArrayList();
   for (i = lowerBound; i < upperBound; i++) {
      if (n[i-lowerBound] != 0)
         ArrayList.add(n[i-lowerBound]);
   }
   return primeNumbers;
}