(Trying out this nifty new feature, congratulations Unsplash) Photo by Ash Edmonds on Unsplash

Acing Software Engineering Interviews

A little while ago I was graduating college, and looking for a job. During that time, I spent a lot of my days gathering knowledge that could help me during technical interviews. I wanted to be able to pull off the perfect one, and come off as professional, knowledgeable, and above all, kickass. Below are some of my thoughts.

Alright, let’s jump right in and look at the easy gotcha questions. These are simple short-answer questions an interviewer can ask that will help them quickly gain some knowledge about you.

• What’s the difference between GET and POST?
• Explain the REST architecture.
• Why would someone need to overwrite the .equals() method in a Java class?
• Explain everything that happens when type in a url into your web browser.
• What is the main difference between HTTP 1.0 and 1.1?
• What is polymorphism?
• Implement a swap function without using a temp variable.
• What is the difference between an interface and an abstract method?
• How is a Hash Table typically implemented?
• Describe a binary tree structure and it’s variants.
• What is Late Static binding?
• How is the each method implemented in Ruby? How would you do it?

Next, here are some of the more involved programming related questions you may get:

Question One

We’ll begin with the good ol’ FizzBuzz problem, popularized by Jeff Atwood in this blog post.

Basically the idea is to print every number from 1 to n, however, print ‘fizz’ every time the number is divisible by 3, to print ‘buzz’ every time the number is divisible by 5, and the print ‘fizzbuzz’ every time the number is divisible by both 3 and 5 (15). These numbers could change to two different prime numbers. This doesn’t change how you would solve the problem.

One of my favorite solutions is:

def fizzbuzz(n):
  print “\n”.join([(‘Fizz’*(not i%3) + ‘Buzz’*(not i%5)) if ((not i%3) or (not i%5)) else str(i) for i in xrange(1, n+1)])

Another great one is:

def fizzbuzz(n):
 for i in xrange(1, n+1): print [i, ‘Fizz’, ‘Buzz’, ‘FizzBuzz’][(i%3 == 0) + 2 * (i % 5 == 0)]

Something else I’ve seen is building on this for a FizzBuzzBazz problem. This just adds the phrase “Bazz”, linked to the next prime, say 7. Everything else stays the same. Usually this is used to show why some solutions may be incorrect, or how they can be simplified.

Question Two

One of the most basic and common questions is “Show me an method that checks to see if a string has any duplicates.”

public boolean inUnique(string str) {
 boolean[] chars = new boolean[256]; // Only works with ASCII
 for(int i=0; i<str.size(); i++) {
   if(chars[str.charAt(i)]) return false;
   chars[str.charAt(i)] = true;
 }
 return true;
}

This approach is simple, and requires O(n) time. If space is more important, testing every char against every other char is the way to go:

public boolean isUnique(string str) {
 for(int i=0; i<str.size(); i++){
   for(int j=0; j<str.size(); j++) {
     if(i==j) continue;
     else if(str.charAt(j) == str.charAt(i)) return false;
   }
 }
 return true;
}

And yet another way, using a hash:

from collections import defaultdict
 
def isUnique(string):
 seen = defaultdict(lambda: False)
 for x in string:
   if not seen[x]: seen[x] = True
   else: return False
 return True

You could also use a bit vector to use even less space.

Question Three

Another common one is to find the nth fibonacci number.

def fib(n):
 return reduce(lambda x, y: [x[1], x[0] + x[1]], xrange(n-2), [0, 1])[1]

Question Four

