Coding Interview Problem: Make Two Robots Collide
Fifteen years ago when I was making the transition from academia into industry, I interviewed for a software developer job at Microsoft. The interview was pretty standard, but there was one question that struck me as interesting. After I was working, and started interviewing candidates myself, I often asked the same question. It’s an unorthodox question. I would never open an interview with it. I use it as a follow-up question for a candidate who does well on a more traditional coding question first. The question probes algorithmic thinking and concurrency in a way that is separated from any specific familiar programming language. It goes like this:
There are two identical robots on an infinite straight track. Each robot can move left and right, can make a mark on the track beneath them, and can sense whether there is a mark beneath them. Each robot can be programmed using the simple five-instruction assembly language described below.
The Problem
Write a single program that, when executed simultaneously in both robots, will cause them to collide. They begin an unknown distance apart. When they begin, the track has no marks on it.
