On Coding Interview Tests

This is a post from my old blog before I switched to a garden model.

---

I botched a coding test the other day. It was my own fault really. I’ve been working as a Python programmer professionally for the past seven years, but when given the choice of language to use for this test, I chose Rust.

I chose it because in all my personal projects of late, I’ve been using Rust. I tend to describe it as a pragmatic Haskell, lacking some of the features of that language’s type system, but giving a little of the flavor and power that a strong type system provides. I’ve written several tools that I regularly use in it, and I’m pretty comfortable with it.

How did I botch the test then? §

I was asked to solve a problem that eventually involved writing a trie. The problem involved storing filter words in an efficient manner for a profanity filter, and a trie is a decent choice.

My usual approach to any kind of exercise like this is to start with the simplist thing that will work, and then get more complicated as the interview progresses. This might be the wrong way to approach these. Maybe the interviewer is hoping I’ll jump straight into hard mode, and I could see the value in that, but I don’t think there’s much sense in making things more complicated than they have to be.

So, I started writing a trie. I was allowed to look things up, and while I had the broad strokes in mind I hadn’t written one of these myself. My honest answer to a request to “write a data structure” would be to say “I’ll go look and see if there are any good implementations already available.” Just like one shouldn’t implement cryptographic algorithms from scratch, I feel like data structures are the same. But they are a popular choice for tests, so here we are.

First, I started with a structstruct:

#[derive(Debug)]
struct TrieNode {
	pub character char,
	pub is_end bool,
	pub children HashMap<char, TrieNode>,
}

#[derive(Debug)]
struct TrieNode {
	pub character char,
	pub is_end bool,
	pub children HashMap<char, TrieNode>,
}

Note

This isn’t the best way to represent this. We don’t actually need to store the charcter in the node, and we can tell if we’re in a leaf node by whether childenchilden is empty or not or even wrap it in an OptionOption. But this is what I wrote, so for sake of discussion, I’m leaving it as it is.

Then came the implementation:

impl TrieNode {
	/// Create a new root node
	/// TODO - consider making a wrapper Trie object instead
	fn root() ->  Self {
		TrieNode {
			character: ' ',
			is_end: false,
			children: HashMap::default(),
		}
	}
 
	/// Create a new node for the provide character
	fn new(character: &char) -> Self {
		TrieNode {
			character,
			is_end: false,
			children: HashMap::default(),
		}
	}
}

impl TrieNode {
	/// Create a new root node
	/// TODO - consider making a wrapper Trie object instead
	fn root() ->  Self {
		TrieNode {
			character: ' ',
			is_end: false,
			children: HashMap::default(),
		}
	}
 
	/// Create a new node for the provide character
	fn new(character: &char) -> Self {
		TrieNode {
			character,
			is_end: false,
			children: HashMap::default(),
		}
	}
}

So far this is all pretty boilerplate. Then came adding a word to the trie and where everything fell apart over a simple oversight.

N.B. I’ve added a lot of comments here that I hadn’t added during the test.

impl TrieNode {
	// ...
	
	/// Add a word to the Trie
	/// This uses an iterative approach of walking down the tree
	/// creating nodes along the way as needed. This might need to be
	/// recursive instead but we can get to that.
	fn add_word(&mut self, word: &str) {
		let mut node = self;
		for c in word.chars() {
			// If the current character is in the children, then we
			// just need to move into that node and continue
			if node.children.contains_key(&c) {
				// Here is where everything fell apart
				node = node.children.get(&c);
			} else {
				// ...
			}
		}
	}
}

impl TrieNode {
	// ...
	
	/// Add a word to the Trie
	/// This uses an iterative approach of walking down the tree
	/// creating nodes along the way as needed. This might need to be
	/// recursive instead but we can get to that.
	fn add_word(&mut self, word: &str) {
		let mut node = self;
		for c in word.chars() {
			// If the current character is in the children, then we
			// just need to move into that node and continue
			if node.children.contains_key(&c) {
				// Here is where everything fell apart
				node = node.children.get(&c);
			} else {
				// ...
			}
		}
	}
}

My first mistake was I hadn’t used a HashMap recently in this sort of context. I had forgotten how to look up keys in it. It’s a common data structure, you’d think I’d know it well, and if not the documentation is always available. I even looked at this page ¹.

Can you spot the problem (I did put a comment there)?

This line causes a type error, not even a borrow checker error, just a type error.