Next, the parentheses problem. One of my favorites, just ask folks at SendGrid. In this one, the basic idea is to create a method that takes a string as input, and returns a boolean. True if the parentheses in the string are valid, false if not. E.g. () is valid. )( is not. There are lots of solutions to this problem. One thing to keep in mind: a stack lends itself perfectly to this problem. Here’s a solution using a one:

def validParentheses? str
 a = []
 str.each_char do |x|
   if x == ‘(‘
     a.push x
   elsif x == ‘)’
     return false if a.pop == nil 
   end
 end
 a.empty?
end

Alternate solotion, given to me by @Sirupsen:

def balanced?(string)
 string.each_char.inject(0) { |open, char|
 return false if open < 0
 char == ‘(‘ ? open + 1 : open — 1
 } == 0
end

It’d be pretty easy to extend this to work with many kinds of brackets. Something like this would do:

def balancedParens(s):
 stack, opens, closes = [], [‘(‘, ‘[‘, ‘{‘], [‘)’, ‘]’, ‘}’]
 for c in s:
   if c in opens:
     stack.append(c)
   elif c in closes:
     try:
       if opens.index(stack.pop()) != closes.index(c):
         return False
     except (ValueError, IndexError):
       return False
  return not stack

Also, here’s a similar problem.

Question Five

Alright, next, another common one I’ve seen goes something like ‘find all possible letter representations for a given phone number.’

num_map = {‘0’: ‘0’, ‘1’: ‘1’, ‘2’: ‘ABC’, ‘3’: ‘DEF’, ‘4’: ‘GHI’, ‘5’: ‘JKL’, ‘6’: ‘MNO’, ‘7’: ‘PQRS’, ‘8’: ‘TUV’, ‘9’: ‘WXYZ’}
 
def get_number_representations(n):
 return itertools.product(*[num_map[x] for x in n])

Question Six

Write a method to shuffle a deck of cards. It must be a perfect shuffle — in other words, each 52! permutations of the deck has to be equally likely. You can assume you have a true random number generator.

public void shuffleCards (int[] cards){ 
 int temp, index;
 for (int i = 0; i < cards.length; i++){
   index = (int) (Math.random() * (cards.length — i)) + i;
   temp = cards[i];
   cards[i] = cards[index];
   cards[index] = temp;
 }
}

Question Seven

Finally, for this section, there’s the classic ‘is binary search tree’ question. Simple enough solution:

def isBST(node, minVal, maxVal):
 if node is None: return True
 if not minVal <= node.val <= maxVal: return False
 return isBST(node.left, minVal, node.val) and isBST(node.right, node.val, maxVal)

Question Eight

The bottle one. You have a five quart jug and a three quart jug, an unlimited supply of water, and nothing else. How would you come up with ***exactly*** four quarts of water?

Like this:

• Fill 5
• Pour into 3
• Pour out 3
• Pour 2 from 5 into 3
• Fill 5
• Pour out 1 from 5 into 3

Or like this:

• Fill 3
• Pour into five
• Fill 3
• Pour 2 into 5 from 3
• Pour out 5
• Pour 1 into 5
• Fill 3
• Pour 3 into 5

Answering this may also just prove you’ve watched Die Hard. 😏

Haha…

Question Nine

A bunch of folks are on an island. A magical genie comes down and gathers everyone together and places a magical hat on at least one person’s head. The hat can be seen by other people, but not by the person wearing it. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are x people and y hats, how long does it take the folks to remove the hats? These people cannot talk to each other.

Answer:

y-1 nights. Simple, no? This is because if there’s one guy wearing a hat, he will see no one around him wearing a hat, it must be him, so he’ll go dunk his head in the water at midnight. Then, if two people are wearing hats, each will see someone else wearing a hat, wait a night, then see that the other didn’t go dunk their head, so it must be them and the other person with a hat on. And so on and so forth.

Question Ten

Here’s one I heard in college, from one of my favorite professors: There is a building of 100 floors. Eggs have a certain strength to them, and will break past floor x. Find the minimal n, with two eggs. By the end you can break both eggs.

Answer:

The most basic attempt is simple, drop the first egg from sqrt(floors), then increment. So 10, then 20, then 30, etc. Then once it breaks at floor x, drop it from floor (x*10)-9, then (x*10)-8, and so on. This puts the worst case minimum at 19.

In that case, we dropped each egg the same number of times no matter what floor the first broke at, a better way to do it is try and get each try of the first egg to reduce the amount you have to drop the second egg, resulting in a true minimum. This means solving for: (x) + (x-1) + (x-2) + (x-3) … + 1 = 100 → x=14. So we’d drop the first egg at 14, then 27, 39, etc. Our worst case minimum is 14.

Also, dynamic programming.

Now, I’m not saying these are the best types of questions to be asking candidates (they’re not), but they are the types of questions I get in interviews. For whatever reason. Doesn’t really matter, it’s your job right now to ace whatever they throw at you, and at least for just-out-of-college software engineering jobs, these tend to be the questions thrown at candidates.

The propose of this post is to get your mind going in the right direction; what you need to know to ace an interview, or at least the technical part. This is not meant to be the only document you read. From here another good next step could be to look at previous Google Code Jams, Top Coder, or (my favorite) Project Euler. Another interviewing technique I’ve seen is where the interviewer has already written the spec file, and it’s your job to make everything pass. Make sure to know you TDD/BDD stuff.

Another topic outside the scope of this post is how to act, this may have an even greater effect on your chances than having your technical wits. I wouldn’t have gotten my current job going in there wearing a suit, I came in wearing a sweatshirt and jeans, immediately fitting in with everyone else.

Last, but definitely not least, have fun! Interviews can be fun if you let them. Don’t stress, enjoy meeting some new people and talking tech. Happy interviewing!