Symbol Recognition Interview Question

By e June 9, 2005 Geek Stuff 1 Comment

Yesterday, I came across this post on Jomo Fisher’s Blog about an interview question he’s considering. To quote the problem in case his blog dies before mine does. . .

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 misunderstood the question, so my results aren’t precisely relevant (hence the posting here and not in his comments). I thought that (0,0) (0,0) for example, would define the bottom left-most point on the grid, and therefore not define a valid area. It looks like he is actually considering that to define the bottom-leftmost square, where I considered the space between (0,0) and (1,1) to be the bottom-leftmost square.

So, my results may not correspond directly to his, but they might still be interesting. Play with this a bit and then compare your results to ours.  My best effort so far is 1.17 calls to CountBlocksSet per grid.

One pointer to verify algorithm correctness. We know that the number of squares should equal 204, the number of rectangles (including squares) should equal 1296, and the number of non-square rectangles would therefore be 1092.

Attached are testdrivercs.txt, the test driver and sample implementation, and gridcs.txt, the sample IGrid implementation.

mysolutioncs.txt is also attached, and includes my iterative improvements.

One thought on “Symbol Recognition Interview Question”

  1. e

    Here’s the sample IGrid and CountBlocksSet interface
    IGrid { int CountBlocksSet(int x1, int x2, int y1, int y2);}
    enum Shape { Square, Rectangle, Unknown }
    class Grid : IGrid
    {
    int left;
    int right;
    int bottom;
    int top;
    public int TotalCalls = 0;
    public Grid(int left, int right, int bottom, int top)
    {
    this.left = left;
    this.right = right;
    this.bottom = bottom;
    this.top = top;
    }
    public int CountBlocksSet(int x1, int x2, int y1, int y2)
    {
    ++TotalCalls;
    int intersectRight = Math.Min(x2, this.right);
    int intersectLeft = Math.Max(x1, this.left);
    int intersectTop = Math.Min(y2, this.top);
    int intersectBottom = Math.Max(y1, this.bottom);
    if (intersectRight <= intersectLeft) return 0;
    if (intersectTop <= intersectBottom) return 0;
    return (intersectRight – intersectLeft) * (intersectTop – intersectBottom);
    }
    }

    Reply ↓

What do you think?