Insert a node in a sorted linked list.

Solution #1: Below is the code to insert a node in a linked list sorted in ascending order. The code assumes that the list is not empty initially.

void insert_sorted(struct node** pHead, int n)
{
    struct node* curr = *pHead;
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = n;

    if(*pHead == NULL)
    {
        temp->next = NULL;
        *pHead = temp;
        return;
    }

    if(curr->data > n)
    {
        temp->next = curr;
        *pHead = temp;
        return;
    }

    while(curr->next != NULL)
    {
        if((curr->data < n) && (curr->next->data > n))
            break;

        curr = curr->next;
    }

    temp->next = curr->next;
    curr->next = temp;
}

Given an array of unsigned integers which is initially increasing and then decreasing, find the maximum value in the array.

Solution #1: This problem can be solved in O(log n) by modifying binary search as follows,

int search(int* arr, int strt, int end)
{
    int mid = (strt+end)/2;

    if((arr[mid-1] < arr[mid]) &&  (arr[mid] > arr[mid+1]))
        return arr[mid];
    else if(arr[mid-1] < arr[mid])
        return search(arr, mid+1, end);
    else if(arr[mid] > arr[mid+1])
        return search(arr, strt, mid-1);
}

int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 6, 5, 4};

    printf("%d\n", search(arr, 0, 9));
    return 0;
}

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;
}

Given an integer n, write code to calculate n+1, without using +,-,++,--,*,/

Solution# 1: Start from the LSB and keep setting them to 0 till we find the first 0. And then set that 0 to 1. Here is the code,

#include 
#include 

int increment(int n)
{
    int i = 1;

    while(i&n)
    {
        n = n & ~i;
        i = i<<1;
    }

    return n|i;
}

int main()
{
    printf("%d\n", increment(5));
    return 0;
}

Write an algorithm to find the number of ways of placing 3 balls in 3 buckets. Bucket 1 can hold 2 balls, bucket 2 can hold 3 balls and bucket 3 can hold 2 balls..

Solution# 1: We can try all the permutations using the following code,

#include 
#include 

int main()
{
    int A;
    int B;
    int C;
    int count=0;

    for(A=0;A<=2;A++)
    {
        for(B=0;B<=3;B++)
        {
            for(C=0;C<=2;C++)
            {
                    if((A+B+C)==3)
                    {
                        printf("%d%d%d\n", A, B, C);
                        count++;
                    }
            }
        }
    }
    printf("count = %d\n", count);
    return 0;
}

Given a string, print all possible uppercase and lowercase permutations of it.

Solution #1: This can be easily solved by recursion. Fix one letter to either uppercase or lowercase and permute rest of the letters. Here is the code,

#include 
#include 
#include 
#include 

void toggle(char* str, int n)
{
    if(n == strlen(str))
    {
        printf("%s\n", str);
        return;
    }

    str[n] = toupper(str[n]);
    toggle(str, n+1);
    str[n] = tolower(str[n]);
    toggle(str, n+1);
}

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

    sprintf(str, "suchit maindola");

    toggle(str, 0);

    return 1;
}

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.

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");
    }*/
}

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.

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]);

}

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);
}

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);
}

Write a function to generate nth Fibonacci number.

This can be done with both iteration and recursion.

Solution #1: Here is an implementation using recursion,

int fib_rec(int n)
{
    if(n == 0)
 return 0;

    if((n == 1) || (n == 2))
        return 1;
    
    return fib_rec(n-1) + fib_rec(n-2);
}

By adding arithmetic operators(+, -, /, *) and parenthesis, make the following expression true: 3 1 3 6 = 8.

Solution: ((3+1) / 3)*6

Write a program to swap odd and even bits of an integer using minimum instructions.

Solution #1: We can mask all the odd bits and shift them by one to right and similarly mask all even bits and shift them by one to the left and then combine the result. Here is the code,

int swapEvenOddBits(int num)
{
return ((num&0xAAAAAAAA)>>1) | ((num&0x55555555)<<1);
}

Write a function to determine the number of bits required to convert int A to B.

