Program to find endianness.

Solution #1: Finding endianness of a machine is to detect whether the machine is little endian or big endian. In a little endian machine the least significant byte is stored first whereas in a big endian machine the most significant byte is stored first. Here is the code,

#include 
#include 

int main()
{
    int i = 1;
    char* ptr = (char*)&i;

    if(*ptr)
        printf("Little Endian\n");
    else
        printf("Big Endian\n");
    return 0;
}

Find the median of two arrays without merging them.

Solution #1: Let the two arrays be A[1...n] and B[1...m] and if they are not sorted initially, then sort them using any standard sort in O(n+m) time. below is the code to find the median without merging the arrays,

#include 
#include 

#define SIZEA 10
#define SIZEB 5

int median(int* A, int sizeA, int* B, int sizeB)
{
    int i=0;
    int j=0;

    int med = (sizeA + sizeB)/2+1;

    //2 is added to correct the offset as both the arrays starts at 0
    while((i+j+2) != med)
    {
        if((i < (sizeA-1)) && (j < (sizeB-1))) //none of the arrays reached the end
        {
            if(A[i+1] < B[j+1])
                i++;
            else
                j++;
        }
        else if (i == (sizeA-1)) //array A has reached the end
            j++;
        else if (j == (sizeB-1)) //array B has reached the end
            i++;
    }

    return A[i] > B[j] ? A[i] : B[j];
}

int main()
{
    int A[SIZEA] = {6, 8, 12, 13, 15, 19, 23, 25, 27, 45};
    int B[SIZEB] = {3, 22, 34, 39, 55};
    //int B[SIZEB] = {1, 2, 3, 4, 5};

    printf("Medain of A and B is %d\n", median(A, SIZEA, B, SIZEB));
    return 0;
}

Program to find maximum contiguous subsequence sum in an array.

Solution #1: The trivial case is when all the elements in the array are positive as in that case the maximum contiguous sum is the sum of all the elements in the array. Also, when all the elements are negative, the maximum contiguous sum is 0. The below code is based on the following observations:

- A maximum contiguous subsequence(MCSS) cannot have negative elements at the boundaries.
- All subsequences that border the MCSS will have negative or zero sum otherwise they would have been a part of MCSS.

Here is the code. The complexity is O(n).

#include 
#include 

#define SIZE 10

int maxSubSum(int *A, int size)
{
    int max = 0;
    int curSum = 0;
    int i, j;

    for(i=0, j=0; j < size; j++)
    {
        curSum += A[j];

        if(curSum > max)
            max = curSum;
        else if(curSum < 0)
        {
            i = j+1;
            curSum = 0;
        }
    }

    return max;
}

int main()
{
    int A[SIZE] = {-3, 4, 2, 1, -8, -6, 4, 5, -2, -4};

    printf("Maximum contiguous subsequence sum = %d\n", maxSubSum(A, SIZE));
    return 0;
}

Find intersection of two arrays.

Solution #1: Intersection of two arrays means the set of elements which are present in both the arrays. The code below assumes that both the arrays are already sorted. Even if they are not, they can be sorted using any standard sorting algorithm like merge sort in O(n logn). The below code has a complexity of O(m+n) where 'm' and 'n' are the size of the arrays.

#include 
#include 

#define SIZE_A 100
#define SIZE_B 300

void intersection(int* A, int lenA, int* B, int lenB)
{
    int i=0;
    int j=0;

    while((i < lenA) && (j < lenB))
    {
        if(A[i] == B[j])
        {
            printf("%d\n", A[i]);
            i++;
            j++;
        }
        else if(A[i] < B[j])
        {
            i++;
        }
        else
        {
            j++;
        }
    }
}

int main()
{
    int A[SIZE_A];
    int B[SIZE_B];
    int i;

    for(i=0; i < SIZE_A; i++)
        A[i] = i*11;

    for(i=0; i < SIZE_B; i++)
        B[i] = i*22;

    intersection(A, SIZE_A, B, SIZE_B);

    return 0;
}

