Phone Interview with Google

I just had a phone interview with someone from Google. I'm quiet confident that it went well. Well enough at least to get me to the next step in whatever recruiting process they have. I had three questions; the first two were rather simple (if you are careful) and the third was an open-ended design question. All questions were about code and had to be answered with a description of the Java source necessary to solve them.

First question:
You have a textfile with integer numbers, one number on each line. Your task is to write a function that reads that file and sums up the numbers.

Here's what I believe I dictated over the phone:

private static int sumNumbersFromFile(String filename) throws IOException
{
  BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
  String s;
  int sum = 0;
  while ((s = in.readLine()) != null)
    sum += Integer.parseInt(s);
  return sum;
}


The follow-up questions concerned error conditions, what can go wrong and how that can be handled. I kind of messed that up, I didn't see the obvious problems. In retrospect, I should have said: file missing, file i/o errors, invalid numbers in the file (parseInt throws NumberFormatException), over-/underflow in sum. These should probably be propagated to the caller since we don't know what to do with them.

Btw. the reasoning for "private static" was that it would be a helper function in a class with a main function. I didn't have enough information and that's the easiest way to embed this method.

I just typed it in and it works. Btw. there's also the issue of charset. Could have mentioned that as well.

Second question:
Implement a function that calculates the fibonacci numbers.

This time I was better with error handling, I right away got it made clear that I should assume that the result fits into an int.

Here's what I believe I dictated over the phone:

public static int fib(int x)
{
  if (x <= 0) throw new IllegalArgumentException("Some descriptive error message!");
  int a = 1, b = 1;
  for (int i = 2; i < x; i++)
  {
    int c = a+b;
    a = b; b = c;
  }
  return b;
}


The only question was about the lower bound of i. Should it be 1, 2, or 3? And I had to listen to the person go through a sample invocation of the method with x=5. Damn, I should have thought of that. It's not exactly rocket science, is it?

I just typed that in and it works also!

Third question:
The third question was open-ended. The task was to design a model for a filesystem implemented in java. The main classes and the interactions between those classes.

I started by asking a few question of how that model might work and picking answers I liked. ;) I kind of thought aloud to explain my reasoning.

• Should it be a concrete implementation or an API? It should be a set of interfaces that describe the model. This allows clients to provide their own implementations, e.g. for a remote filesystem.
• Should there be a distinct class to model a filesystem? Yes, it's reasonable to expect multiple concurrent file systems. Also, Windows has multiple roots, which we could model as multiple file systems.
• Should file and directory be modeled separately or as one class? Both choices have their advantages and disadvantages. I went with the separate approach (distinct File and Directory classes) because they allow better type safety. However, to capture the commonalities, I introduced a common superinterface that I called FileSystemItem.

So my code looked like this:

interface FileSystem
  Directory getRoot();

interface FileSystemVisitor
  void visitDirectory(Directory directory);
  void visitFile(File file);


I know this looks pretty incomplete, but I barely had enough time to elaborate. First off, why did I return an array instead of a list? I thought about it for a moment but didn't find any convincing arguments either way - which I said.

As soon as I mentioned the visit method and the Visitor pattern, my interviewer shot off a couple of follow-up questions how that might work and how it is defined on directories and files. I guess I answered with a bit of unintelligible babbling, but my interviewer seemed to be content (content?) with my answers. The next question was about commonalities between File and Directory, so I started to list them, name, access rights... And the next follow-up question was how I would handle access rights, duh.

My design was along these lines:

enum Permission
  USER_READABLE, USER_WRITEABLE, USER_EXECUTABLE, GROUP_READABLE, ...

interface FileSystemItem
  boolean hasPermission(Permission permission);
  Set getPermissions();
  void setPermission(Permission permission, boolean enable);
  void setPermissions(Set allpermissions);


This developed over a little bit of discussion. Using an enum probably isn't the best choice, but I didn't have any other quick ideas. I started with the hasPermission method, but later changed that to introduce the getPermissions method and make hasPermission a convenience method. I also prefered the setPermission method over the setPermissions method, arguing that it is more difficult to reason about what should happen when something goes wrong, e.g. if you don't have permission to set all those permissions. Not the best of explanations, but I wasn't pressed on that.

I'm trying to get it all together, but after all the interview went on for 55 minutes (that's what the phone said when I hung up). There was another question on interfaces vs. abstract classes. Interfaces give less restrictions on the implementation and abstract classes allow bundling of common code. I went with a design that uses interfaces, but can provide abstract classes that implement the interfaces and include common code.

My Questions
After all that I was allowed a couple questions of my own. I asked how the interview went (to which I didn't get any convincing answer except that it went ok). I also asked what the interviewers position at google is (software engineer, only started last year, came from university). And my third (and last) question was some small interesting, exciting, fascinating story of something that happened at google. My interviewer said that he/she couldn't think of something of the top of the head and just told me a few standard things about google - nothing new there. That's not a complaint, it was kind of a personal question after all.

Wrapping up
Wrapping up, I think I did okish on the first question. I would have expected more from myself. I should have taken more notes there. The code works, but I didn't get the error handling/error conditions right. Second question I did very well, except for that tiny little thing at the end. I got the code right, but I should have thought of walking through the code myself. The third question ... I think I got the basics right (system of interfaces), my reasoning wasn't always entirely sound, but given the short amount of time, it went pretty well overall. Array vs. List? An enum for the permissions isn't the best design either, but I had to make a decision and that is something that works, at least. I could have done better, especially on the first question, but I think it's enough to get to the next step in Googles recruiting process.