I've quit my current job and am going through the interview process for a couple of companies. Since I'm applying for a technical role I have to take the occasional technical interview. Having done a lot of these myself (as an interviewer) I was looking forward to how other people will do that.
Let's look at one of the interviews in more detail. I'm going to explain what I like and what I didn't enjoy as much.
TL;DR
Full disclosure: my result was that I'm not a lead developer because the interviewer was not convinced that I had understood the problem and wasn't even sure that I understood the solution in the end. I had a good laugh when the responsible HR person broke the news (because I'm pretty high up my arse). So this post might be a bit biased towards shining a good light on me. I'll try to point out where I believe I made mistakes as well as the other way round.
Please tweet @philgiese with your feedback.
The challenge
The task I got was to create an algorithm that counts the number of paths between two points on a grid. I do have to admit that my enthusiasm immediately went out of the window. My best guess is that I will never have to do anything even remotely related to this challenge when I work for that company. Why test me with that task?
To reduce the scope of the problem there is a rule that you can only move to the right or to the top.
This means that A can never be higher up or farther to the right than B.
I was happy to hear this so that I didn't have to think about these scenarios anymore.
A couple of examples were then added to clarify what the test was looking for.
Admittedly, I have improved these examples here a bit. The ones I was looking at had no color coding. Also, the six paths example was missing. Here, the interviewer asked me "Can you see the six paths?". Obviously, I could not see the paths because they weren't there. I started drawing lines with my finger on my screen and then proclaimed "Yes, I can see six paths.".
I'll add these interruptions any time I think the flow of the interview could have been better.
This was the first occurrence when I wished for an online whiteboard like Miro. We started using it at work and I can't imagine a remote-life without it anymore.
I thought about getting a pen and paper but as my interviewers wouldn't be able to see what I doodle in front of me I ditched the idea. For now, I was left with my imagination. Unfortunately, this also means that my interviewers were left with my imagination which may have been a problem going forward.
Starting to code
After I declared that I had understood the problem I could start to code. We used syncfiddle for that. I had never used this tool before.
My first question was "Where can I write tests?" because that's how I approach problems.
Sadly, the tool doesn't support this but my interviewer pointed me to a couple of console.log() statements that would serve as my tests.
The first console.log() was A(0;0) and B(1;1).
Admittedly, I was happy so at least have some sort of editor I can code in. But this one isn't great. Some issues I had while coding:
- No test-runner (still, my biggest issue)
- All "tests" were equality checks (i.e.
console.log(numberOfPaths(A, B) === 6))) which isn't helpful because this doesn't show you how far off your solution is - No proper autocompletion (a couple of times I had syntax errors because I was missing a closing parenthesis)
- Wrong comment syntax (I used
CMD + /to toggle comments for a line or a block and it used the wrong syntax which screwed my code)
If they would have asked me before the interview whether I use VSCode with LiveShare we could have used a proper editor.
That way I would have been in an environment I'm used to, where I know the shortcuts, and where I could have added a spec-file.
Also, we could have seen each other's cursers which would have made it much easier to talk about specific parts of the code.
Before I started to code I said "I'm pretty sure this is going to be a recursive function in the end, but I'd like to start simple nonetheless.". I do this because TDD wants you to write the least amount of code to fix a test. So, I went ahead and wrote the following code.
function numberOfPaths(A, B) {
let stepsX = 0
for (let i = A.x; i < B.x; i++) {
stepsX++
}
let stepsY = 0
for (let i = A.y; i < B.y; i++) {
stepsY++
}
return stepsX + stepsY
}
With that code, the first "test" went green. I was happy. My interviewer was not. He told me that this algorithm does compute the number of steps and not the number of paths. That is true and also the reason why I called the variables steps and not paths. I was fully aware that this algorithm is not correct (and stated this before I wrote it) but I always want to start simple and then become more complex over time. That's how I approach problems and I thought that the interview was about that.
Anyway, I realized that I might need to show more of my algorithmic skills. I had the intuition that he wanted me to write the recursive version right away. With recursion, you need to make sure that you have some notion of "did I reach the end yet?" in your algorithm. Also known as the abortion criteria. Otherwise, no matter what you'll do you'll end up with a stack overflow error. I removed the code I had written so far and implemented the following two methods.
function canMoveX(A, B) {
return A.x < B.x
}
function canMoveY(A, B) {
return A.y < B.y
}
Interruption. "What are you doing there? Please explain what you're up to." OK, I might have been too silent when I removed my old code and added these two methods. I explained what I was going to write a recursive algorithm and that I think that I will need these two helper methods. Then I stubbed out the following code.
function numberOfPaths(A, B) {
if (!canMoveX(A, B) && !canMoveY(A, B)) {
// done, arrived at B
}
if (!canMoveX(A, B)) {
// arrived at right border
}
if (!canMoveY(A, B)) {
// arrived at top border
}
// split path
}
I explained that these are the conditions I'm thinking of.
When we can't move anymore we know that we've reached B.
If we can only move into one direction we hit a border.
That also means no new paths can appear given the rules we defined.
I probably made a big mistake right then and there. For me, part of the solution was to count how often a new path would split away along the way. As it turned out at the end of the interview that was not the mental model of the interviewer. This might have prevented a couple of misunderstandings along the way.
Given that I wanted to count splits along the way I wrote the following (wrong) code.
function numberOfPaths(A, B, paths = 0) {
if (!canMoveX(A, B) && !canMoveY(A, B)) {
return paths
}
if (!canMoveX(A, B)) {
return numberOfPaths({ x: A.x, y: A.y + 1 }, B, paths)
}
if (!canMoveY(A, B)) {
return numberOfPaths({ x: A.x + 1, y: A.y }, B, paths)
}
return (
numberOfPaths({ x: A.x + 1, y: A.y }, B, paths + 1) +
numberOfPaths({ x: A.x, y: A.y + 1 }, B, paths + 1)
)
}
At this point, I should add that the mental model of the interviewer was "count how often we arrive at B".
That doesn't play nicely with incrementing a number when you reach a split position.
He also asked me why I was incrementing a variable when there is a split to which I replied that I thought the task was to count the number of paths.
Given that we looked at the problem from two different angles and that from his point of view I was heading in the wrong direction I can understand that he wanted me to re-iterate the problem.
We even looked at the initial diagram (at the top of this post) again and he wanted me to state the problem again.
I must admit, that I was put off a little by that.
Because I didn't think that I was stuck.
My "tests" we're failing but that was OK.
I did not assume to crank out the correct algorithm.
When I looked at my conditionals I felt confident that they were correct.
The resulting number was simply way too large which meant there must be something wrong when I incremented my counter.
Then something happened that I did not expect. He changed my code. Now it looked like this:
function numberOfPaths(A, B, paths = 0) {
if (!canMoveX(A, B) && !canMoveY(A, B)) {
return 1
}
if (!canMoveX(A, B)) {
return numberOfPaths({ x: A.x, y: A.y + 1 }, B, paths)
}
if (!canMoveY(A, B)) {
return numberOfPaths({ x: A.x + 1, y: A.y }, B, paths)
}
return (
numberOfPaths({ x: A.x + 1, y: A.y }, B, paths + 1) +
numberOfPaths({ x: A.x, y: A.y + 1 }, B, paths + 1)
)
}
Now all tests were "green".
However, my line of thought was gone.
Why?
Because this solution only makes sense in the "count how often we arrive at B" model and not the "increase counter whenever we split a path" one.
In retrospect, it feels like the interviewer might have been convinced that I'm going nowhere. He might have thought that by changing my code he's going to help me. However, I felt this was extremely rude. Whenever I'm pairing or interviewing someone I would always ask whether I'm allowed to type something before I do it. Before that, I would highlight a piece of code (which didn't work in the editor we were using) to focus the attention of my pair.
The error I made was trying to carry the number of paths forward through the recursion. A change that would fit better would be that one:
function numberOfPaths(A, B) {
if (!canMoveX(A, B) && !canMoveY(A, B)) {
return 0
}
if (!canMoveX(A, B)) {
return numberOfPaths({ x: A.x, y: A.y + 1 }, B)
}
if (!canMoveY(A, B)) {
return numberOfPaths({ x: A.x + 1, y: A.y }, B)
}
return (
numberOfPaths({ x: A.x + 1, y: A.y }, B) +
numberOfPaths({ x: A.x, y: A.y + 1 }, B) +
1
)
}
Yes, this code is still not entirely correct (it's off by one) but would have gotten me closer to the solution. Of course, I can only guess that the interviewer couldn't follow. And ultimately its probably my fault for not being clear about my approach earlier on. What I would have wished for though would have been that the interviewer not simply point out the mistakes but asked me to re-iterate my approach. After all, this interview is all new information and work conditions for me and not for him.
I'm also not saying that my approach is better than his. It's definitively more complicated. But hey, make it work, then make it pretty.
For completeness, here's the code following my model that would ultimately work.
function numberOfPaths(A, B, initial = true) {
if (!canMoveX(A, B) && !canMoveY(A, B)) {
return 0
}
if (!canMoveX(A, B)) {
return numberOfPaths({ x: A.x, y: A.y + 1 }, B, false)
}
if (!canMoveY(A, B)) {
return numberOfPaths({ x: A.x + 1, y: A.y }, B, false)
}
return (
numberOfPaths({ x: A.x + 1, y: A.y }, B, false) +
numberOfPaths({ x: A.x, y: A.y + 1 }, B, false) +
// when you start at A you need to record two new paths
// after that there will always be only one new
// path when you encounter a split
(initial ? 2 : 1)
)
}
I haven't published the post yet but I keep thinking about it. I've come up with another solution that even better fits my mental model. Clear proof that 20 minutes doesn't tell you anything about a candidate.
function numberOfPaths(A, B, newPaths = 1) {
if (!canMoveX(A, B) || !canMoveY(A, B)) {
return newPaths
}
return (
// all paths we have found so far
newPaths +
// a split means we found one new path
numberOfPaths({ x: A.x + 1, y: A.y }, B, 1) +
// because we're already on an existing one
numberOfPaths({ x: A.x, y: A.y + 1 }, B, 0)
)
}
Improving the solution
As the last step, I was asked whether I could improve my solution.
Since I was still wrapping my head around "my" solution that really was his solution I asked what kind of improvement he was looking for?
He pointed out that, for instance, the code numberOfPaths({ x: A.x + 1, y: A.y }, B) appears twice.
Here's where I made another mistake.
I took this as a hint that I could extract some common code.
TL;DR that didn't work out.
I tried some weird things that would never have worked.
Maybe this was what caused my interviewer to think that I never understood the problem to start with.
Then, again, he adjusted my (or at this point our) code without asking me first.
function numberOfPaths(A, B) {
if (!canMoveX(A, B) && !canMoveY(A, B)) {
return 1
}
if (!canMoveX(A, B)) {
return 0
}
if (!canMoveY(A, B)) {
return 0
}
return (
numberOfPaths({ x: A.x + 1, y: A.y }, B) +
numberOfPaths({ x: A.x, y: A.y + 1 }, B)
)
}
My reaction? I said "Uh?" followed by "OK...". The thing is, that code is not correct and when he did the change my developer spider senses tingled with exactly that feeling. To this day I'm not sure whether he wanted me to tell him that he broke the code right then and there. Since it felt like he was showing me the solution I didn't respond with anything. That's again something I probably shouldn't have done.
Fun fact, five minutes after the interview I think I realized what he wanted me to do.
The moment you've hit a border you can't find any new paths.
So, what you can do to simplify this script is to merge the if-statements.
function numberOfPaths(A, B) {
if (!canMoveX(A, B) || !canMoveY(A, B)) {
return 1
}
return (
numberOfPaths({ x: A.x + 1, y: A.y }, B) +
numberOfPaths({ x: A.x, y: A.y + 1 }, B)
)
}
I felt a bit mislead by the statement about code duplication. Even though the question is a bit loaded he could have asked "Do you need all if-statements?". Then I could explain the logic back and probably have gotten the idea I had after the interview right in the interview. Ultimately, I felt a bit tricked into the wrong line of thinking.
Conclusion
I've pointed out already what I would have changed so let me start this by saying what I liked.
- The problem was not just explained but I had something to look at and some examples to help me get started.
- The shared coding session while not perfect was better than me, for instance, sharing my screen
- When I had some syntax errors my interviewer corrected them for me so that I can move along quicker
Now, to what I didn't like.
In general, I don't like this particular kind of test. This algorithm is either correct or incorrect. Therefore, it is hard to make progress and once you're just a little stuck you essentially fail the whole task. I've personally always chosen exercises where you can achieve 80% and leave with a good feeling.
While this interview was supposed to be about learning how I solve problems I got the feeling that it was about whether my approach matches his. To be fair, I might have caused this by not being vocal enough about what I'm going to do.
I never felt like the other people acknowledged that this is a stressful situation for me. What I sometimes do is to ask "do you need a minute to think?" so that I know the other person isn't stuck but just can't formulate his idea with words right now.
What really bothered me is that even though I told my interviewer that the code I'm going to write is not final and incorrect but that I want to start small he afterward pointed out exactly that. Also, when he edited parts of my solution without asking for permission first. The only effect this has is that he confused me because we were coming from different directions.
Update 2020-09-16
After I've published this blog post my colleagues also read it. Obviously, they immediately started to think about other ways to solve this puzzle. If they put their solutions somewhere online I'm going to add links to them. I must admit that I enjoy this a lot! That feeling when you see a problem and you can't stop thinking about it until you've also tinkered with it for some time.
- Federico Ghedina (fedeghe) came up with a solution that uses Pascal's triangle to compute the paths
Awesome solution because it works without recursion which means that it might run for quite some time but it will never result in a stack overflow error.
What are your experiences with interviews? Do you agree with me? What would you have done differently? Both from my position and the one of the interviewer? What kind of task do you use when you conduct technical interviews?
Do you have other and even better solutions for this problem?
Reach out to @philgiese on twitter with your thoughts!