A little visualization goes a long way
Clarity recently held its 15th Tech Challenge (TC). TCs are recurring coding competitions amongst the consultants here. Oftentimes the problems are released weeks in advance, such as developing an AI for a card game, and at the deadline the various solutions are tested against each other. TC 15 was the third time that we’ve done a Top Coder style tech challenge, where we compete to solve as many short coding problems in 90 minutes as possible.
I like this type of TC because it requires virtually no prep time to compete in (maybe some prep time to win) and it gives me a chance to work on some pure logic puzzles, the likes of which I don’t see every day during client work. I had a respectable finish, but was a little upset over one of the problems I missed.
The problem was an “easy” one, but in my rush to get through as many problems as possible, I made a mental modeling mistake. The problem statement was:
Southern China is suffering from a heavily snowy winter. The heavy snow even causes the closure of an important highway connecting southern and northern China. You've got several reports containing the start and end points of highway segments covered by heavy snow. Given those reports as two int[]s startPoints and endPoints, you are to return the total length of highway segments covered by snow. Note that the reported segments may overlap.
Some further constraints were given, basically allowing me to dispense with any error handling and then some test examples were given:
Example 1: {17,85,57}; {33,86,84}
Returns: 44 (these segments don't overlap)
Example 2: {45,100,125,10,15,35,30,9}; {46,200,175,20,25,45,40,10}
Returns: 132 (There are 3 segments covered by snow: 9-25, 30-46 and 100-200)
<-- and so on -->
My solution was able to pass all the given test cases, except for the first one. I ran out of time before I fixed it, but it turns out my overlap code was a bit off, and in the first example I was counting the segment between 84 and 85 as being snowy, when it was actually a gap.
Beyond a dish of humble pie for myself, the reason to bring this up was that it got me thinking about how much graphical visualizations can help to model a problem. For example, I am pretty sure I would have gotten this problem right on the first try if the examples had looked a bit more like this:
