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.
Comments
- Anonymous
May 25, 2005
A little better than 3.3, 2.96 (ok, 3) average. I suspect lineTargets could be optimized.
int total = grid.CountBlocksSet(0, WIDTH, 0, HEIGHT);
if (total == 1) return Shape.Square;
int wide = 0;
int[] lineTargets = new int[] {4, 2, 6, 1, 7, 3, 8, 0 };
int i;
for (i = 0; i < lineTargets.Length && wide == 0; i++)
{
wide = grid.CountBlocksSet(0, WIDTH, lineTargets[i], lineTargets[i]);
}
if (wide * wide == total)
{
return Shape.Square;
}
else
{
return Shape.Rectangle;
} - Anonymous
May 25, 2005
Brute force expirementation shows that setting lineTargets to { 3,5,1,6,0,2,4,7 } and adding the obvious "if (total == 2) return Shape.Rectangle;" yields 2.65 average calls.
There's probably a wholly better algorithm though. - Anonymous
May 25, 2005
Using a lookup table for total->shape (discovered by brute force) gets you down to 1.3 calls. There's a mathematical relationship there between total blocks and the shape, but I can't quite figure it out.
There are a lot of places to go with this, seems like it might make a good interview question, to answer your original question. - Anonymous
June 03, 2005
Nice problem. This function has an average of 1.22 calls.
static Shape Recognize(IGrid grid)
{
int r=grid.CountBlocksSet(0, 7, 0, 7);
if (r==1 || r==9 || r==25 || r==36 || r==49 || r==64)
return Shape.Square;
if (r!=4 && r!=16)
return Shape.Rectangle;
if (r==16)
{ // distinguish between 4x4 and 2x8
int r2=grid.CountBlocksSet(1, 7, 1, 7);
r2=r-r2;
if (r2==2 || r2==9)
return Shape.Rectangle;
else return Shape.Square;
}
// r==4
// distinguish between 2x2 and 4x1
r=grid.CountBlocksSet(2, 4, 0, 7);
if (r==1 || r==3)
return Shape.Rectangle;
if (r==2)
if (grid.CountBlocksSet(3, 3, 0, 7)==1)
return Shape.Rectangle;
else return Shape.Square;
if (r==4)
if (grid.CountBlocksSet(3, 3, 0, 7)!=2)
return Shape.Rectangle;
else return Shape.Square;
r=grid.CountBlocksSet(1, 6, 1, 6);
if (r==0 || r==3)
return Shape.Rectangle;
if (r==1 || r==2)
return Shape.Square;
if (grid.CountBlocksSet(5, 5, 0, 7)==2)
return Shape.Square;
return Shape.Rectangle;
} - Anonymous
December 13, 2005
Mik's is very close to what I'd come up with. Slightly more efficient, I'm guessing, Jomo? - Anonymous
August 23, 2006
static Shape Recognize(IGrid grid)
{
int area = grid.CountBlocksSet(0, 7, 0, 7);
// Is the number a square number (1, 4, 9, 16...)
// If not then it's a rectangle.
double length = Math.Sqrt(area);
if (length - Math.Truncate(length) != 0)
{
return Shape.Rectangle;
}
// So we know the area is a square number.
// There is a limited number of rectangles with
// square numbers. These are:
// 1x4 = 4
// 4x1 = 4
// 2x8 = 16
// 8x2 = 16
if (area == 16)
{
int area2 = grid.CountBlocksSet(1, 7, 1, 7);
area2 = area - area2;
if (area2 == 2 || area2 == 9)
return Shape.Rectangle;
else
return Shape.Square;
}
if (area == 4)
{
int areaDif = area - grid.CountBlocksSet(1, 6, 1, 6);
if (areaDif == 0)
areaDif = area - grid.CountBlocksSet(2, 5, 2, 5);
if (areaDif == 0)
areaDif = area - grid.CountBlocksSet(3, 5, 3, 5);
if (areaDif == 1 || areaDif == 4)
return Shape.Rectangle;
else
return Shape.Square;
}
// The area is a square number
// and it's not one of the unusual rectangles
// with a square number area
// so therefore the shape must be a square.
return Shape.Square;
} - Anonymous
March 19, 2008
PingBack from http://blog.euphemos.com/2005/06/09/40/