Program to allocate memory for a 2D array.

Solution #1: Here is the code,

#include 
#include 

int** alloc2d(int row, int col)
{
    int i;
    int** ptr = NULL;

    ptr = (int**)malloc(row * sizeof(int*));

    for(i=0; i< row; i++)
        ptr[i] = (int*)malloc(col * sizeof(int));

    return ptr;
}

int main()
{
    int** arr = alloc2d(5, 10);

    int i,j;

    for(i=0; i<5; i++)
        for(j=0; j<10; j++)
            arr[i][j] = i*j;

    for(i=0; i<5; i++)
    {
        for(j=0; j<10; j++)
        {
            printf("%d\t",arr[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Write a program to shuffle a deck of cards.

Solution #1: The approach is to pick a card in sequence and replace it with another card picked at random from the remaining cards. Here is the code,

#include 
#include 
#include 

#define DECK_SIZE 52

//generate random number between a and b(both inclusive)
int gen_rand(int a, int b)
{
    int num;

    srand(time(NULL));

    num = a + rand()%(b-a+1);

    return num;
}

void shuffle(int *deck, int size)
{
    int i=0;
    int rand_pick=0;
    int temp=0;

    for(i=0; i < size; i++)
    {
        //pick a random card between current card and last card(both inclusive)
        rand_pick = gen_rand(i, size);

        //swap it with the current card
        int temp = deck[rand_pick];
        deck[rand_pick] = deck[i];
        deck[i] = temp;
    }
}

int main()
{
    int deck[DECK_SIZE];

    //initalize cards in serial order
    int i=0;
    for(i=0; i < DECK_SIZE; i++)
        deck[i] = i;

    shuffle(deck, DECK_SIZE);

    //print cards
    for(i=0; i < DECK_SIZE; i++)
        printf("%d\n", deck[i]);

    return 0;
}

Write a function to replace certain characters('., ') in a string with a special character('|').

Solution #1:
Example,
Input => "Hey, I am a rockstar.....yeah"
Output => "Hey|I|am|a|rockstar|yeah"

#include 
#include 
#include 

int hasCh(char *str, char ch)
{
    int len = strlen(str);
    int i = 0;

    for(i=0; i < len; i++)
    {
        if(str[i] == ch)
            return 1;
    }

    return 0;
}

void replace(char *str, char *delimit)
{
    int len = strlen(str);
    int cur = 0;
    int flag = 0;
    int i = 0;

    for(i=0; i< len; i++)
    {
        if(hasCh(delimit, str[i]))
        {
            if(!flag)
            {
                flag = 1;
                str[cur] = '|';
                cur++;
            }
        }
        else
        {
            flag = 0;
            str[cur] = str[i];
            cur++;
        }
    }

    str[cur] = '\0';
}

int main()
{
    char str[50] = {0, };

    sprintf(str, "%s", "Hey, I am a rockstart...yeah");

    replace(str, ", .");

    printf("%s\n", str);

    return 0;
}

Implement sizeof() operator.

Solution #1: We know that in pointer arithmetic, incrementing or decrementing a pointer of type 't' increments or decrements it by 'size of t' respectively. Below are some examples for 32-bit architecture,

int* pInt = 0x0004;
++pInt;                 //now it points to 0x0008

double* pDouble = 0x0002;
++pDouble;         //now points to 0x000A

char* pCh = 0x0005;
++pCh;                //now points to 0x0006

Now that we know this, we can make a character pointer point to an object of type 't' and another char pointer point to 't+1' and their difference will give the size of the object. Here is the code,

#define my_sizeof(a) (size_t)((char*)(&(a)+1)-(char*)(&(a)))

struct temp {
 int i;
 float f;
 char c;
};

int main()
{
 struct temp t;
 printf("Size of t is %d\n", (int)my_sizeof(t));

 return 0;
}