node = node.children.get(&c);

node = node.children.get(&c);

For the non-rustaceans in the audience, Rust has a decent amount of type inference. A lot of the time, the only types you need to specify are on data structures and function signatures. When I declared the nodenode variable what is actually happening is this:

let mut node: &mut TrieNode = self;

let mut node: &mut TrieNode = self;

But, the return value of node.children.get()node.children.get() is not a &mut T&mut T but a plain &T&T. Trying to assign a mutable reference to a non-mutable reference variable is a type error.

For the curious...

The reason that add_wordadd_word takes a &mut self&mut self is because we need to modify the trie when we actually add nodes. The code above doesn’t show that part, but it should be obvious.

At this point I probably panicked a little. It didn’t occur to me that the answer was as simple as just using get_mut()get_mut() instead. I didn’t find it quickly on the HashMap documentation and rust-analyze wasn’t helping much either.

I went down a rabbit hole of thinking I needed a Rc<RefCell>Rc<RefCell> to contain the children. This comes up a lot in self-referential data structures in Rust, and I usually think of it as a code smell², but I was too stressed to realize that didn’t apply here. Trees/tries aren’t self-referential.

So I ended up wasting half the coding test trying to sort out what should have been a simple problem, and ended up abandoning Rust and switching to Python just to try to salvage the situation as much as possible, but the damage was done.

Needless to say, I didn’t get called back.

A botched coding test from the other side §

I once was shadowing a coding interview for a fellow who was referred by a coworker of ours. He had worked with him at a previous job and knew what he was capable of.

Given that both of us knew that, we expected him to sail through this test, that it was just a formality. We couldn’t have been more wrong.

From the start he had issues getting on the office WiFi and then joining the Lifesize to share his screen on the monitor in the room we were in. The room was also the one meeting room built for recording so it had noise dampening walls that for some people is very off putting. Once he actually got to the test, he was so frazzled from all the technical issues that he floundered on things that should have been simple for an experienced Python programmer.

In the debrief I was torn. We are taught that if you’re on the fence, you should go with “No”, but then our coworker had vouched for this fellow, that had to count for something. I ended up going with “Hire” while the interviewer I was shadowing went with “No Hire” but he was also on the fence, the rest of the interviews went great, but the person making the final decision wanted to go with “No Hire”.

It was only after our coworker, the one who had referred him had forcefully argued that we give him another shot that it was decided to give him another test, and go from there.

That was about five years ago, and this fellow has been a productive member of the team since. Could we have afforded to skip on him? Maybe. But then we could also have ended up with someone worse.

What are these tests actually meant to measure? §

I’ve been on both sides of these tests over the years, and I never feel comfortable with them.

As the interviewee there’s the stress of trying to impress this stranger, on top of trying to get to know them and maybe establish a rapport. As the interviewer I always worry I’ll be stuck in the situation my poor interviewer was stuck in, watching someone flounder without any way to really help (they didn’t know Rust that well).

On one level, these tests are used to weed out the really poor performers, people who have inflated their resume, maybe even thrown in some lies. It’s better to miss a good candidate than to pick up a bad one, or so they say.

In a market like the current one, where so many software engineers are looking for work, it’s easier as the employeer to just be conservative and not take a risk. But then you could end up missing really good candidates.

What we’re trying to answer with these tests is, can this person program, and how do they write, document, and explain their code as they go. In some ways this might be better served by a short test outside of the interview setting and then a code review session with the interviewer where the candidate walks them through the code, and they have a conversation about it. Is that possible to cheat? Sure, but it will come up in the review. If the person doesn’t understand the code, isn’t able to defend their decisions, then it’s going to be obvious.

This sort of lower stress environment would also help with neurodivergent candidates, e.g. those with adult ADHD or autism. Those people tend to have a harder time getting through these sorts of tests.

In a real work environment, coding isn’t the majority of the work anyway. It’s thinking about and discussing what needs to be built. Those skills are better displayed in a code review setting.

I don’t know what the real solution is here. I just hate that my anxiety and stress made me miss out on what I know would have been a good fit, at a company I’d have happily stayed at for years to come.

Footnotes §

1. I think that cargo clippycargo clippy would have caught this and given a useful suggestion, but I also don’t think I ran that, another mistake.

2. Rust’s ownership model really nudges you towards thinking about who owns each value, so to me having to reach for Rc<RefCell>Rc<RefCell> means you might need to rethink your design.