Deep or Wide (Job Interview Preparation)

I had the pleasure of a going through a couple of job interviews in the past month. I was pleased with my performance on both. They were pleased with my performance on at least one.

Both companies are cool tech firms, but the interviews were very different.

Wide Company

Wide Company wanted to know if I was a real, modern software developer. This means that they wanted to know about my knowledge of tools and techniques, and my understanding of the principles of modern software architecture. They belted out a series of short-answer questions that sounded something like this:

  • What is a design pattern? (A well-structured solution to a common software problem. Most of the time means creating an interface where you weren’t planning to use one.)
  • Can you name a design pattern? (Sure – me laughing – Singleton)
  • OK, what’s a Singleton? (OK, here is where I expressed regret at not naming Decorator or Composite, since those are more interesting. But a Singleton is a pattern – or antipattern if you don’t like it – that only allows one instance through a factory method. It accurately models resources such as the operating system in some instances.)
  • How familiar are you with JavaScript? (Pretty good. I know what variable hoisting is.)
  • How familiar are you with Java? (Pretty darned good. I can solve problems using Java in job interviews.)
  • Have you ever used git? (I deploy my web sites using git and use it extensively at work, independent of our official VCS.)
  • Do you know about AngularJS? (Well, I know it is an app framework, something resembling MVC. I don’t really know it right now.)
  • Have you ever deployed anything to the cloud? (Well, not really.)
  • What is a Lambda expression? (Roughly an anonymous function that may or may not capture some lexical scope. If it does capture variable values in this way, it can be called a closure.)
  • What is dependency injection? (Also called inversion of dependency, it’s when you decouple a class from a class it uses by having the latter conform to an interface and having the object specified at run time rather than instantiating it directly. The Spring framework automates this pattern.)

There were more, but I have forgotten them. Or perhaps blocked out the painful memories…

Deep Company

Deep Company wanted to know how I solve problems using algorithms, data structures, and software.

They sent me a shared document and asked me to type solutions that they reviewed live during the interview. They gave me programming problems, and I chose to solve the problems in Java. In this interview, the questions resembled exam problems from a university course, and they asked me not to reveal any questions outside of the interview. So I won’t! Instead, I’ll make up problems of similar difficulty :

  • Suppose you have two circular linked lists. Write a method that tells me if the two lists are equal. The signature might look like this :

boolean areEqual (Node a, Node b)

Now this is the point where you are supposed to ask questions, which I did. But I tried to provide my own answers where I could.

  1. Can I assume Node has fields Node.next, and Node.value?
  2. Are the passed nodes “head”, “tail”, or neither? A: Neither. There is no head or tail, and elements do not have a position index. It does not follow the traditional list API.
  3. Are the lists considered equal if the contain the same values in any orientation, regardless of whether a and b point to the same location in those lists?
  4. Can the nodes be null? Are there any one-element lists?
  5. And so on…

If you take the restriction that the nodes passed are supposed to be equal, and every element value matches at every position going around the list, then this problem can be solved by iterating around the list and checking each value for a match, and stopping when you reach the first node again. I wrote my answer mostly ignoring null edge cases at first,

  • Now write the same method, but without the assumption that the passed node positions have to match. Now a and b represent any arbitrary node in the circular list, but I want equals to be true if either list matches the other where you are allowed to start at any position.

Here I actually wrote down sample data structure instances as an example, and asked if they would be considered equal or not.

            a        b
            |        |
            v        v
Apple -> Banana -> Cherry ---
  ^                         |
  |--------------------------

I hope that you understand my ASCII art. I may need to work on my posting skills. Please comment if you have a cool tool for drawing data structures in WordPress or HTML.

And, yes, those two structures are supposed to return true for equality.

Now the problem becomes harder, but is still doable. You can brute-force the solution with a two-level loop, one rotate the starting position until the starting elements match in value, another to check each position for equality after that.

  • Can you optimize your solution?

Optimization depends on the use cases. An optimization for one case makes other cases run slower.

Suppose the lists contain lots of repeat values. If that is true, then keeping a count of the number of occurrences of each value in a hash table would allow you to short-circuit the method and return false right away if the lists do not contain the same content counts. But if the counts match, you must continue and check their structure to make sure that matches as well.

So, to the future : I am preparing for more interviews. But which way? Deep or wide?

Do I write some sample codes in Spring, AngularJS, and EJB 3.0?

Or do I solve algorithm puzzles and then optimize them?

I’ll do a little of both.

…

Wish me luck!