CareerCup

This took some doing to get right. I wouldn't have gotten this on an interview... The basic idea is to start from the lower right corner, and search the grid with this repeating pattern: left, up, right, up... until the value is found. Binary search is used to improve O(n). As to what O(n) is... maybe something like O(d*log(d)), where d is the average of width and height. Anyone?

int* lower_bound_stride(int* pArr, int* pArrEnd, int val, int stride)
{
   while (pArr != pArrEnd)
   {
      int* pNext = pArr + ((pArrEnd - pArr)/(2*stride))*stride;
      if (*pNext < val)
         pArr = pNext + stride;
      else if (*pNext > val)
         pArrEnd = pNext;
      else
         return pNext;
   }
   return ((*pArr >= val)||(pArr == pArrEnd)) ? pArr : pArr + stride;
}

int FindInGrid(int* pGrid, int w, int h, int toFind)
{
   int curX = w - 1, curY = h-1;
   for (int i = 0; pGrid[curY*w + curX] != toFind; i++)
   {
      int* pLeft = pGrid + curY*h;
      switch (i%4)
      {
      case 0:
         curX = std::lower_bound(pLeft, pLeft + curX, toFind) - pLeft;
         break;
      case 2:
         curX = std::lower_bound(pLeft + curX, pLeft + w, toFind) - pLeft;
         break;
      case 1:
      case 3:
         curY = (lower_bound_stride(pGrid + curX, pGrid + curY*w + curX, toFind, w) - (pGrid + curX))/w; 
         if (((i%4) == 1) && (pGrid[curY*w + curX] > toFind))
            curY--;
         break;
      }
   }
   return curY*w + curX;
}


void main()
{
   int grid[] = {0,  2,  4,  8,  16,
                 1,  3,  5,  10, 18,  
                 6,  7,  9,  14, 21, 
                 11, 12, 13, 15, 23,
                 17, 19, 20, 22, 24};
   for (int i = 0; i < sizeof(grid)/sizeof(grid[0]); i++)
      printf("idx(%d) = %d\n", grid[i], FindInGrid(grid, 5, 5, grid[i]));
   getch(); 

}

output:

idx(0) = 0
idx(2) = 1
idx(4) = 2
idx(8) = 3
idx(16) = 4
idx(1) = 5
idx(3) = 6
idx(5) = 7
idx(10) = 8
idx(18) = 9
idx(6) = 10
idx(7) = 11
idx(9) = 12
idx(14) = 13
idx(21) = 14
idx(11) = 15
idx(12) = 16
idx(13) = 17
idx(15) = 18
idx(23) = 19
idx(17) = 20
idx(19) = 21
idx(20) = 22
idx(22) = 23
idx(24) = 24

Do a binary search to find the grid location

This can be solved using the binary search.
Check the value of (Matrix[0][0] + Matrix[M][N])/2
If its greater than the given value then low = {0,0} and high is {midM, midN}
else low is {midM, midN} and high is {M,N}

struct Point{
  int x;
  int y;
}Point;
  
Point* m_x_n_Grid(int * input, int length, int width, int test, Point pos)
{
  int x = pos.x;
  int y = pos.y;
  
  if (*(input+(x*width) + y) == test){
    return new Point(x, y);
  }
  else{
    Point * p1, p2;
    if (y + 1 >= length)
      return null;
    else if(*(input+(x*width) + y+1) > test)
      p1 = m_x_n_Grid(input, length, width, test, new Point(x, y+1))

    if (x + 1 >= width)
      return null;

    if (*(input+((x+1)*width) + y) > test)
      p2 = m_x_n_Grid(input, length, width, test, new Point(x+1, y))
      
    return (p1 == null)?p2:p1;
  }

}
void main()
{
  // some initialization for input, length and width of the grid
  // plus the input integer

  Point *p = m_x_n_Grid(input, length, width, test, new Point(0,0));
}