Interesting Google Videos

Here are some interesting videos that Google has produced:

How to Break Web Software

Mondrian Code Review on the Web

BigTable: A Distributed Structured Storage System

Cluster Computing and MapReduce

Java Interview Preparation

I spent close to 40 hours studying for the Google onsite interview. Here's an outline of the material I studied and how relevant it ended up being to the actual interview:

• TopCoder Algorithms Tutorials. I worked through all of these and practiced at least a couple problems related to each article. I wasn't asked any geometry problems but also hadn't mention any graphics experience on my resume. However, there was a coding question involving a greedy algorithm and another requiring depth-first search. For some code solutions, the interviewer asked for the big-O time complexity.
• Wu:Riddles CS Forum. This ended up being very important! I worked through the entire forum, paying special attention to problems that looked especially interview worthy. Going through this forum was much more effective than practicing TopCoder problems. A lot of interview material was related to topics discussed on this forum.
• Wu:Riddles in general. This is one of the best collections of classic riddles and puzzles on the web. I didn't get any interview questions that were riddle-like, but if there had been any, this web site almost certainly would either have had the exact riddle or something very similar to it. Maybe that's why they don't use riddles much any more. But solving riddles seems to be a good way to keep the creative side of problem solving sharp, and it's also a nice break from textbook study.
  
• CLR Algorithms book. I wanted to have solid preparation on algorithms and especially to be able to give textbook examples of each kind of algorithm -- e.g. problems solvable with gredy algorithms, problems that benefit from dynamic programming, how hash tables work, etc. I wasn't directly asked for examples, but knowing them did help recognize what algorithms may apply to a coding problem. Of course, I didn't have time to study the entire book, so my focus was on topics that appeared in the TopCoder tutorials and the Wu:Riddles forum.
  
• Wikipedia pages on algorithms, sorting, big O notation, and the pigeon hole principle. For me, these were a gentler intro before getting into CLR. Studying the Wikipedia pages would probably have been enough preparation, but for me diving into CLR and going deeper than necessary was a way to ensure the fundamentals were really solid.
  
• Design Patterns book. The most important part to know was the first chapter. The questions I was asked were cleverly aimed to probe for experience in using design patterns. We talked about what patterns are, why they're important, when to use them, when not to use them (a good answer shows experience), how to decide what patterns to use and not to use, etc. That part of the interview basically involved giving a 5-minute synopsis of Chapter 1, plus a few design stories to illustrate key points. I had prepared a list of JDK examples of each pattern to talk about, but was asked more about patterns I've used or avoided in my own code.
  
• Effective Java book. I read the whole thing and typed up a study sheet for each item heading, including bullets for any sentences that were in boldface. I also had stories of real-world design experiences where going against the advice of the book ended up being critical to success. The interviewer seemed to like those stories.
• Refactoring book. My resume had specific items about refactoring experience, and one interviewer did ask a lot of questions about it. Chapers 2-4 were the most important to know, especially describing what forces affect the decision of whether to refactor or not to refactor, listing what code smells were most common by my experience, identifying key techniques for successful refactoring, etc.

Below are some other hints I collected from the web and other people who've interviewed at tech companies (not necessarily at Google):

• How do ArrayList, HashMap, LinkedList, and HashSet work and what are their big-O time and space complexities?
  
• Can you take a while or for loop and wrap it inside a java.util.Iterator implementation?
• How do you use the synchronized keyword together with wait() and notify()/notifyAll()?
  
• Bit manipulation tricks
  
• Coding on a whiteboard is effective in an interview for a few reasons.
• It shows whether you know the language well enough to be productive without an IDE.
• It really exposes how clear your thinking is, especially how close you are to the final solution on the first try.
  
• It shows how good you are at stepping through your own code. Are you systematic and careful? Or ad hoc and rushed?
  
• Java language keywords/constructs and their edge cases -- e.g. try-finally, static, checked vs. runtime exceptions, where classes can be declared, etc.
  
