CareerCup Interview Question
Country: United States
Interview Type: In-Person
#define DIR_UP 0
#define DIR_LEFT 1
#define DIR_RIGHT 2
#define DIR_DOWN 3
void
build_matrix(int *a, int n, int dir, int row, int col, int cur) {
a[row][col] = cur;
if (cur == n) {
return;
}
switch (dir) {
] case DIR_UP:
if (a[(row - 1) * n + col] == 0) { /* cell not yet written */
row--;
} else {
dir = DIR_RIGHT;
col++;
}
break;
case DIR_LEFT:
if (col > 0 && a[row * n + col - 1] == 0) {
col--;
} else {
dir = DIR_UP;
row--;
}
break;
case DIR_RIGHT:
if (col < n && a[row * n + col + 1] == 0) {
col++;
} else {
dir = DIR_DOWN;
row++;
}
break;
case DIR_DOWN:
if (row < n && a[(row + 1) * n + col] == 0) {
row++;
} else {
dir = DIR_LEFT;
col--;
}
break;
}
build_matrix(a, n, dir, int row, col, cur++);
}
void
print_matrix(int n) {
int *a, row, col, size = n * n * sizeof(int)
if (n == 0) {
return;
}
a = malloc(size);
memset(a, 0, size);
build_matrix(a, n, DIR_RIGHT, 0, 0, 1);
for(row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
printf("%d\t", a[row * n + col]);
}
printf("\n");
}
}
Just draw the matrices and watch for the odd (1st, 3rd, 5th, etc) and evens (2nd, 4th, 6th, etc)
It is easy to see that the Nth is generated from the (N-2)th by three simple operations:
a. "shift" the (N-2)th matrix right and down by one
b. Add 4*(N-1) to each element of the shifted matrix
c. "Draw" the border "around" of the shifter (N-2)th matrix by filling it with 1, 2, 3... N, ... 4(n-1)
(a. and b. is interchangable if you like or can be done paralelly, c. should be done after them IF we are not creating a new matrix just let the old one grow)
I know that it is not a simple solution but a very nice inductive way to create those matrices and induction equals recursion :)
#include <stdio.h>
#define MAX_N 20
// don't bother with parameter passing
int matrix[MAX_N][MAX_N];
void Spiral(int n) {
int i, j;
if (n == 1) {
matrix[0][0] = 1;
} else if (n == 2) {
matrix[0][0] = 1; matrix[0][1] = 2; matrix[1][1] = 3; matrix[1][0] = 4;
} else {
Spiral(n-2);
// shift and increment
for (i=n-1; i>0; i--) {
for (j=n-1; j>0; j--) {
matrix[i][j] = matrix[i-1][j-1] + 4*(n-1);
}
}
// fill border around
j = 1;
for (i=0; i<n; i++) { // top
matrix[0][i] = j++;
}
for (i=1; i<n-1; i++) { // right
matrix[i][n-1] = j++;
}
for (i=n-1; i>0; i--) { // bottom
matrix[n-1][i] = j++;
}
for (i=n-1; i>0; i--) { // left
matrix[i][0] = j++;
}
}
}
void Dump(int n) {
int i, j;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
printf("%3d", matrix[i][j]);
}
printf("\n");
}
printf("\n");
}
int main() {
int n;
for (n = 1; n<10; n++) {
Spiral(n);
Dump(n);
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
int time=1;
int recurse(int **M,int sr,int sc,int er,int ec)
{ int i=0;
if(sr<er&&sc<ec)
{
for(i=sc;i<=ec;i++)
M[sr][i]=time++;
for(i=sr+1;i<=er;i++)
M[i][ec]=time++;
for(i=ec-1;i>=sc;i--)
M[er][i]=time++;
for(i=er-1;i>sr;i--)
M[i][sc]=time++;
recurse(M,sr+1,sc+1,er-1,ec-1);
}
else
{
if (sr==er && sc==ec)
M[er][ec]=time++;
}
}
int main()
{
int N;
scanf("%d",&N);
int **M= malloc(sizeof(int*)*N);
int i;
for(i=0;i<N;i++)
M[i]=malloc(sizeof(int)*N);
recurse(M,0,0,N-1,N-1);
int j;
for(i=0;i<N;i++){
for(j=0;j<N;j++)
printf(" %3d ",M[i][j]);
printf("\n");
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
int time=1;
int recurse(int **M,int sr,int sc,int er,int ec)
{ int i=0;
if(sr<er&&sc<ec)
{
for(i=sc;i<=ec;i++)
M[sr][i]=time++;
for(i=sr+1;i<=er;i++)
M[i][ec]=time++;
for(i=ec-1;i>=sc;i--)
M[er][i]=time++;
for(i=er-1;i>sr;i--)
M[i][sc]=time++;
recurse(M,sr+1,sc+1,er-1,ec-1);
}
else
{
if (sr==er && sc==ec)
M[er][ec]=time++;
}
}
int main()
{
int N;
scanf("%d",&N);
int **M= malloc(sizeof(int*)*N);
int i;
for(i=0;i<N;i++)
M[i]=malloc(sizeof(int)*N);
recurse(M,0,0,N-1,N-1);
int j;
for(i=0;i<N;i++){
for(j=0;j<N;j++)
printf(" %3d ",M[i][j]);
printf("\n");
}
return 0;
}
#!/usr/bin/python
def create_spiral(n):
mat=list()
for i in range(n):
mat.append([0]*n)
spiral(mat,0,0,n,0)
for i in range(n):
for j in range(n):
print mat[i][j],
print
def spiral(mat,i,j,s,cnt):
if s<=0: return
val=cnt
for t in range(s):
val+=1
mat[i][j+t]=val
for t in range(1,s-1):
val+=1
mat[i+t][j+s-1]=val
for t in range(s-1,0,-1):
val+=1
mat[i+s-1][j+t]=val
for t in range(s-1,0,-1):
val+=1
mat[i+t][j]=val
spiral(mat,i+1,j+1,s-2,val)
if __name__=='__main__':
n=5
create_spiral(n)
Here is an iterative and recursive approach:
public static void main(String[] args) {
int n = 4;
fillMatrixIter(n);
fillMatrixRec(n);
}
public static void fillMatrixIter(int n) {
int[][] m = new int[n][n];
int z = n - 1;
int counter = 1;
for (int i = 0; i <= z; i++) {
for (int j = i; j <= z - i; j++) {
m[i][j] = counter++;
}
for (int j = i + 1; j <= z - i; j++) {
m[j][z - i] = counter++;
}
for (int j = z - i - 1; j >= i; j--) {
m[z - i][j] = counter++;
}
for (int j = z - i - 1; j >= i + 1; j--) {
m[j][i] = counter++;
}
}
System.out.println();
}
public static void fillMatrixRec(int n) {
int[][] m = new int[n][n];
int z = n - 1;
int counter = 1;
fillMatrixRec(m, 0, z, counter);
}
public static void fillMatrixRec(int[][] m, int i, int z, int counter) {
if (i > z) {
System.out.println();
return;
}
for (int j = i; j <= z - i; j++) {
m[i][j] = counter++;
}
for (int j = i + 1; j <= z - i; j++) {
m[j][z - i] = counter++;
}
for (int j = z - i - 1; j >= i; j--) {
m[z - i][j] = counter++;
}
for (int j = z - i - 1; j >= i + 1; j--) {
m[j][i] = counter++;
}
fillMatrixRec(m, i + 1, z, counter);
}
- bluesky September 28, 2012