Web Toolbar by Wibiya

Pages

Friday, July 15, 2011

Basketball Riddle

You have a basketball hoop and someone says that you can play 1 of 2 games.

Game #1: You get one shot to make the hoop.
Game #2: You get three shots and you have to make 2 of 3.

If 'p' is the probability of making a particular shot, for which values of p should you pick one game or the other?


Solution #1: The probability of winning Game #1 = p.

Probability of winning Game #2 = P(2,3) + P(3,3)
where,
P(2,3) = probability to make 2 of 3 shots, and
P(3,3) = probability to make 3 of 3 shots.

2 of 3 shots can be taken in C(3,2) ways: (YYN, YNY, NYY). Consider YYN, since these shots are independent, we can simply multiply their probabilities to find the probability of getting YYN.

Therefore, P(YYN) = p*p*(1-p).
It's obvious that the probability of other sequences(YNY, NYY) is also p*p*(1-p). So the total probability:
P(2,3) = 3*p*p*(1-p).

3 of 3 shots can be tken in one way, therefor:
P(3,3) = p*p*p.

So, probability of winning Game #2 = P(2,3) +P(3,3) = 3*p*p - 2*p*p*p.

Now, if P(Game #1) > P(Game #2):

p  > 3*p*p - 2*p*p*p,

on solving this equation, we get,

p < .5

So, play Game #1 when 'p' < .5 otherwise play Game #2.

Thursday, July 14, 2011

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

Solution #1: Imagine that the matrix is sorted in ascending order for both row and column. Here is the code,

int find(int arr[][5], int size, int num)
{
    int row=size-1;
    int col=0;

    while((row > 0) && (col < size))
    {
        if(arr[row][col] == num)
            return 1;
        else if(arr[row][col] < num)
            col++;
        else
            row--;
    }

    return 0;
}

void main()
{
    int arr[5][5] = {15, 25, 35, 45, 55,
             16, 26, 36, 46, 56,
             17, 27, 37, 47, 57,
             18, 28, 38, 48, 58,
             19, 29, 39, 49, 59};

    int row=0;
    int col=0;

    if(find(arr, 5, 24))
        printf("FOUND!!\n");
    else
        printf("NOT FOUND!!\n");

    /*for(row=0; row < 5; row++)
    {
        for(col=0; col < 5; col++)
            printf("%d ", arr[row][col]);

        printf("\n");
    }*/
}

Tuesday, July 12, 2011

Given a huge file with 2GB size with one string per line, which sorting algorithm will you use to sort the file and why?

Solution #1: The catch here is "2GB" file. By saying "2GB", the question stresses that we cannot bring the entire data in memory at the same time. Therefore we will have to sort the data in chunks. This can be done by a class of sorting algorithms called external sorting. External sorting works as follows:


Suppose we have 200 MB of available memory,

1) Read 200 MB of data in main memory and sort it by some conventional method like quicksort in O(n log n).

2) Write the sorted data back to a temporary file on disk.

3) Repeat steps 1 and 2 until all the data is in sorted 200 MB chunks (2GB/200MB = 10 chunks). We will now merge these chunks into a single output file.

4) Read the first 15 MB of of each chunk (15*10 = 150 MB total) into input buffer in main memory and allocate remaining 50 MB for output buffer.

5) Perform a 10-way merge on the input buffer and store the result in the output buffer. If the output buffer is full, write it to the final sorted file on the disk and empty it. If any of the 10 input buffers get empty, fill it again with the next 20 MB of the associated 200 MB chunk until no more data from the chunk is available.

Monday, July 4, 2011

Given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

Solution# 1: We will start with three pointers: a_end, a_tail and b_tail where;
a_end - last memory location of A
a_tail - last non-zero element of A
b_tail - last non-zero element of B

We start the merge from the end by comparing elements at a_tail and b_tail and putting the greater one at a_end. Here is the code,