• What techniques do you use to maximize unit test coverage in your code? Have you experienced any situations where achieving a high level of unit test coverage was difficult? What made it difficult and what did/could you do to lessen the difficulty?
• You are investigating a bug, but when you try the reported steps, sometimes the bug occurs and sometimes it does not.
• In your experience, what are the most common reasons that a bug might be inconsistently reproducible? Come up with at least 5 types of causes and give an example of each.
  
• For each potential reason, what techniques would you use to identify the cause of the bug and its fix?
• Have you ever fixed a bug which you never actually observed directly? If yes, how were you able to locate the problem and fix it?
  

Permutations by Swapping Adjacent Pairs

References:
1) Counting and Listing All Permutations
2) An algorithm to list all the permutations

Known variously as the Steinhaus-Johnson-Trogger algorithm, the Johnson-Trotter algorithm, or the Steinhaus algorithm. Summarized in these steps:

Initialize the first permutation with <1 <2 ... <n
While there exists a mobile integer:

1. Find the largest mobile integer k.
2. Swap k and the adjacent integer it is looking at.
3. Reverse the direction of all integers larger than k.
   

To embody the traveling metaphor into action, the algorithm replaces integer as the basic element of the procedure with a structure that maintains an integer and a direction. Call the structure a directed integer, or just an integer if the context is clear. The direction may take on only one of two values, "left" or "right", and can be implemented as a boolean. It's convenient and certainly appropriate to say that a directed integer is looking left- or rightwards depending on the value of the attached field direction.

The algorithm requires one more definition: a directed integer is said to be mobile if it is greater than its immediate neighbor in the direction it is looking at.

Example output:

1 2 3 4
1 2 4 3
1 4 2 3
4 1 2 3
4 1 3 2
1 4 3 2
1 3 4 2
1 3 2 4
3 1 2 4
3 1 4 2
3 4 1 2
4 3 1 2
4 3 2 1
3 4 2 1
3 2 4 1
3 2 1 4
2 3 1 4
2 3 4 1
2 4 3 1
4 2 3 1
4 2 1 3
2 4 1 3
2 1 4 3
2 1 3 4

OO Design Methodologies

(From GoF Design Patterns, Section 1.6 "How Design Patterns Solve Design Problems")

Object-oriented design methodologies differ in their approaches:

1. Create classes and operations based on the nouns and verbs found in a written problem statement or specification.
   
2. Focus on collaborations and responsibilities. Use CRC Cards (from Kent Beck) as a design aid.
3. Translate real-world objects directly into object types and their behaviors into operations, known as the analysis model.
   

GoF says there will always be a disagreement on which approach is best, though the analysis model appears to be popular. However, the OO design still often ends up with classes that have no counterparts in the real world, so GoF warns:

Strict modeling of the real world leads to a system that reflects today's realities buyt not necessarily tomorrow's. The abstractions that emerge during design are key to making a design flexible. Design patterns help you identify less-obvious abstractions and the objects that can capture them.

For example: Design a chess system using object-oriented principles.

Coefficients of Binomial Expansion

Given a binomial of the form (x+y)ⁿ, where n >=1, write a function coefficients(int n) that prints out the coefficients of the binomial expansion in O(n) time. For example, calling coefficients(10) prints:

1 10 45 120 210 252 210 120 45 10 1

Solution

We start with the binomial theorem, which tells us that the coefficient for each term k (1 <= k <= n) is n!/(k!(n-k)!). Using coefficients(10) as an example, we can see that the term in position #1 has degree 10 and coefficient 1. The coefficient of the next term (#2 with degree 9) is:

  10!      10
------- = ----
 1!9!      1

