I applied for Google's new grad position, available September 1. They contacted me a few weeks later to set up a phone interview.

They gave me a list of categories to choose from, based on my specialization. I had to choose three from the following options:

• Advanced Algorithms
• Audio/video
• Billing/payment testing
• Compilers and software tools (linkers, debuggers, IDEs, etc.)
• Computer vision
• Concurrency, multi-threading, synchronization
• Database internals
• Distributed systems
• Embedded software and real-time systems
• Front end
• Graphics and imaging
• Information retrieval and data mining
• Internationalization
• Load and performance testing
• Mac and iPhone development
• Machine learning and AI
• Natural language processing
• Networking (TCP/IP and OSI stack)
• Object-oriented analysis and design
• Operating systems
• Production Systems
• Project Management
• QA
• Security and cryptography
• System administration
• Test automation
• UI design and implementation
• Web applications and multi-tiered systems
• Windows development
• Wireless applications

They also asked me to choose my top three programming languages.

PHONE INTERVIEW QUESTIONS:********

Based on my choices, I was expected to know certain concepts. As I chose the software side, my questions focused on:

1. Big-O and Algorithms
2. C++, Java, C#
3. System Design
4. Sorting
5. Hashtables
6. Trees
7. Graphs
8. Discrete Math
9. Operating Systems: processes, threads, and concurrency issues. I needed to know about locks and mutexes.

BOOKS RECOMMENDED (by Google):

1. Review of Basic Algorithms: Introduction to the Design and Analysis of Algorithms by Anany Levitin
2. Programming Interviews Exposed: Secrets to Landing Your Next Job (Programmer to Programmer) by John Mongan, Noah Suojanen, and Eric Giguere HIGHLY RECOMMENDED

Besides the questions listed, they also asked:

--Which would be better for situation X, Merge Sort or Quick Sort?

Write a function that finds the median of a set of three numbers. Also, find the Big O. Can it be done with only 2 comparisons, or do you need 3?

If you had a savings account with $1 at a 100% interest rate, at what year would you have $15 billion dollars?

When would you want to use a hash table over a binary search tree? What are the Big O's?

What IS Big O?

What happens if one resource is waiting on another resource to finish, but that same resource happens to be waiting on that other same resource?