Hack the Build: Interview Question Musings

I mentioned in an earlier post that I was moving to the C# team. Well, I’ve moved now and I’ve been spending some time interviewing developer candidates for positions in the C# product unit. A developer interview typically includes at least one coding problem. 

I’m also always on the lookout for new questions. Here’s the question I’m kicking around right now. Consider this code:

         
const int WIDTH = 8;
const int HEIGHT = 8;

interface IGrid {
  int CountBlocksSet(int x1, int x2, int y1, int y2);
}

enum Shape {
    Square,
 Rectangle
}

static Shape Recognize(IGrid grid) {
  // Implement this.
}

The goal is to implement a symbol recognition algorithm. The symbol can only either be a square or a rectangle. The image always fits in an 8-by-8 grid (zero relative) represented by ‘grid’. The method CountBlocksSet will return the total number of blocks that are set within the area of the rectangle passed in.

Calling CountBlocksSet is very slow (imagine that it’s driving a physical scanner) so you want to call it as few times as possible. The speed does not depend on the size of the rectangle passed in to CountBlocksSet.

I’ve posted a very naïve implementation of Recognize here as an example. If you run this on all squares and rectangles that will fit in an 8-by-8 grid you will get 64 calls to CountBlocksSet for each call to Recognize. There’s a simple improvement to this solution which will reduce the calls to ~16 (on average) and it’s possible to do even better than that. What algorithm gives the lowest number of calls (on average)? My personal best so far is average of ~3.3 calls, but the solution is not simple. My gut feeling is there is a simpler answer that gives as good (or possibly better) performance.

If you're interested in trying this out yourself, I've also included a bit of code here that will call Recognize with all possible rectangles and squares and report back on the efficiency of the algorithm. I've also create a mock implementation of IGrid to go along with it.

Update June 6, 2005

Several people have sent me solutions to this problem that do a far better job than my ~3.3 solution. The best so far goes to Travis Fisher who posted a solution that gives ~1.189 calls. His solution also was much easier to understand than mine and was far smaller--he only needed 15 semicolons (with no somersaults to reduce them).

Also, Ian McMeans posted a neat Python solution that weighed in at ~1.2615 (unverified).

Since I know there are still people working on this problem I'll wait a while before posting the spoiler.

This posting is provided "AS IS" with no warranties, and confers no rights.