Solution #1: Basically, the question asks you to figure out which bits are different in A and B. Example: in case of 32 and 3, answer is 3 as they have 3 bits which are different. Taking a XOR and then counting the no. of 1s is the simplest approach. Here is the code,

void findBits(int a, int b)
{
    int c = a^b;

    int count=0;

    for(;c!=0; c=c>>1)
        count += c&1;

    printf("Number of bits required to convert int A to B is %d\n", count);
}

What does ((n&(n-1)) == 0) checks??

Solution: A number and its predecessor when &ed will result in '0' only when there is just one '1' bit in the number eg. 1000 and its predecessor 0111. So, this condition checks whether the number is a multiple of 2 or not.

Create mirror image of a tree.

Solution #1: A mirror image of a tree is a tree in which left and right children of each node get swapped. This problem has a recursive nature and therefore can be easily solved with recursion. The algorithm will look like this,

- check if  the node is NULL, if yes then return, continue otherwise
- swap left and right child
- repeat for left and right child

Here is the code,

void mirror(node *root)
{
    if(root == NULL)
        return;

    //swap left and right children
    node* temp = root->left;
    root->left = root->right;
    root->right = temp;

    //recursively call on left and right child
    mirror(root->left);
    mirror(root->right);
}

Multiply two integers without using * operator or while/for loop.

Solution #1: This can be done using recursion,

int multiply(int a, int c)
{
    static int b = 0;
    if(c == 0)
        return b;
    else if(c<0)
    {
        b-=a;
        return multiply(a,++c);
    }
    else
    {
        b+=a;
        return multiply(a,--c);
    }
}

void main()
{
    printf("Product = %d\n", multiply(5, -2));
}

3 ants are at 3 vertices of a triangle. They randomly start moving towards another vertex. What is the probability that they don't collide?

Solution #1: Let the vertices of triangle be A, B and C. Now, each ant has two path options eg. the ant at A can go either A->B or A->C. So, there are eight scenarios possible for ants movements(2*2*2). Out of these eight scenarios, there are two where there will be no collision: A->B, B->C, C->A or A->C, C->B, B->A. So the probability of no collision is 2/8 = 1/4.

Given a cake(cuboid) with a rectangular piece cut from it(any size or orientation), how would you divide the cake into two equal halves by a single cut of knife.

Solution #1: Consider a plane perpendicular to the cake and passing through the center of the cake. Now, no matter at what angle you keep this plane at, it will divide the cake in two equal halves. So, the point is, a perpendicular plane passing through the center of a cuboid will always divide it into two equal halves. Now, if we connect centers of cake and rectangular piece and run our knife through that line we will cut both of them in two equal halves giving us two equal halves of cake.

Write an algorithm for Breadth-first-search.

A breadth-first-search is one which starts from root node and crawls down exploring neighboring nodes.

Solution #1: We can use a queue to perform BFS. Here is the algorithm,

- Enqueue root node
- Dequeue a node and check it:
    - if it is a match, then return success
    - else enqueue it's children
- Check if queue is empty, if it's empty then return failure, otherwise repeat step 2.

Below is the code,

void bfs(struct node* root)
{
    queue q;

    q.push(root);

    while(!q.empty())
    {
        struct node* temp = q.front();
        q.pop();
        
        printf("%d ", temp->data);

        if(temp->left != NULL)
            q.push(temp->left);

        if(temp->right != NULL)
            q.push(temp->right);
    }

    printf("\n");
}

Given a sorted array in ascending order, write a function to create a binary tree having minimal height from this array.

Solution #1: We are asked to create a balanced tree to keep the height minimal. The balanced tree can be created by inserting the middle element first and then subsequently adding the left and right half of the array. This problem again demands recursion. The algorithm will look like this:-

- Insert middle element
- Insert left-half
- Insert right-half

Here is the code,

int arr[100] = {0,};

void insertArrElement(node **ptrRoot, int* arrPtr, int start, int end)
{
    if(start > end)
        return;

    int mid = (start+end)/2;
    insert(ptrRoot, arr[mid]);
    insertArrElement(&((*ptrRoot)->left), arrPtr, start, mid-1);
    insertArrElement(&((*ptrRoot)->right), arrPtr, mid+1, end);

    return;
}

