Interview Question
Country: China
Test code:
int main()
{
int x,y;
for(y=4;y>=-4;y--)
{
for(x=-4;x<=4;x++)
{
printf("%3d ", circle_digit(x,y));
}
printf("\n");
}
return 0;
}
Test Result:
73 74 75 76 77 78 79 80 81
72 43 44 45 46 47 48 49 50
71 42 21 22 23 24 25 26 51
70 41 20 7 8 9 10 27 52
69 40 19 6 1 2 11 28 53
68 39 18 5 4 3 12 29 54
67 38 17 16 15 14 13 30 55
66 37 36 35 34 33 32 31 56
65 64 63 62 61 60 59 58 57
Let A = max(abs(x),abs(y));
Num = (2*A+1)*(2*A+1);
If (x,y) lies in first quadrant
If x > y
Num = (2*(A-1)+1)*(2*(A-1)+1) + x-y;
else if x < y
Num = Num -(y-x);
else if (x,y) lies in 2nd quadrant
similarly define here too
and actually this is the function. you give any (x,y) it will give the number correspond to it in this matrix.
complexity is O(1);
Yep, the key observation is that you have the odd squares (1, 9, 25, 49, etc.) on the diagonal of the NE quadrant of the matrix. You essentially find the relevant odd square number and then compute an offset along an edge or two of the square. This allows you compute the number in constant time.
Lets take the initial cordinate system which is on 21 i.e. x=0, y=0 and 1 is at according to this system is x=2,y=-2
Now cordinate system changes to 1 therefore new cordinate system gets shifted to 2,-2
i.e to find (x,y) of any point subtract 2,-2 with x and y and if any of them is grater than 4 subtract 4 with it
i.e new cordinate becomes
x' = x - 2
if x'>4, x' = 4 - x'
y' = y - (-2)
similarly for y
Eg.
take example of 17 whose x=0, y = -4 according to old system
new x = 0-2 = 2
y = -4 -(-2) = -2
hence -2,-2
Suppose the matrix is p[5][5], so the the number of (x,y) is p[x+2][2-y]. for p[2*k+1][2*k+1], i guess the number of (x,y) would be p[k+x][k-y]. There is a pattern in the array n(k,k)=p[2k][0]=(2k+1)*(2k+1)
The c implementation of n(x,y) is as bellow:
- chenlc626 March 13, 2013include <stdio.h> int circle_digit(int x,int y) { int maxXY; maxXY=abs(x); if(maxXY<abs(y)) maxXY=abs(y); if(x==maxXY && y>-maxXY && y<maxXY) { //right side return ((2*maxXY-1)*(2*maxXY-1)) +maxXY-y; }else if(y==-maxXY && x> -maxXY && x<=maxXY) { return ((2*maxXY-1)*(2*maxXY-1))+3*maxXY-x; }else if(x==-maxXY && y >= -maxXY && y<maxXY) { return (2*maxXY-1)*(2*maxXY-1)+5*maxXY+y; }else if(y==maxXY && x>=-maxXY && x<=maxXY) { return (2*maxXY-1)*(2*maxXY-1)+7*maxXY+x; } }