void mergeArrays(int* A, int* B, int a_size, int b_size)
{
    int a_end = a_size + b_size - 1;
    int a_tail = a_size - 1;
    int b_tail = b_size - 1;
    
    while((a_tail >= 0) && (b_tail >= 0))
    {
        if(B[b_tail] > A[a_tail])
            A[a_end--] = B[b_tail--];
        else
            A[a_end--] = A[a_tail--];
    }

    while(b_tail >=0)
        A[a_end--] = B[b_tail--];
}

void main()
{
    int A[200] = {0,};
    int B[50] = {0,};
    int i;

    for(i=80; i<230; i++)
        A[i-80] = i*2;

    for(i=0; i<50; i++)
        B[i] = i;

    mergeArrays(A, B, 150, 50);

    for(i=0; i<200; i++)
        printf("A[%d] =  %d\n", i, A[i]);

}

Sunday, July 3, 2011

Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.

Solution #1: This is a classic problem to implement using backtracking. We will start from the first row and move down to the last row placing a queen at each row and checking that each queen satisfies the following two conditions:

- The column number must be different from the already placed queens.
- It should not share a diagonal with already placed queens.

Here is the code,

#define BOARD_SIZE 8
int col[BOARD_SIZE]={0,};

void printQueens()
{
    int i;
    for(i=0; i < BOARD_SIZE; i++)
    {
        printf("%d\n", col[i]);
    }
    printf("\n");

}

int checkRow(int row)
{
    int i;
    for(i=0; i < row; i++)
    {
        int diff = abs(col[i] - col[row]);
        if((diff == 0) || (diff == (row-i)))
            return 0;
    }
    return 1;
}

void putQueen(int row)
{
    if(row == BOARD_SIZE)
    {
        printQueens();
        return;
    }

    int i=0;
    for(i=0; i < BOARD_SIZE; i++)
    {
        col[row] = i;
        if(checkRow(row))
            putQueen(row+1);
    }
}

void main()
{
    putQueen(0);
}

Saturday, July 2, 2011

Implement "Paint Fill" function used in paint.

Solution #1: Given a border separated region within a canvas, a "Paint Fill" function fills the region with a given color when the user clicks inside that region. Essentially we color all the pixels starting from the clicked pixel till we hit border all around. This is a classic recursion problem. The code below first implements a canvas of size=50x50 and then initializes it with Black color(1), creates a region within the canvas and fills it with white color(0) and then calls the "fill" function to fill this region with red color(5) recursively and finally prints the canvas.
enum
{
    WHITE = 0,
    BLACK = 1,
    RED = 5
};
void printCanvas(int canvas[][50], int canSize)
{
    int x,y;

    for(y=0; y < canSize; y++)
    {
        for(x=0; x < canSize; x++)
        {
            printf("%d ", canvas[y][x]);
        }
        printf("\n");
    }
    printf("\n");    
}

void createBorder(int canvas[][50])
{
    int x,y;

    for(y=5; y<45; y++)
    {
        for(x=5; x<45; x++)
        {
            canvas[y][x] = WHITE;
        }
    }
}

void init_canvas(int canvas[][50])
{
    
    int x,y;

    for(y=0; y<50; y++)
        for(x=0; x<50; x++)
            canvas[y][x] = BLACK;
}


void fill(int canvas[][50], int canSize, int x, int y)
{
    if(canvas == NULL)
        return;

    if(((x < canSize) && (x >= 0)) && ((y < canSize) && 
    (y >= 0)) && (canvas[x][y] != BLACK) && (canvas[x][y] == WHITE))
    {
        canvas[x][y] = RED;
        fill(canvas, canSize, x, y+1);
        fill(canvas, canSize, x, y-1);
        fill(canvas, canSize, x+1, y);
        fill(canvas, canSize, x-1, y);
    }
}


void main()
{
    int canvas[50][50] = {0,};

    init_canvas(canvas);
    createBorder(canvas);

    fill(canvas, 50, 25, 25);
    printCanvas(canvas, 50);
}