int main()
{
    int i=0;
    for(i=0; i<100; i++)
        arr[i] = i;

    node* root = NULL;

    insertArrElement(&root, arr, 0, 99);
    
    return 1;
}

Write a function to check whether a tree is balanced or not.

A balanced tree is one in which no two leaf nodes differ in distance from the root node by more than one.

Solution #1: The most straight forward approach would be to calculate the maximum and minimum depth of the tree and then find out their difference. Here is the code,

int maxDepth(node* root)
{
    if(NULL == root)
        return 0;

    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return 1 + (leftDepth > rightDepth ? leftDepth:rightDepth);
}

int minDepth(node* root)
{
    if(NULL == root)
        return 0;

    int leftDepth = minDepth(root->left);
    int rightDepth = minDepth(root->right);

    return 1 + (leftDepth < rightDepth ? leftDepth:rightDepth);
}

int isBalanced(node* root)
{
    if(maxDepth(root) - minDepth(root) > 1)
        return 0;
    else
        return 1;
}

Sort a stack in ascending order when standard stack operations(push, pop, peek and isEmpty) are given.

Solution #1: We can use another stack to do the sorting. Suppose s1 is the original stack and s2 is the other stack. The algorithm will look like this,

- Pop from s1(e1) and peek s2(e2).
- if e2 < e1, then push e1 on s2,
- if e2 > e1, then keep popping from s2 into s1 till the next element is less than e1 and then push e1 on s2.

Keep doing it till s1 is empty. Now, s2 will be sorted in ascending order! This algorithm will have a time complexity of O(N^2).

Implement a queue using two stacks.

Solution #1: Suppose we have two stacks, s1 and s2. For enqueue operation we will simply push the data on s1. For dequeue, we will pop everything from s1 into s2 and will then pop from s2 and will again push everything back on s1.

Enqueue Operation:
- Push on s1

Dequeue Operation:
- Pop everything on s1 and push on s2
- Pop s2
- Pop everything on s2 and push again on s1

Now, the dequeue operation can be pretty time consuming when the stack is big. Also, two back to back dequeue operations will require needless moment of elements between two stacks. This can be optimized by letting elements stay in the s2 and en-queuing data to s1 and dequeuing from s2 till s2 becomes empty. So, essentially, we are reducing the number of stack transfers.

Enqueue Operation:
- Push on s1

Dequeue Operation:
- If s2 is not empty, pop from it
- If s2 is empty, pop everything on s1 and push in s2
- Pop s2

Given two numbers represented by linked lists with each node containing a single digit. Add them and return the list containing the resulting number.

Solution #1: Traverse both the lists adding their node's digit and storing the sum in the resulting list till one of the lists ends. Continue from the remaining list and add rest of its nodes to the resulting list. Here is the code,

Example:
list 1: 4 -> 5 -> 6
list 2: 7 -> 8 -> 9
result: 1 -> 4 -> 6 > 1

node* addLists(node* lptr1, node* lptr2)
{
    node* list = NULL;
    node* prev = NULL;
    node* remaining = NULL;
    int carry=0;
    int sum=0;

    while((lptr1 != NULL) && (lptr2!= NULL))
    {
        sum = 0;

        node* temp = (node*)malloc(sizeof(node));
        sum = lptr1->data + lptr2->data + carry;
        carry=0;

        if(sum >= 10)
            carry = 1;

        sum = sum%10;
        temp->data = sum;
        temp->next = NULL;

        if(list == NULL)
        {
            list = temp;
            prev = temp;
        }
        else
        {
            prev->next = temp;
        }

        prev = temp;
        
        lptr1 = lptr1->next;
        lptr2 = lptr2->next;
    }

    remaining = (lptr1 != NULL)?lptr1:lptr2;

    while(remaining != NULL)
    {
        node* temp = (node*)malloc(sizeof(node));
        temp->data = remaining->data + carry;
        carry = 0;
        temp->next = NULL;

        prev->next = temp;

        prev = temp;
        remaining = remaining->next;
    }

    return list;
}

In a linked list, delete a node with only a pointer given to that node.