The next term (#3 with degree 8) is:

  10!     10*9
------ = ------
 2!8!      1*2

And the next term (#4 with degree 7) is:

  10!     10*9*8
------ = --------
 3!7!      1*2*3

Notice the pattern unfolding: the coefficient for the term in position k is the ((coefficient*degree)/position) of the term in position k-1. So we can implement this quite efficiently:

public void coefficients(int n)
{
  int coeff = 1;
  int degree = n;
  int position = 1;
  do
  {
    System.out.print( coeff + " " );
    coeff = ( coeff * degree-- ) / position;
  } while ( position++ <= n );
  System.out.println();
}

Of course, this can be made even more efficient by exploiting the symmetry of the coefficients, but as it stands, this implementation runs in O(n) time.

A Coder and a Half

If a coder and a half write a module and a half in a day and a half, how many modules can 6 coders write in 7 days?

Solution

We know that 1½ coders write 1½ modules in 1½ days.
So 3 coders write 3 modules in 1½ days.
So 6 coders write 6 modules in 1½ days.
So 6 coders write 12 modules in 3 days.
So 6 coders write 24 modules in 6 days.
So 6 coders write 28 modules in 7 days.

The answer is 28 modules.

GoF Design Patterns

Motivation and Purpose

• Encapsulate internal state of objects.
• Distinguish intrinsic state from extrinsic state.
  
• Decompose a system into abstractions.
• Delegation works best when used in highly stylized ways (i.e. design patterns).
  
• Principles of reusable object-oriented design:
• Program to an interface, not an implementation. (Use loose coupling.)
  
• Favor object composition over class inheritance. (Use delegation.)
  
• Techniques for designing for change:
• Avoid dependency on type of implementation class.
• Avoid dependency on specific operation dispatch.
• Increase information hiding.
• Increase algorithm hiding.
• Decrease tight coupling; increase loose coupling.
• Increase flexibility by using object composition in general and delegation in particular instead of subclassing.
• Alter behavior of a library class without modifying the library.
  

Examples of design patterns in Java:

Creational Patterns

• Abstract Factory -- BorderFactory, Collections, org.w3c.dom.Document (create methods)
  
• Builder -- StringBuilder, ProcessBuilder
  
• Factory Method -- URLStreamHandlerFactory, InitialContextFactory
  
• Prototype -- (copyable state objects for supporting cancelable UI)
  
• Singleton -- java.lang.Runtime
  

Structural Patterns

• Adapter -- InputStreamReader, OutputStreamWriter
  
• Bridge -- Swing PLAF
  
• Composite -- java.awt.Component/Container
  
• Decorator -- BufferedReader/Writer, ZipInputStream, other java.io classes
  
• Facade -- what Swing is to java.awt.Graphics
  
• Flyweight -- Icon (when cached)
  
• Proxy -- RMI, WeakReference, ThreadLocal
  

Behavioral Patterns

• Chain of Responsibility -- KeyEvent dispatch in AWT/Swing (consume() method stops chain)
  
• Command -- javax.swing.Action (not quite - need a better example)
  
• Interpreter -- java.util.regex.Pattern
  
• Iterator
  
• Mediator -- event cascades
  
• Memento --javax.swing.undo.UndoableEdit, java.awt.datatransfer.Transferable, java.beans.XMLEncoder/Decoder
  
• Observer -- Swing/AWT event listeners
  
• State -- graphical tools (e.g. from a component palette) used in a visual editor
  
• Strategy -- dispatch of Undo; typical pattern for View-Controller interaction
  
• Template Method -- java.io.Reader/Writer
  
• Visitor -- SAX API (org.xml.sax)
  

Examples of the Pigeonhole Principle

From the Wikipedia article:

• You have a drawer with 10 black socks and 12 blue socks. Without looking in the drawer, how many socks do you need to pull out to get at least one pair of socks the same color?
• Show that there must be at least two people in London with the same number of hairs on their head.
• If there are N people (N >= 2) who can arbitrarily shake hands with one another, show that there are at least two people who shake the same number of hands.
• Show that there cannot be a lossless compression algorithm that will compress any file to a strictly smaller size.

Ties into probability theory:

• If 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon. For 5 pigeons and 10 holes, it's 69.76%. For 10 pigeons and 20 holes, it's 93.45%.
  
• Given a group of 23 randomly chosen people, there is more than a 50% chance that at least two of them will have the same birthday. For 60 or more people, the probability is greater than 99%. (Known as the Birthday Paradox)

Puzzles whose solutions use the pigeonhole pricniple:

• You have a chessboard with two diagonally opposite corners removed. Is it possible to cover the remaining board with domino pieces that are each two board squares in size?
• There are 500 boxes with apples, each containing no more than x apples. Find the maximal possible value of x , such that one can for sure find 3 boxes containing equal number of apples.
  
• Several math proofs using the pigeonhole principle.
• And some other interesting math problems on the PHP.
  

Clock Hands

An analog clock shows the time as 3:15. What is the angle between the hour and minute hands?

Solution

The hour hand will move 360 degrees in 12 hours, so that's 30 degrees per hour, which is 7.5 degrees per 15 minutes. So at 3:15, the hour hand is at 97.5 degrees when the minute hand is at 90 degrees. So the angle between them is 7.5 degrees.

Russian Roulette

You are forced to play a game of Russian roulette. The gun with six chambers is initially empty, and your comrade puts two bullets in the gun in adjacent chambers. He closes the barrel, spins it, and pulls the trigger. CLICK - the chamber was empty. Now he puts the gun to your head and will pull the trigger one more time. Which do you prefer - that the barrel first be spun again or that he just pull the trigger?

Solution

Your odds are better if he pulls the trigger without spinning again.

If the barrel is respun, you have a 2/3 (4 out of 6) chance of survival. However, you know that the gun was already triggered on an empty chamber. There are 4 empty chambers, and 3 of them are followed by another empty chamber; only 1 out of 4 is followed by a bullet. So, if the trigger is pulled without respinning, you have a 3/4 chance of survival.

Four Quarts

If you had an infinite supply of water and a 5 quart and 3 quart jug, how would you measure exactly 4 quarts?

Solution

1. Fill the 5Q jug.
2. Pour contents of 5Q jug to fill the 3Q jug. This leaves 2 quarts in the 5Q jug.
   
3. Empty the 3Q jug.
4. Pour remaining 2 quarts from the 5Q jug into the 3Q jug. There is 1 quart of space left in the 3Q jug.
   
5. Fill the 5Q jug.
6. Pour water from the 5Q jug into the 3Q jug until it is full.
7. The 5Q jug now has 4 quarts.

First Common Node in Intersecting Linked Lists

You have two singly linked lists, L1 and L2, which start from different head nodes. Some number of nodes into each list, they meet at a common node and share all the nodes from that point on. Describe an algorithm for finding the first common node.

Solution

The naive approach would be to start with the first node of L1 and check each node of L2 to see if it matches, iterating until a match is found. But of course, we can do better.

The key is that because L1 and L2 have a common "tail", you can just compare corresponding nodes between L1 and L2, walking down the lists in tandem, as long as they are the same distance from the tail end of the list. To get to that point, you first traverse L1 and L2 separately to determine their lengths. Then you skip over the first |L1-L2| nodes from the longer list, since those couldn't possibly be part of the common tail. Now you're looking at the same number of remaining nodes in both lists. Just walk down them together, checking corresponding nodes until the common one is found.

Sorting Algorithms Summary

• O(N²) in average and worst case; no extra memory required; stable.
  
• Bubble sort
• Uses about N²/2 comparisons and N²/2 exchanges on the average and in the worst case.
  
• Selection sort
• Find the smallest element in the array and exchange it with the element in the first position. Then repeat for 2nd, 3rd,...,nth positions.
  
• Uses about N²/2 comparisons and N exchanges.
  
• Each item is moved at most once.
• Method of choice for sorting files with very large records.
  
• Insertion sort
  
• Consider the elements one at a time, inserting each in its proper place among those already considered, keeping them sorted.
  
• Is linear for "almost sorted" files.
  
• Uses about N²/4 comparisons and N²/8 exchanges on the average; twice as many in the worst case.
• Uses sentinel value to avoid having extra boundary check in inner loop.