ConnectedColors
Answering Google Tech Lead’s interview question
Google Tech Lead is a YouTube personality who posts content of interest to software engineers. Recently, I found a programming challenge he uses to interview candidates. Go ahead and watch him describe the problem. Note: you may want to pause the video prior to his explanation of the solution.
Problem
Given a grid of colored cells, find the maximum number of connected colors.
Above is an example of a 3x4 grid with 3 colors. The maximum number of connected colors is 5. You can also think of this as the maximum connected area.
The problem is a variation of the Flood Fill algorithm inspired by paint applications. Given a grid of colored cells and starting from a given cell and color, paint all matching connected cells a new color.
Algorithm
The basic idea is to apply depth-first search repeatedly until all cells in the grid are visited. The depth-first search should find the connected area reachable from a given point. Both recursive and iterative approaches are possible.
It’s important that the algorithm avoids re-visiting nodes. A naive implementation may fail to terminate by oscillating between visited nodes.
Solution
I decided to put together a solution in C#. You can find it on GitHub here.
Included
- recursive solution
- iterative solution
- unit tests
- README to get started
Let me know if you have a simpler or more efficient approach!