Solution #1: Store the address of the next node in a temporary pointer. Copy the contents of the next node in the given node and delete the next node. Here is the code,

void deleteArbitNode(node* lptr)
{
    node* temp = lptr->next;


    lptr->data = lptr->next->data;
    lptr->next = lptr->next->next;

    free(temp);
}

Also note that this approach is not possible for deleting the last node.

In a linked list, find the nth element from the end.

Solution #1: An intuitive approach would be to do this problem recursively. Recursively travel till the last node and then get back till we reach the nth node from the end. Here is the code,

void nthElementRec(node* lptr, int n)
{
    static int index = 1;

    if(lptr->next == NULL)
        return;

    nthElementRec(lptr->next, n);
    index++;

    if(index == n)
        printf("%d\n", lptr->data);
}

Solution #2: Take two pointers, p1 and p2, and make them point to first and nth element from the beginning respectively. Now increment both the pointers till p2 reaches the end. At this point p1 will point to the nth element from the end. Here is the code,

void nthElement(node* lptr, int n)
{
    node* p1;
    node* p2;
    int i;

    p1 = p2 = lptr;

    for(i=0; i<n-1; i++)
        p2=p2->next;

    while(p2->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }

    printf("%d\n", p1->data);
}

Remove duplicates from a linked list.

Solution #1: If we are allowed to use extra space, iterate through the list storing each node's  data in a hash table. Now, if a node's data is already present in the hash table then it's a duplicate, so remove it.

Solution #2: Iterate over the list, checking all previous elements for duplication. If a duplicate is found, remove it. Here is the code,

void removeDup(node* lptr)
{
    node* curr = NULL;
    node* iter = NULL;
    node* prev = NULL;

    curr = lptr->next;
    iter = lptr;
    prev = lptr;

    while(curr != NULL)
    {
        while(iter != curr)
        {
            if(iter->data == curr->data)
            {
                prev->next = curr->next;
                free(curr);
                curr = prev;
                break;
            }
            iter = iter->next;
        }

        iter = lptr;
        prev = curr;
        curr = curr->next;
    }
}

To check whether a string is a rotation of another string or not.

Solution #1: The first thing, of course, would be to make sure that both the strings have same length. Now, suppose these strings are str1 and str2 and one of them is a rotation of the other(eq. str1 = "google" and str2 = "oglego"). Append str2 to itself(making "oglegooglego"). Now, if we have a function to find a substring within a string, we can use it to find str1 in modified str2. If found, then str2 is a rotation of str1.

Replace all spaces in a string with '%20'.

Solution #1: The most straight forward approach is to scan the entire string while copying it to another buffer and replacing each space with a '%20' in the new buffer. Time complexity will be O(n).

Solution #2: If we can assume that the string buffer is sufficiently large then we can scan the entire string to count the number of spaces and then modify the same string buffer by scanning it backwards and adjusting its length. Here is the code,

void replaceSpaces(char* str)
{
    int space_count=0;
    char* ptr = str;
    char* new_end = NULL;

    while(*ptr != '\0')
    {
        if(*ptr == ' ')
            space_count++;

        ptr++;
    }
        
    new_end = ptr + space_count*2;

    *new_end = '\0';
    
    while(ptr != str)
    {
        if(*ptr == ' ')
        {
            *new_end-- = '0';
            *new_end-- = '2';
            *new_end-- = '%';
        }
        else
        {
            *new_end-- = *ptr;
        }
        ptr--;
    }
}

Determine if two strings are anagrams or not.

Solution #1: If destruction of strings is allowed then we can sort the strings in O(n log n) time and then compare them in O(n) time.

Solution #2: If we have the luxury of using plenty of extra memory then we can create two arrays of size 256 and store the occurrence of all unique characters in both strings in each array and then compare the arrays. Here is a pretty straight forward code. Time complexity being O(n + n + 1) ~ O(n).

