techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Displaying words in a spiral

Given a word, display it in a spiral
eg. "abcde" in a 6*7 matrix

a b c d e a b
b c d e a b c
a a b c d c d
e e b a e d e
d d c b a e a
c b a e d c b

Guys, I know this is an old question. But it was recently asked in a Microsoft Internship Interview. I am trying to figure out the best possible method. Any suggestions.
ashish Send private email
Wednesday, July 09, 2008
 
 
Here is my solution

    1 2 3 4 5 6 7
1    a b c d e a b
2    b c d e a b c
3    a a b c d c d
4    e e b a e d e
5    d d c b a e a
6    c b a e d c b

Principle Idea : For any element say (2,3) calculate the number of steps/hops you'll have to make from (1,1) to reach (2,3) if we move in a spiral fashion.

Another thing to be noted is the recursion
f(r,r)=f(r-1,r-1) + someValue
eg f(2,2)=f(1,1) + 22
similarly f(3,3)=f(2,2) + someValue
                =f(1,1) + someValue
                =1 + someValue

Therefore to calculate the number of hops( plus 1) for say
f(2,3) = f(2,2) + constant(we can easily calculate this
constant)

Is there any better way to calculate f(r,c) ??
ashish Send private email
Wednesday, July 09, 2008
 
 
Here is the code using the above principal idea

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int initial(int maxR,int maxC,int r,int c)
{
        int ri,ci;
        ri=(maxR-r) < r-1 ? maxR-r: r-1;
        ci=(maxC-c) < c-1 ? maxC-c: c-1;
        return (ri < ci ? ri : ci)+1;
}

int length(int maxR,int maxC,int r,int c)
{
    int i=initial(maxR,maxC,r,c),i1=1;
    int count=0;
    while(i1 < i)
    {
        count+=((maxC-1)<<1) + ((maxR-1)<<1);
        maxR-=2; maxC-=2;
        i1++;
    }
    if(r == i)
        count+=c-i+1;
    else if(c == i-1+maxC)
        count+=maxC-1+r-i+1;
    else if(r == i+maxR-1)
        count+=maxC-1+maxR-1+(i+maxC-1)-(c)+1;
    else if(c == i)
        count+=((maxC-1)<<1)+maxR-1+(i+maxR-1)-r+1;
    return count;
}

int main()
{
    int maxR,maxC;
    printf("\nnumber of rows :");
    scanf("%d",&maxR);
    printf("\nnumber of columns :");
    scanf("%d",&maxC);
    char s[]="abcde";
    int len=strlen(s);
    printf("\n%d",len);
    int i,j;
    for(i=1;i <= maxR;i++)
    {
      printf("\n");    
          for(j=1;j <= maxC;j++)
      printf("%c",s[(length(maxR,maxC,i,j)-1)%len]);
    }        
    system("PAUSE");
    return 0;
}
ashish Send private email
Wednesday, July 09, 2008
 
 
If you save the result in an array before printing it, and if you start filling the array from the center and walk in a spiral, you can solve the problem in O(R*C) instead of O(R*C*min(R,C)). Also, this way the spiral looks a bit better.

#define R      7
#define C      6
#define TEXT "abcde"

main()
{
    int r = (R-1)/2;
    int c = (C-1)/2;
    int steps = 0;
    char a[R][C] = {0};
    int dirR = 0;
    int dirC = 1;
    int ndirR, ndirC;

    while (r>=0 && r<R && c>=0 && c<C) {
        a[r][c] = TEXT[steps%strlen(TEXT)];
        // try to turn right
        ndirR = dirC;
        ndirC = -dirR;
        if (a[r+ndirR][c+ndirC] == 0) {
            dirR = ndirR;
            dirC = ndirC;
        }
        r += dirR;
        c += dirC;
        steps++;
    }
    for (r=0; r<R; r++) {
        for (c=0; c<C; c++) {
            printf("%c", a[r][c]);
        }
        printf("\n");
    }
}
Guenter Roeck Send private email
Thursday, July 10, 2008
 
 
Thanks Guenter :) . Your approach is nice and simple. Nice!!
ashish Send private email
Saturday, July 12, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz