How to Solve Every Software Engineering Interview Question

Published Nov 20, 2018 in Interviewing

This post unfortunately does not contain a secret skeleton key that will unlock every tricky Software Engineering interview question. What’s below is a framework that you can apply to every interview question that will set you up for success every time.

Software engineering interviews are not primarily about seeing if you can pull the #1 most perfect solution to a problem out of your hat. What’s more important is showing your work: demonstrating your analytical skills and problem solving ability. This is where a framework is useful.

It’s helpful to have an “interview checklist” in order to not forget about important steps, like running through your code line by line after writing it. What’s more, many interviewers are looking for you to run hit these steps every time you solve a question. Gayle Laakman McDowell has a great checklist in her book Cracking the Coding Interview.

The Framework

Here’s the 4-item checklist:

Clarify: Most questions aren’t 100% specified. Make sure to both:
- Ask clarifying questions
- State your assumptions
Design: Throw out a basic solution, then workshop it.
- It’s ok to write pseudocode in this phase, but say you’re doing so.
- If you have more than one idea, explain the tradeoffs you’re making when you choose one.
- Mention the time/space complexity of each option if it’s important.
Code:
- Before writing anything, succinctly state your approach to the problem.
Test: After implementing:
1. Pick a basic (but not trivial) input and run through the code line-by-line given that input.
2. Describe the test cases you’d write.
  - Best option: write real unit tests!
  - Second best option: describe each

Example Interview

I’ll run through a quick sample interview following these steps.

Setting the scene: you hop on the phone call or enter the interview room and after introductions, the interviewer asks you this question:

Write a program to print the outside nodes in a binary tree.

(from Google interview questions on Glassdoor)

Step 1: Clarify

Consider the input
- Is the root considered an outside node? [assume yes]
- Are leaves considered outside nodes? [assume yes]
- What about non-leaf nodes inside the tree? [assume no]
- Can I assume the tree is a proper binary tree? (e.g. no invalid edges)
- Assuming the input fits in memory.
Consider the output
- Should the nodes be printed in a certain order?

Step 2: Design

You could traverse the tree and keep track of whether you’re in an outside node or not. This coupled with checking if a node is a leaf would solve the problem.

This algorithm would need to traverse all n nodes, so it would take O(n) time and take up O(n) space since, in small cases, all nodes are outside nodes.

Specifically, in pseudocode:

# Tip: write "pseudocode" above any pseudocode you write.
outer_nodes = []
def visit_node(node, is_outer=None):
  is_leaf = not node.left and not node.right
  if is_outer or is_leaf:
    outer_nodes.append(node)

  # Continue traversing...
  visit_node(node.left, is_outer == 'left' and 'left')
  visit_node(node.right, 'is_outer == 'right' and 'right')

Step 4: Basic unit test

Wait… why is step 4 before step 3? Here’s where, personally, I might write some unit tests before implementaion.

I’m a proponent of Test-Driven Development. In interviews sometimes writing a simple test case beforehand can help clarify your assumptions (and check for any miscommunication). It also can get you brownie points because very few candidates will ever do this. I did this in my Google interview.

# Basic unit test
root = Node(1,
  left=Node(2,
    left=Node(3,
    right=Node(4,
      left=Node(6))),
  right=Node(5)))

self.assertListEqual(get_outer_nodes(root), [1, 2, 3, 6, 5])

Step 3: Write the code

Quickly recap what you’re about to write, then dive into the implementation. Here’s a sample solution:

class Node():
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left = left
    self.right = right


def outer_nodes(node, nodes, which_outer_node=None):
  if not node:
    return
  is_leaf = not node.left and not node.right
  if is_leaf or which_outer_node:
    nodes.append(node.data)

  left_outer_node = None
  if which_outer_node == 'left':
    left_outer_node = 'left'
  outer_nodes(node.left, nodes, left_outer_node)

  right_outer_node = None
  if which_outer_node == 'right':
    right_outer_node = 'right'
  outer_nodes(node.right, nodes, right_outer_node)


def get_outer_nodes(root):
  nodes = [root.data]
  outer_nodes(root.left, nodes, 'left')
  outer_nodes(root.right, nodes, 'right')
  return nodes

If you want to tinker with the code above without copy/pasting it, it’s available as a Colab notebook.

Step 4 (continued): Verify the code

After finishing the code, pick an input (like the tree in the unit test above) and run through the code line by line.

Wrapping Up

Having a checklist is useful in a lot of critical situations where your brain might be stressed and forget things – like piloting a plane, doing surgery, or… doing an engineering interview.

Clarify, design, code, test. Now go and get that job at $BIG_TECH_CO!

jeffcarp

Software

Life