int areAnagrams(char* str1, char* str2)
{
    int i;
    int arr1[256] = {0,};
    int arr2[256] = {0,};

    int unique_char_1 = 0;
    int unique_char_2 = 0;
    char* ptr1 = str1;
    char* ptr2 = str2;

    while(*ptr1 != '\0')
    {
        if(arr1[*ptr1] == 0)
            unique_char_1++;

        arr1[*ptr1]++;
        ptr1++;
    }

    while(*ptr2 != '\0')
    {
        if(arr2[*ptr2] == 0)
            unique_char_2++;

        arr2[*ptr2]++;
        ptr2++;
    }

    if(unique_char_1 != unique_char_2)
        return 0;

    for(i=0; i<256; i++)
    {
        if(arr1[i] != arr2[i])
            return 0;
    }

    return 1;
}

Solution #3: The above code can also be written using just one array like this,

int areAnagrams(char* str1, char* str2)
{
    int arr[256] = {0,};

    int unique_char_1 = 0;
    int unique_char_2 = 0;

    char* ptr1 = str1;
    char* ptr2 = str2;

    while(*ptr1 != '\0')
    {
        if(arr[*ptr1] == 0)
            unique_char_1++;

        arr[*ptr1]++;
        ptr1++;
    }

    while(*ptr2 != '\0')
    {
        if(arr[*ptr2] == 0)
            return 0;

        arr[*ptr2]--;

        if(arr[*ptr2] == 0)
        {
            unique_char_2++;

            if(unique_char_1 == unique_char_2)
                return 1;
        }

        ptr2++;
    }

    return 0;
}

Remove duplicates in a string.

Solution #1: Let us first consider the case when extra buffer is not allowed. Scan every character in the string and compare it with every previous character, if it is a duplicate then ignore it, otherwise copy it. This approach will have a time complexity of O(n^2). Here is the code,

void removeDuplicates(char* ptr)
{
    int end = 1;
    int length = strlen(ptr);
    int current;
    int i;

    current = 1;

    for(end=1; end<length; end++)
    {
        for(i=0; i<end; i++)
        {
            if(ptr[end] == ptr[i])
                break;
        }

        if(i == end)
        {
            ptr[current] = ptr[i];
            current++;
        }
    }
    ptr[current] = 0;
}

int main(int argc, char** argv)
{
    char str[256] = {0,};

        gets(str);

    removeDuplicates(str);

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

    return 1;
}

2) Now, let's consider the case when we have the luxury of using extra memory. Also consider that the string is made up of extended ASCII characters. So let's make a bit array of 256 bits. Now, we can scan the string and use this array to keep a track of all the characters we encounter and ignore the duplicate ones.

Reverse a string.

Solution #1: If extra space is available then copy the string in reverse order to a newly allocated string in O(n) time.

Solution #2: Again, if extra space is permissible then we can use a stack to first push the entire string on the stack and then pop it in reverse order.

Solution #3: If it has to be done in place, then we can take two pointers at the start and end of the string and can swap the characters they point to while incrementing and decrementing them respectively till they collide.

Solution #4: Approach three can also be done recursively as follows,

void reverse(char *start, char *end)
{
    char temp;

    if(start >= end)
        return;
    
    temp = start[0];
    start[0] = end[0];
    end[0] = temp;

    reverse(start+1, end-1);    
}

int main(int argc, char** argv)
{
    char str[256] = {0,};
    int len;

        gets(str);
    len = strlen(str);

    reverse(str, str+len-1);

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

    return 1;
}

Determine if a string has all unique characters.

Solution #1: The most simple approach will be to check each character with every other character. The time complexity will be O(n^2) with no extra space requirement.

Solution #2:If changes are allowed, then we can sort the string in O(n log n) time and then check the adjacent elements for duplicates. Total time complexity is n log n + n ==> n log n.

Solution #3: If the string is formed of extended ASCII characters then we can make an array of size 256 and store the occurrence of each character in this array.

int main(int argc, char** argv)
{
    int arr[256] = {0,};
    char *ptr = NULL;

    ptr = argv[1];

    while(*ptr != '\0')
    {
        if(arr[*ptr])
        {
            printf("Found Duplicate...\n");
            return 0;
        }
        else
        {
            arr[*ptr] = 1;
        }
        ptr++;
    }

    printf("No duplicates...\n");

    return 1;
}

This code can further be optimized by using a bit array instead of using an int array. For that we will need 256 bits.