I've Lost My Marbles

"Lost, lost, no more happy thoughts." I peered over the top of my laptop toward the glow of the television screen. A feeling of nostalgia crept in as I connected eyes with Arthur Malet. His expression had an air of defeat and hopelessness as he portrayed the character Tootles in the 1991 film "Hook" directed by Steven Spielberg. Tootles was a lost-boy. A now elderly orphan whose prized possession was a misplaced leather pouch containing a small handful of marbles. These were his happy thoughts. Without them, he would be forever unable to return to Neverland. I watched quietly as my thoughts wandered to my own marbles. Not shiny, spherical, or even material at all, the marbles I had misplaced took a different form.

These marbles were philosophical. They were the subject of an interview problem that I had been challenged with years earlier. It was a warm fall morning with clear skies, the type that I would yearn for following the cloudy and consistently wet winter months in the Seattle area. Despite the luxurious accommodations of the hotel that my prospective employer's travel agent had booked for me, I managed to get very little sleep the night before. My pre-existing insomnia mixed with the extremely nervous energy of my upcoming interview had kept my neurons firing on all cylinders the night before. Unsure of what to do with my horribly nervous energy, I elected to walk from the hotel to the interview site.

At roughly three miles, the northward walk along Lake Union toward Fremont was serene. The sunlight had just begun spilling over the tall evergreens and the city was saying good morning. I peered east toward small seaplanes moored along the dock as I furiously tried to organize all of the lessons that I had learned in Gayle McDowell's "Cracking the Coding Interview." The interview would require that I work through problems with a programming language that I was allowed to select from a subset of languages. With each step, my anxiety increased. In this world, the interview itself had an algorithm, the candidate just didn't know what it was.

The day was a wreck. My anxiety had reached its peak. Having navigated four of the five interviews for the day, the fifth interviewer posed the final question that I would be required to solve.

You are given a grid of perpendicular lines. On the intersections of these lines are marbles. A marble may be removed from the grid if and only if it resides on the same horizontal or the same vertical as another marble. Write an algorithm to determine the optimal number of marbles that may be removed from the grid.

My wheels began to turn as the small-statured interviewer drew a small grid on the whiteboard. The illustration was familiar, a simple tic-tac-toe board. As we discussed the problem, it was quickly apparent to me that the problem was well-posed and that under the given constraints an optimal solution did, in fact, exist. Consider the following configuration with three marbles.

Note that removing marble one is valid as it lies on the same vertical as marble two.

Then of course, removing marble two is valid as it lies on the same horizontal as marble three.

Now, marble three is alone and cannot be removed because, in the current state, it does not lie on the same horizontal or the same vertical as any other marbles because marbles one and two have already been removed.

Now, we replace the marbles on the grid and start again. This time, we first remove marble two.

The removal is valid as it lies on the same vertical as marble one, and the same horizontal as marble three.

We are then left with marble one, and marble three. It is clear that neither of the remaining marbles may be removed as they do not lie on the same vertical or horizontal as another marble. As such, the final state is two marbles remaining rather than the single marble of the first attempt. Thus, we can achieve an optimal result.

I stared at the board considering the different algorithmic approaches that I might take. I won't belabor you with the details of my struggle. I only know that, in retrospect, if I were my interviewer, I would not have been impressed. Not because I lacked problem-solving skills to navigate the problem. I considered the different ways one might start removing marbles and considered the algorithms that I had in my toolbox. We discussed them, yet I struggled. The time expired. The interviewer and I exchanged pleasantries for the final time and I was escorted outside. The only thing I could do then was wait to hear from the recruiter handling my candidacy.

I reconsidered that specific problem for days. If I thought that I was Superman, it was my kryptonite. In the days following the interview, I wrote a working algorithm to solve the problem. I sat in the six-person cubicle in the basement office of my then current employer when the mail notification sounded. I switched to my inbox and read the subject line thanking me for my interest in the prospective employer. I didn't need to open the email to know that the body text would contain a scripted message that they had decided to pursue other candidates. I did anyway. I was crushed. That was the final stage, and the closest I would ever come to achieving the goals I had set for myself years prior.

The problem continued to haunt me throughout my career. I frequently discussed the problem with my colleagues and generally framed it as a horror story. I would think about it while listening to mind-numbing discussions about one language being superior to another and why this third-party framework was "correct" as it had far more stars on GitHub. I would never be allowed to engineer anything. Not for any of the companies that would hire me anyway. I would be turning login buttons blue my entire career and I knew it. Like Peter Banning, played by the late Robin Williams, straining with every fiber of his being to touch the outstretched hands of his children and secure their release from the villain Captain James Hook, I too clung to the mast unable to fly. To fly required happy thoughts and mine were a distant memory.

As if startled awake by Tinker Bell (Julia Roberts), I sat up sharply in my bed. I had it! My marbles weren't lost. I was simply searching in the wrong place. In that interview, and in the years after, I had always considered the problem through the lens of traversing the grid and removing the marbles. I had entirely missed the value of the exercise. I considered that the problem itself was only an abstraction. Revisiting the problem, I now understood that the marbles in the problem represented a graph where each marble represented a vertex in the graph and the removal rules represented edges between those vertices.

A graph $G$ is a set of vertices $V = {v_1, v_2, \cdots, v_n}$ and the set of edges $E = {e_1, e_2, \cdots, e_k}$ between those vertices where $e_i = {v_r, v_s}$ with $r \in [1, n]$ and $s \in [1, n]$ with $r eq s$. In our problem, the edge set$E$is created from the rules where$v_r$and$v_s$are adjacent if and only if$v_r$and$v_s$ lie on the same horizontal or the same vertical. Revisiting our problem we have

Then we have the graph $G = (V, E)$ with $V = {v_1, v_2, v_3}$ and $E = \Big{ {v_1, v_2}, {v_2, v_3}\Big}$. By inspection, we can see that the vertex set forms a connected component. It is also clear that if some subset of $V^* \subseteq V$ is a connected component, all of the marbles in $V^*$, save one, could be removed. Then the problem was no longer one of trying to traverse a grid, it was simply understanding the reduction and that to find the optimal number that could be removed, I simply needed to find the connected components of the graph, count them and subtract the count from the sum of the total number of vertices in each component.

We had already demonstrated that all but the last marble of each connected component could safely be removed. In the toy example, there is exactly one connected component containing three vertices. Then $3-1 = 2$ is the optimal number of marbles that can be removed. This generalizes quite easily.

I sprang from my bed with no concern for the time. I hurried into my office and started scrawling notes to convince myself. It wasn't about the marbles, it was task optimization. Understanding this problem gives rise to process optimization. Given a set of tasks and the dependencies between them, I could quickly and algorithmically optimize workflows with some minor adjustments.

Now, strictly speaking, I did sign a non-disclosure agreement so I will leave the full solution as an exercise to the reader. Regardless, these were my happy thoughts.

I could now return to Neverland.