How to Solve Every Software Engineering Interview Question
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 also 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.
Sidebar: This post is based on my experience as an interviewer and an interviewee at Google, however I am not writing on behalf of Google in any capacity.
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.
- Before writing anything, succinctly state your approach to the problem.
- Test: After implementing:
- Pick a basic (but not trivial) input and run through the code line-by-line given that input.
- Describe the test cases you’d write.
- Best option: write real unit tests!
- Second best option: describe each
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.
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.
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