Interview Questions #5

This was one of the interview questions which I come across.

/*
 * Find the distance from Source 'S' to Destination 'D' in the given array, and '#' 
 * denotes you can travel, '&' denotes you can't travel. The number of '#' between 
 * 'S' & 'D' represents the distance.  
 *
 * Input String 
 *                     {'#', '&', '#', 'S'},
 *                     {'#', '#', '&', '#'},
 *                     {'#', '&', '#', '#'},
 *                     {'D', '&', '#', '&'}
 *
 * Output String       6 
 */

#include<stdio.h>
#define COL_SIZE 4


int source_to_destination(char arr[][4], int column)
{
    int row, distance = 0, found = 0; 
    signed int col;
    // Check whether we got the array properly
    for (row = 0, col = 0; **arr && row < 4 && col < 4; col++) {
        printf("%c\t", *(*(arr + row) + col));
      
        if (col == COL_SIZE - 1) {
            col = -1;
            row++;
            printf("\n");         
        }
    }

    for (row = 0, col = 0; **arr && row < 4 && col < 4; col++) {
        
         
        if ((*(*(arr+row)+col) == '#')||  (*(*(arr+row) + col) == '&')) {
            //printf("%c\t", *(*(arr + row) + col));
            if (found == 1 && (*(*(arr+row)+col) == '#')) {
                distance++;
                //printf("Distance is %d\n", distance);
            }
            if (col == (COL_SIZE - 1)) {
                col = -1;
                row++;
                //printf("\n");
            }         
            continue;
        }

        if (*(*(arr+row)+col) == 'S') {
            //printf("Found Source, so set flag\n");
            found = 1;
        }

        if (col == (COL_SIZE - 1)) {
            col = -1;
            row++;
            //printf("\n");         
        }

        if (*(*(arr+row)+col) == 'D') {
            //printf("Found Destination, so print the distance\n");
            return distance;
        }
    }
    
    return 0;
}


/*
* Find the distance from Source 'S' to Destination 'D', and '#' denotes you can travel,
* '&' denotes you can't travel. The number of '#' between 'S' & 'D' represents the 
* distance.  
*/
int main()
{
    int distance = 0;
    char arr[][COL_SIZE] = {
                     {'#', '&', '#', 'S'},
                     {'#', '#', '&', '#'},
                     {'#', '&', '#', '#'},
                     {'D', '&', '#', '&'}
                   };

    distance = source_to_destination(arr, COL_SIZE);
    printf("The distance from Source to Destination is %d\n", distance);
    return 0;
}

Output:

# & # S # # & # # & # # D & # & The distance from Source to Destination is 6

Here is the optimized program from my friend.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define ROW 4
#define COL 4
#define SOURCE 'S'
#define DESTINATION 'D'
#define CHECK 1
#define DONT_CHECK 0
#define TRAVEL '#'



int find_distance(char *p)
{
    int i, flag = DONT_CHECK, n=0;

    for(i=0;i<ROW*COL;i++) {
         if(flag) {
             if(*(p+i) == TRAVEL)
                 n++;
             else if(*(p+i) == DESTINATION)
                 break;
         } else
             flag  = (*(p+i) == SOURCE) ? CHECK : DONT_CHECK;
    }

    return n;
}

int main()
{
    char a[ROW][COL] = {
                         {'#', '&', '#', 'S'},
                         {'#', '#', '&', '#'},
                         {'#', '&', '#', '#'},
                         {'D', '&', '#', '&'}
                       };

    printf("Distance between S and D is [%d]\n",find_distance((char*)a));
    return 0; 

} 

Output:

Distance between S and D is [6]

His point is you must understand that array is contiguous memory, so it's enough to do the entire program with single pointer as we are only traversing from the start to end.