Determine direction of stack growth.

Solution #1: The direction of stack growth depends on OS as well as on the architecture. Below is a program to detect the direction of stack growth,

void b(int* x)
{
    int y;

    //if address of y is less than address of x
    //then the direction is downwards, upwards otherwise
    if(&y < x)
        printf("Stack growing downwards.\n");
    else
        printf("Stack growing upwards.\n");
}

void a()
{
    int x;
    b(&x);
}

int main()
{
    a();
    return 0;
}

Subset sum problem.

Problem Statement: Given a set of numbers A[1...n], find a subset which sums up to a given number S.

Solution #1: Below is the code using Brute-force approach. The complexity is O(2^n).

int subsetSum(int* A, int len, int sum)
{
    if(sum == 0)
        return 1;
    
    if((len < 0) || (sum < 0))
        return 0;

    return subsetSum(A+1, len-1, sum) || subsetSum(A+1, len-1, sum-A[0]);
}

Solution #2: A faster way to solve this problem is by using dynamic programming. Below is the equation and the code,

RES[i][j] : is '1' if there is a subset in set A[1...i] which sums up to 'j', '0' otherwise.

RES[i][j] = RES[i-1][j] | RES[i-1][j-A[i]]

int RES[100][100];

int subsetSumDyn(int* A, int len, int sum)
{
    int i,j;

    for(j=0; j<=sum; j++)
        RES[0][j] = 0;
    
    for(i=0; i<=len; i++)
        RES[i][0] = 1;

    for(i=1; i<=len; i++)
    {
        for(j=1; j<=sum; j++)
        {
            int index = j - A[i-1];
            if(index >=0)
                RES[i][j] = RES[i-1][j] | RES[i-1][index];
            else
                RES[i][j] = RES[i-1][j];
        }
    }

    return RES[len][sum];
}

int main()
{
    int A[] = {13, 21, 11, 14, 4, 5};
    int len = sizeof(A)/sizeof(int);

    printf("Subset sub: %d\n", subsetSumDyn(A, len, 32));
    return 0;
}

Maze Algorithm.

Problem Statement: A mouse is at one corner of a maze and he has to reach the corner diagonally opposite to him. Write an algorithm to find the path through the maze. The maze is represented by a matrix of '0's and '1's where '1' denotes a path and '0' denotes a wall.

This problem can be solved using backtracking. Below is the code,

#define N 4

void printMaze(int maze[N][N])
{
    int i, j;

    for(i=0; i < N; i++)
    {
        for(j=0; j < N; j++)
            printf("%d ", maze[i][j]);
        printf("\n");
    }
}

void move(int maze[N][N], int sol[N][N], int x, int y)
{
    if((x == N-1) && (y == N-1))
    {
        sol[x][y] = 1;
        printMaze(sol);
        return;
    }

    if(x != N-1)
    {
        if(maze[x+1][y])
        {
            sol[x][y] = 1;
            move(maze, sol, x+1, y);
            sol[x][y] = 0;
        }
    }

    if(y != N-1)
    {
        if(maze[x][y+1])
        {
            sol[x][y] = 1;
            move(maze, sol, x, y+1);
            sol[x][y] = 0;
        }
    }
}

int main()
{
    int maze[N][N] = 
    {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {0, 1, 1, 1}
    };

    int sol[N][N] = {0,};

    move(maze, sol, 0, 0);
    return 0;
}

Edit Distance.

Problem Statement: The edit distance between two words is the minimum number of letter insertions, letter deletions and letter substitutions required to transform one word into another. For e.g. edit distance between "food"and "money" is 4. Below is the equation and the code for the problem,

min[i, j] = MIN(min[i-1, j] + 1, min[i, j-1] + 1, min[i-1, j-1] + (A[i] != B[j]))

#define MIN(a, b) ((a)<(b))?(a):(b)

int min[100][100];

int editDistance(char* A, char* B)
{
    int n = strlen(A);
    int m = strlen(B);

    int i, j;

    for(i=0; i <= n; i++)
        min[i][0] = i;
    
    for(j=0; j <= m; j++)
        min[0][j] = j;

    for(i=1; i <= n; i++)
    {
        for(j=1; j <= m; j++)
        {
            min[i][j] = MIN(min[i-1][j] + 1, min[i][j-1] + 1);
            min[i][j] = MIN(min[i][j], min[i-1][j-1] + (A[i-1]!=B[j-1]));
        }
    }

    return min[n][m];
}

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

    sprintf(A, "%s", "food");
    sprintf(B, "%s", "money");

    printf("EDIT DISTANCE: %d\n", editDistance(A, B));
    return 0;
}

Given two strings, print all interleaving strings.

Solution #1: Note that interleaving of two strings does not change the actual order of the characters within the two strings. For e.g.

str1 = "AB"
str2 = "MN"

So, in the output string, 'A' will always come before 'B' and 'M' will always come before 'N' .

Interleaving strings are,

ABMN
AMBN
AMNB
MABN
MANB
MNAB

void interleave(char* str1, char* str2, char* str, int len)
{
    int i=0;

    //if both input strings reach null, print final string and return
    if(str1[0] == '\0' && str2[0] == '\0')
    {
        printf("%s\n", str-len);
        return;
    }

    if(str1[0] != '\0')
    {
        str[0] = str1[0];
        interleave(str1+1, str2, str+1, len);
    }
    if(str2[0] != '\0')
    {
        str[0] = str2[0];
        interleave(str1, str2+1, str+1, len);
    }
}

int main()
{
    char* str1 = "AB";
    char* str2 = "MNO";

    //get length of input strings
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int len = len1+len2;

    //allocate memory for output string
    char* str = (char*)malloc(len+1);
    memset(str, 0, len+1);

    interleave(str1, str2, str, len);
    return 0;
}

Longest Increasing Subsequence problem.

Problem Statement: Given an array of integers, determine the longest increasing subsequence (not necesarily contiguous).

Solution #1: Below is the equation and the code for the problem,

Equations:
LIS[i] = MAX( LIS[j] ) + 1; where 0 <= j < i and A[i] > A[j]

#define MAX(a, b) ((a)>(b))?(a):(b)

int LIS[1000];

int lis(int* A, int len)
{
    int i, j;
    int max;

    LIS[0] = 1;

    for(i=1; i < len; i++)
    {
        max = 0;
        for(j=0; j < i; j++)
        {
            if(A[i] > A[j])
                max = MAX(max, LIS[j]);
        }

        printf("max: %d\n", max);

        LIS[i] = max + 1;
    }

    return LIS[len-1];
}

int main()
{
    int A[] = {4, 3, 9, 4 ,1 ,6};

    printf("LIS: %d\n", lis(A, 6));
    return 0;
}

Longest common subsequence problem.

Problem Statement: Given two character arrays, arr1[m] and arr2[n], determine a longest common subsequence among these two arrays.

Solution #1: A Brute force approach will take exponential time to solve this problem. We will use dynamic programming to solve it in O(mn) time and space. Below is the equation and the code for the problem,


LCS[i, j] = LCS[i-1][j-1] + 1 ; arr1[i] == arr2[j]
               = MAX(LCS[i-1][j], LCS[i][j-1]) ; otherwise

#define MAX(a,b) ((a)>(b))?(a):(b)

int LCS[100][100];

int lcs(char* arr1, int len1, char* arr2, int len2)
{
    int i = 0;
    int j = 0;

    //LCS is 0 when arr2 is NULL
    for(i=0; i <= len1; i++)
        LCS[i][0] = 0;

    //LCS is 0 when arr1 is NULL
    for(j=0; j <= len2; j++)
        LCS[0][j] = 0;

    for(i=1; i <= len1; i++)
    {
        for(j=1; j <= len2; j++)
        {
            if(arr1[i] == arr2[j])
                LCS[i][j] = LCS[i-1][j-1] + 1;
            else
                LCS[i][j] = MAX(LCS[i-1][j], LCS[i][j-1]);
        }
    }

    int temp = LCS[len1][len2];

    return temp;
}

int main()
{
    char* arr1 = "adbcad";
    char* arr2 = "dbacd";

    printf("LCS: %d\n", lcs(arr1, strlen(arr1), arr2, strlen(arr2)));
    return 0;
}

Count bits in an integer.

Solution #1: The most straightforward approach is to check each bit one by one. Here is the code,

int count1(int n)
{
    int count=0;

    while(n)
    {
        if(n&1)
            count++;

        n = n>>1;
    }

    return count;
}

Solution #2: The below code is an efficient version which improves the average time,

int count2(int n)
{
    int count=0;

    while(n)
    {
        count++;
        n = n&(n-1);
    }

    return count;
}

Coin denomination problem

Problem Statement: You are given n types of coin denominations of values d1 < d2 < ... < dn (all integers). Give an algorithm which makes change for an amount of money C with as few coins as possible.

Solution #1: Let min[i] represents the minimum number of coins required to make the change 'i'. Now, minimum number of coins required to make change 'C' = min[C-dj] + 1, where d1 <= dj <= dn. Below is the code with comments,

#define INFINITY 99999

int min[1000] = {0, };


int coins(int* arr, int len, int c)
{
    int i,j;

    //initialize all elements with INFINITY i.e.
    //infinite coins needed to make ith change
    for(i=0; i<=c; i++)
        min[i] = INFINITY;

    //0 coins are needed to get 0 change!
    min[0] = 0;

    //1 coin is needed to get the change equal to
    //any of the available coins
    for(i=0; i < len; i++)
        min[arr[i]] = 1;

    for(i=0; i<=c; i++)
    {
        for(j=0; j < len; j++)
        {
            int index = i-arr[j];
            if(index < 0)
                continue;

            if(min[index]+1 < min[i])
                min[i] = min[index]+1;
        }
    }

    return min[c];
}

int main()
{
    int arr[] = {4, 5, 7};
    printf("COINS: %d\n", coins(arr, 3, 166));

    return 0;
}

Implement atoi().

Solution #1: Here is the code,

int my_atoi(char* str)
{
    int len = strlen(str);
    int i;
    int isNegative = 0;
    int num = 0;

    if(str[0] == '-')
    {
        isNegative = 1;
        str++;
    }

    for(i=0; i < len; i++)
    {
        int curr = str[i] - '0';

        //if it is a digit then put it at the units place
        if((curr >=0) && (curr <= 9))
        {
            num = num*10 + curr;
        }
        else //if not a digit then break
            break;
    }

    if(isNegative)
        num = num*-1;

    return num;
}

int main()
{
    printf("%d\n", my_atoi("-123"));
    return 0;
}

Find second maximum value in an array efficiently.

Solution #1: Sorting is one obvious way, but, there is another efficient way. Here is the code,

int secondMax(int* arr, int len)
{
    int max = 0;
    int sMax = 0;
    int i = 0;

    for(i=0; i < len; i++)
    {
        int curr = arr[i];

        if(curr > max)
        {
            sMax = max;
            max = curr;
        }
        else if(curr > sMax)
            sMax = curr;
    }

    return sMax;
}

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

    printf("Second Max: %d\n", secondMax(arr, 5));

    return 0;
}

Implement mask_and_set_bits()

Solution #1: Given an integer 'value', a position 'pos', an integer 'n' and another integer 'bits'. Replace 'n' bits in 'value' starting at position 'pos' with 'bits'. Here is the code written for 32-bit architectures,

void mask_and_set_bits(unsigned int* val, unsigned int pos, unsigned int n, unsigned int bits)
{
    *val = (*val)&((0xFFFFFFFF << (pos+n))| ~(0xFFFFFFFF << pos));
    *val = *val|(bits << pos)&~((0xFFFFFFFF << (pos+n))|~(0xFFFFFFFF << pos));
}

Find 2 smallest numbers in an array efficiently.

Solution #1: Here is the code,

void findMinTwo(int* arr, int len)
{
    int i;
    int min = INT_MAX;
           int sMin = INT_MAX;

    for(i=0; i < len; i++)
    {
        //if arr[i] is less them min, set min = arr[i]
        //and set sMin = min
        if(arr[i] < min)
        {
            sMin = min;
            min = arr[i];
        }
        //else if arr[i] is less then sMin, update sMin
        else if(arr[i] < sMin)
        {
            sMin = arr[i];
        }
    }

    printf("%d %d\n", min, sMin);
}

Given an array of 0s and 1s, segregate 0s on left and 1s on right side.

Solution #1: Here is the code,

void segregate01(int* arr, int len)
{
    int start = 0;
    int end = len-1;

    while(start < end)
    {
        while((arr[start] == 0) && (start != end))
            start++;

        while((arr[end] == 1) && (end != start))
            end--;

        if(start < end)
        {
            swap(&(arr[start]), &(arr[end]));
        }
    }
}

Given a sorted array with duplicate elements, find the number of occurrences of x.

Solution #1: We will use the modified binary search to solve this in O(log n) time. Here is the code,

int count(int* arr, int x, int start, int end)
{
    if(start > end)
        return;

    int mid = (start+end)/2;
    int cnt = 0;

    if(arr[mid] == x)
        cnt = 1 + count(arr, x, start, mid-1) + count(arr, x, mid+1, end);
    else if(arr[mid] > x)
        cnt = count(arr, x, start, mid-1);
    else
        cnt = count(arr, x, mid+1, end);

    return cnt;
}

Given an array with duplicates, find the minimum distance between given x and y.

Solution #1: Below is the code with explanation in comments,

int minDistance(int* arr, int len, int x, int y)
{
    int prevIndex = -1;
    int min = INT_MAX;
    int i=0;
    int first;
    int second;
    int distance;


    for(i=0; i < len; i++)
    {
        if((arr[i] == x) || (arr[i] == y))
        {
            //first time encounter with x or y
            //'first' stores either x or y, depending on
            //which is encountered first
            if(prevIndex == -1)
            {
                first = (arr[i]==x)?x:y;
                second = (arr[i]==x)?y:x;
                prevIndex = i;
            }
            else
            {
                //if arr[i] is same as 'first', reset prevIndex
                if(arr[i] == first)
                    prevIndex = i;
                //if arr[i] is different from 'first', calculate distance
                else
                {
                    distance = i - prevIndex;
                    prevIndex = i;
                    min = MIN(min, distance);

                    //swap first and second
                    int temp = first;
                    first = second;
                    second = temp;
                }
            }
        }
    }
    return min;
}

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

    int len = sizeof(arr)/sizeof(int);

    printf("MIN DISTANCE: %d\n", minDistance(arr, len, 4, 5));
    return 0;
}

Reverse bits of a byte.

Solution #1. E.g.

00001001 ==> 10010000

Here is the code,


#define GET(n, x) ((n&(1<<x))>>x)
#define SET(n, x) (n|(1<<x))
#define RESET(n, x) (n&(~(1<<x)))

int reverseBits(unsigned char n)
{
    int temp = n;
    int start = 0;
    int end = 7;

    while(start < end)
    {
        int sbit = GET(n, start); //find start bit
        int ebit = GET(n, end); //find end bit
        
        //set end bit equal to start bit
        temp = sbit?SET(temp, end):RESET(temp, end);
        //set start bit equal to end bit
        temp = ebit?SET(temp, start):RESET(temp, start);

        start++;
        end--;
    }

    return temp;
}

Reverse a linked list.

Solution #1: Iterative approach to reverse a linked list,

void itrReverse(struct node** head)
{
    if(*head == NULL)
        return;

    struct node* prev = NULL;
    struct node* curr = *head;
    struct node* next = curr->next;

    while(1)
    {
        curr->next = prev;

        if(next == NULL)
            break;

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

    *head = curr;
}

Solution #2: Recursive approach to reverse a linked list,

void recReverse(struct node** head)
{
    struct node* first;
    struct node* rest;

    if(*head == NULL)
        return;

    first = *head;
    rest = first->next;

    if(rest == NULL)
        return;

    recReverse(&rest);

    first->next->next = first;
    first->next = NULL;

    *head = rest;
}
 

A sorted array is rotated unknown number of times. Find the minimum in the array.

Solution #1: A sorted array rotated unknown number of times will look something like this,

6, 7, 8, 9, 1, 2, 3, 4, 5

We will use modified binary search to find the minimum element in this array. Here is the code,

int findMin(int* arr, int start, int end)
{
    if(start == end)
        return arr[start];

    int mid = (start+end)/2;

    if(arr[mid] < arr[mid-1])
        return arr[mid];
    else if(arr[mid] < arr[end])
        return findMin(arr, start, mid-1);
    else if(arr[mid] > arr[end])
        return findMin(arr, mid+1, end);
}

Find diameter of a Binary Tree.

Solution #1: Diameter of a tree is the maximum distance between its any two nodes. For e.g. consider the below tree,

            5
         /      \
       2         9
     /    \      /
    1    4    7

Diameter: 5 (1-2-5-9-7 or 4-2-5-9-7)

Here is the code,

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

    int lh = height(root->left);
    int rh = height(root->right);

    return 1 + MAX(lh, rh);
}

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

    int lheight = height(root->left);
    int rheight = height(root->right);

    int ldia = diameter(root->left);
    int rdia = diameter(root->right);

    return MAX(1 + lheight + rheight, MAX(ldia, rdia));
}

Inorder traversal without recursion.

Solution #1: We can use a stack to implement Inorder traversal without recursion. Here is the code,

void recInorder(struct node* root, stack& s)
{
    struct node* current = root;

    while(1)
    {
        if(current != NULL)
        {
            s.push(current);
            current = current->left;
        }
        else
        {
            if(!s.empty())
            {
                struct node* temp = s.top();
                s.pop();

                printf("%d ", temp->data);

                current = temp->right;
            }
            else
                break;
        }
    }

    printf("\n");
}

Construct a Binary Tree, given its Inorder and preorder.

Solution #1: Consider the following tree,

               5
           /        \
         2          7
      /   \         /
     1    4      6

Inorder: 1 2 4 5 6 7
Preorder: 5 2 1 4 7 6

Algorithm:
1. Take first element from Preorder (in this case 5) and find it in Inorder.
2. Elements on the left side of '5' (1 2 4) form the left subtree of '5' and similarly elements on the right side (6 7) form right sub tree.
3. Recursively select each element from Preorder and create its left and right subtrees from Inorder.

Here is the code,

struct node* create(int* in, int* pre, int inStrt, int inEnd)
{
    if(inStrt > inEnd)
        return NULL;

    int i;
    static int preIndex = 0;

    //create node from preOrder
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = pre[preIndex];

    //find node in inOrder
    for(i=inStrt; i<=inEnd; i++)
        if(in[i] == pre[preIndex])
            break;

    preIndex++;
    
    //recursively call create for the left and right
    //half of inOrder created by preOrder
    temp->left = create(in, pre, inStrt, i-1);
    temp->right = create(in, pre, i+1, inEnd);

    return temp;
}

Find maximum width of a Binary Tree.

Solution #1: Maximum width of a tree is explained in the below e.g. 

                 4

             /       \

          5           7

       /     \       /

     9       8    3

Width of level 1: 1

Width of level 2: 2

Width of level 3: 3

Therefore, maximum width: 3

We will first write a function to calculate the width at a given level and then will use this function to determine the maximum width of the tree. Here is the code,

int width(struct node* root, int level)
{
    if(root == NULL)
        return 0;

    if(level == 1)
        return 1;

    return width(root->left, level-1) + width(root->right, level-1);
}

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

    int maxW = 0;
    int curW = 1;
    int level=2;

    while(curW)
    {
        curW = width(root, level++);

        maxW = MAX(curW, maxW);
    }

    return maxW;
}

Print nodes at level k in a Binary Tree.

Solution #1: Here is the recursive code,

void printLevel(struct node* root, int k)
{
    if(root == NULL)
        return;

    if(k == 1)
    {
        printf("%d\n", root->data);
        return;
    }

    printLevel(root->left, k-1);
    printLevel(root->right, k-1);
}

Get level of a node in a Binary Tree.

Solution #1: Here is the code,

int getLevel(struct node* root, int n, int level)
{
    if(root == NULL)
        return 0;

    if(root->data == n)
        return level;

    return getLevel(root->left, n, level+1) | getLevel(root->right, n, level+1);
}

Print ancestors of a node in a Binary Tree.

Solution #1: Here is the code,

int isAncestor(struct node* root, int n)
{
    if(root == NULL)
        return 0;

    if(root->data == n)
        return 1;

    if(isAncestor(root->left, n) || isAncestor(root->right, n))
    {
        printf("%d\n", root->data);
        return 1;
    }

    return 0;
}

Given a Binary Search Tree, print nodes within a given range.

Solution #1:

Algorithm:
- If the current node lies between 'min' and 'max', print it.
- If the current node is greater than 'min', recursively call left child.
- If the current node is lesser than 'max', recursively call right child.

Here is the code,

void printRange(struct node* root, int min, int max)
{
    if(root == NULL)
        return;
    
    if( (min <= root->data) && (root->data <= max) )
        printf("%d\n", root->data);

    if(min < root->data)
        printRange(root->left, min, max);

    if(root->data < max)
        printRange(root->right, min, max);
}

Print all permutations of a given string.

Solutiom #1:

void permute(char* str, int len, int level)
{
    //if last character is reached, print the string
    if(len == 1)
    {
        printf("%s\n", str-level);
        return;
    }

    int i;

    for(i=0; i < len; i++)
    {
        //swap first charater with the ith character
        swap(&(str[0]), &(str[i]));

        //recursively permute rest of the string
        permute(str+1, len-1, level+1);
        
        //bring first character back to its position
        swap(&(str[0]), &(str[i]));
    }
}

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

    sprintf(str, "abcd");

    permute(str, strlen(str), 0);

    return 0;
}

Count total number of vertical columns in a Binary Tree.

Solution #1: Every node in a binary tree can be considered belonging to a column. If we assume that 'root' belongs to column '0' then root->left belongs to column '-1', root->right belongs to column '+1' and root->left->right belongs to column '0' and so on. We have to find the total number of such columns. Here is the code,

void totalCol(struct node* root, int col, int* minC, int* maxC)
{
    if(root == NULL)
        return;

    totalCol(root->left, col-1, minC, maxC);
    totalCol(root->right, col+1, minC, maxC);

    *minC = MIN(*minC, col);
    *maxC = MAX(*maxC, col);
}

int main()
{
    struct node *root=NULL;

    int minC=0;
    int maxC=0;

    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 100);
    insert(&root, 30);
    insert(&root, 10);
    insert(&root, 5);

    totalCol(root, 0, &minC, &maxC);

    printf("Total Col: %d\n", maxC - minC + 1);

    return 0;
}

Given an unsorted array, find out if there exist a subarray whose sum is zero.

Solution #1: Here is the recursive code,

#define SIZE 9

int hasZero(int* A, int len, int prevSum)
{
    if(len == 1)
        return((A[0]+prevSum) == 0);

    int sum = prevSum + A[0];

    if(sum == 0)
        return 1;

    return hasZero(A+1, len-1, sum) | hasZero(A+1, len-1, 0);
}

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

    printf("hasSum: %d\n", hasZero(A, SIZE, 0));

    return 0;
}

Given a number, find the next larger number using the same digits.

Solution #1:

Algorithm:
- Move from right -> left and stop when the current digit is greater than the next one, let's call this point, 'hotspot'.
- Sort all the digits from hotspot till the end of the number in increasing order.
- Swap the digit on the left of the 'hotspot' with the last digit of the new number.

e.g.
5784321
hotspot: 8
after sorting: 5712348
after swapping: 5812347

Here is the code,

void nextLarge(char* num)
{
    int len = strlen(num);
    int i;

    //decrement i till digits are increasing from right to left
    for(i=len-1; num[i] < num[i-1]; i--)
    {
        //return if the digits are sorted in decreasing
        //order, number is already the largest.
        if(i == 1)
            return;
    }

    //sort everything from hotspot till the end
    sort(num, i, len-1);

    //swap digit before hotspot with the last one
    swap(&(num[i-1]), &(num[len-1]));
}

int main()
{
    char num[20] = {0, };

    sprintf(num, "%s", "5417962");
    
    nextLarge(num);

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

    return 0;
}

Calculate vertical sum of a Binary Tree.

Solution #1: Vertical sums of a binary tree are the sum of its each vertical column. For e.g. consider the below tree,

                 5

             /        \

          3           8

         /  \        /    \

       2     4    6     9

Vertical Sum for first column: 2

Vertical Sum for second column: 3

Vertical Sum for third column: 15 (5+4+6)

Vertical Sum for fourth column: 8

Vertical Sum for fifth column: 9

Output: 2 3 15 8 9

Algorithm:

- start from root and hash its value in a map using a key, say, 'key_col'

- recursively hash left and right children with key value 'key_col-1' and 'key_col+1'

- if the key entry is not present in the hash map then create one and set value as 'root->data'

- if the key entry is already present then just add 'root->data' to the existing value

In the end, we have vertical sum stored in the hash map. Here is the code,

void mapNode(struct node* root, map& m, int col)
{
    if(root == NULL)
        return;
    
    map::iterator it = m.find(col);

    //if column is already mapped and map already
    //has some value stored for the column then
    //add root->data to already stored value, otherwise,
    //just store root->data.
    if(it == m.end())
        m.insert(pair(col, root->data));
    else
        it->second += root->data;

    mapNode(root->left, m, col-1);
    mapNode(root->right, m, col+1);
}

int main()
{
    struct node *root=NULL;
    map m;
    map::iterator iter;

    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 100);
    insert(&root, 30);
    insert(&root, 20);
    insert(&root, 75);

    mapNode(root, m, 0);

    for(iter = m.begin(); iter != m.end(); iter++)
        printf("%d ", iter->second);

    printf("\n");

    return 0;
}

Find the kth largest element in a Binary Search Tree.

Solution #1: Traverse the tree in descending order and keep a count of number of nodes visited. When this count is equal to 'k', print the element. Here is the  code,

void printk(struct node* root, int k)
{
    if(root == NULL)
        return;

    static int index = 0;

    printk(root->right, k);

    if(++index == k)
    {
        printf("%d\n", root->data);
        return;
    }

    printk(root->left, k);
}

Reverse a stack without using extra space (recursion can be used).

Solution #1: Even recursion will take extra space, but, the purpose of the question is to come up with a recursive implementation. First, we will implement a function "insertAtBottom()" which inserts an element at the bottom of the stack. And then we will use this function to implement "reverseStack()". Here is the code,

Algo:
- recursively empty the stack.
- add elements back using "insertAtBottom()"

void insertAtBottom(stack& s, int x)
{
    if(s.empty())
    {
        s.push(x);
        return;
    }

    int a = s.top();
    s.pop();
    insertAtBottom(s, x);
    s.push(a);
}

void reverseStack(stack& s)
{
    if(s.empty())
        return;

    int a = s.top();
    s.pop();
    reverseStack(s);
    insertAtBottom(s, a);
}

int main()
{
    stack s;

    s.push(5);
    s.push(4);
    s.push(2);
    s.push(7);
    s.push(9);

    //current stack: top - 9 7 2 4 5 - bottom
    
    reverseStack(s);

    //reversed stack: top - 5 4 2 7 9 - bottom
    
    while(!s.empty())
    {
        printf("%d ", s.top());
        s.pop();
    }

    printf("\n");

    return 1;
}

Print all the possible strings a telephone number can represent.

Solution #1: The below code doesn't take into account the fact that keys 7 and 9 represent 4 alphabets and also it just prints ' ' and '+' for key 1 and 0 respectively. The code is just to explain the logic for printing the combinations and additional logic can be added to handle these cases. Here is the code,

char digitToChar(char x, int index)
{
    char ch;

    switch(x)
    {
        case '0':
            ch = '+'; break;
        case '1':
            ch = ' '; break;
        case '2':
            ch = "abc"[index]; break;
        case '3':
            ch = "def"[index]; break;
        case '4':
            ch = "ghi"[index]; break;
        case '5':
            ch = "jkl"[index]; break;
        case '6':
            ch = "mno"[index]; break;
        case '7':
            ch = "pqrs"[index]; break;
        case '8':
            ch = "tuv"[index]; break;
        case '9':
            ch = "wxyz"[index]; break;
        default:
            ch = ' ';

    }

    return ch;
}

void printAll(char* num, char* arr, int len, int x)
{
    int i=0;

    if(x == len)
    {
        printf("%s\n", arr);
        return;
    }

    for(i=0; i<3; i++)
    {
        arr[x] = digitToChar(num[x], i);
        printAll(num, arr, len, x+1);
    }
}

int main()
{
    char* num = "8017393450";
    char arr[20] = {0,};

    printAll(num, arr, 10, 0);

    return 0;
}

Implement itoa().

Solution #1: Here is the code,

void reverse(char* str)
{
    int len = strlen(str);

    int start = 0;
    int end = len - 1;

    while(start < end)
    {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;
    }
}

char* itoa(int x)
{
    char arr[50] = {0, 0};
    int isNegative = 0;
    int len = 0;
    int index = 0;

    if(x < 0)
    {
        isNegative = 1;
        x *= -1;
    }

    while(x)
    {
        int i = x%10;
        x = x/10;

        arr[index++] = '0' + i;
    }

    if(isNegative)
        arr[index++] = '-';

    arr[index] = '\0';

    reverse(arr);
    
    char* ptr = (char*)malloc(index+1);
    memcpy(ptr, arr, index+1);

    return ptr;
}

int main()
{
    printf("%s\n", itoa(-9247124));

    return 0;
}

Given a binary tree, store the sum of left and right subtrees in a node.

Solution #1: Here is the recursive code,

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

    int lsum = sum(root->left);
    int rsum = sum(root->right);

    int temp = root->data;

    root->data = lsum + rsum;

    return root->data + temp;
}

Print a binary tree level by level with each level printed on a new line.

Solution# 1: The regular BFS algorithm doesn't keep a track of the level it is on. We will modify it to keep a track of the current level. Below is the code,

Input Tree:
           6
         /    \
       4      8
     /   \       \
    1    5      9

Output:
6
4 8
1 5 9

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

    q.push(root);
    q.push(NULL);

    while(q.front() != NULL)
    {
        struct node* temp = q.front();
        q.pop();

        while(temp != NULL)
        {
            printf("%d ", temp->data);

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

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

            temp = q.front();
            q.pop();
        }
        
        printf("\n");

        q.push(NULL);
    }
}

Trim a tree so that all the elements in the tree are between min and max.

Solution #1: If the root is lesses than the 'min' then we know that we can trim the root as well as the entire left sub-tree. Similarly, if the root is greater than the 'max' then we know that we can trim the root as well as the entire right sub-tree. Here is the recursive code,

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

    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

struct node* trim(struct node* root, int min, int max)
{
    if(root == NULL)
        return NULL;

    if(root->data < min)
    {
        struct node* temp = root->right;
        freeTree(root->left);
        free(root);
        return trim(temp, min, max);
    }
    else if(root->data > max)
    {
        struct node* temp = root->left;
        freeTree(root->right);
        free(root);
        return trim(temp, min, max);
    }

    root->left = trim(root->left, min, max);
    root->right = trim(root->right, min, max);

    return root;
}

int main()
{
    struct node *root;

    insert(&root, 100);
    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 40);
    insert(&root, 30);
    insert(&root, 35);
    insert(&root, 120);
    insert(&root, 110);
    insert(&root, 32);

    Inorder(root);
    printf("\n");

    root = trim(root, 30, 50);

    Inorder(root);
    printf("\n");

    return 0;
}

Find the longest zig-zag path in a binary tree.

Solution #1: The longest zig-zag path is the longest LRLRLR... or RLRLRL... in a tree where 'L' and 'R' stands for left and right children. Also, note that the longest zig-zag path doesn't necessarily starts from the root. Here is the recursive code,

int maxZigzag(struct node* root)
{
    int lcount = 0;
    int rcount = 0;
    int max = 0;
    struct node* temp = root;

    if(root == NULL)
        return 0;

    while(1)
    {
        if(temp->left != NULL)
        {
            lcount++;
            temp = temp->left;
        }
        else
            break;

        if(temp->right != NULL)
        {
            lcount++;
            temp = temp->right;
        }
        else
            break;
    }
    
    while(1)
    {
        if(temp->right != NULL)
        {
            rcount++;
            temp = temp->right;
        }
        else
            break;

        if(temp->left != NULL)
        {
            rcount++;
            temp = temp->left;
        }
        else
            break;
    }

    max = MAX(lcount, rcount);
    max = MAX(max, maxZigzag(root->left));
    max = MAX(max, maxZigzag(root->right));

    return max;
}

int main()
{
    struct node *root;

    insert(&root, 100);
    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 40);
    insert(&root, 30);
    insert(&root, 35);
    insert(&root, 120);
    insert(&root, 110);
    insert(&root, 32);

    printf("maxZigzag = %d\n", maxZigzag(root));
    return 0;
}

Write a program to find if a tree is symmetric.

Solution #1: A symmetric binary tree is one where if you draw a vertical line passing through the root node then the left half should be the mirror image of the right half. Here is the recursive code,

int isSymmetric(struct node* l, struct node* r)
{
    if((l == NULL) && (r == NULL))
        return 1;

    if(((l == NULL) && (r != NULL)) || 
            ((l != NULL) && (r == NULL)))
        return 0;

    return isSymmetric(l->left, r->right) && isSymmetric(l->right, r->left);
}

Verify a Binary Search Tree or implement isBST().

Solution #1: A Binary Search Tree can be verified using its property that the left child is smaller than the root which is smaller than the right child. But checking just that does not suffice as in the below case, such an approach will fail,

            8
        /        \
     4          16
   /    \       /     \
 2     9    10     20

Approach: Every node's data must lie between a 'min' and a 'max' value. These values are adjusted as we move through the recursion. If we move to the left child, the 'max' value becomes the value of the parent's data as no node in the left tree can have a value greater than the parent. Similarly, as we move to the right child, the 'min' value becomes the value of the parent's data as no node in the right tree can have a value lesser than the parent. Here is the code,

int isBST(struct node* root, int min, int max)
{
    if(root == NULL)
        return 1;

    if((root->data < min) || (root->data > max))
        return 0;

    return isBST(root->left, min, root->data) && isBST(root->right, root->data, max);
}

int main()
{
    struct node *root;

    insert(&root, -10);
    insert(&root, -20);
    insert(&root, 30);
    insert(&root, -5);
    insert(&root, 40);

    printf("isBST = %d\n", isBST(root, INT_MIN, INT_MAX));
    return 0;
}

Implement a stack with a constant time minimum lookup.

Solution #1: A constant time minimum lookup can be achieved by using an extra stack. Let's call this stack 'min_stack'. This stack will always have the minimum value at the top.

Modify 'push' and 'pop' operations as follows:

push:
- If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well.
- Else, push the top element of 'min_stack' again on 'min_stack'.

pop:
- Every time you pop an element from the original stack, pop from 'min_stack' as well.

Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2

original_stack                min_stack
        2                                 1
        1                                 1
        9                                 3
        8                                 3
        5                                 3
        3                                 3
        7                                 7

You can see that at any stage, the 'min_stack' can be queried for the minimum element in the stack.

Rotate a matrix by 90 degrees.

Solution #1: Rotation of a matrix by a certain angle (+90, -90, +180, -180) can be done by a combination of basic operations like transpose, column swapping and row swapping. For example, to rotate a matrix by +90 degrees just transpose it and then swap the columns. Rest of the rotations can be done using a similar approach. Below is the code for +90 degrees rotation,

#define N 5

void printMatrix(int mat[N][N])
{
    int i=0;
    int j=0;

    for(i=0; i < N; i++)
    {
        for(j=0; j < N; j++)
            printf("%d ", mat[i][j]);

        printf("\n");
    }
}

void initMatrix(int mat[N][N])
{
    int i=0;
    int j=0;

    srand(time(NULL));
    for(i=0; i < N; i++)
        for(j=0; j < N; j++)
            mat[i][j] = rand() % 10;
}

void transpose(int mat[N][N])
{
    int i=0;
    int j=0;

    for(i=0; i < N; i++)
    {
        for(j=i; j < N; j++)
        {
            int temp = mat[i][j];
            mat[i][j] = mat[j][i];
            mat[j][i] = temp;
        }
    }
}

void swapCol(int mat[N][N])
{
    int i=0;
    int j=0;

    for(i=0; i < N; i++)
    {
        for(j=0; j < N/2; j++)
        {
            int temp = mat[i][j];
            mat[i][j] = mat[i][N-1-j];
            mat[i][N-1-j] = temp;
        }
    }
}

int main()
{
    int matrix[N][N] = {0, };

    //initialize and print matrix
    initMatrix(matrix);
    printMatrix(matrix);
    
    printf("\n");

    //transpose and swap columns to rotate by +90
    transpose(matrix);
    swapCol(matrix);

    printMatrix(matrix);
    
}

Write a program to find a sub-tree in a Binary Search Tree whose sum is maximum.

Solution #1: Sum of a tree is the sum of all the nodes of that tree. We have to find a sub-tree whose sum is maximum. Clearly, this tree has negative elements as well otherwise the question is trivial and the original tree itself is the answer. Here is the recursive code,

int maxSum(struct node* root, int* max)
{
    if(root == NULL)
        return 0;

    int sum = maxSum(root->left, max) + maxSum(root->right, max) + root->data;

    if(sum > *max)
        *max = sum;

    return sum;
}

int main()
{
    struct node *root;

    insert(&root, -10);
    insert(&root, -20);
    insert(&root, 30);
    insert(&root, -5);
    insert(&root, 40);

    int max=0;

    maxSum(root, &max);
    printf("maxSum = %d\n", max);

    return 0;
}

Write a function to check whether there exists a root to leaf path sum equal to a given number.

Solution #1: Here is the recursive code,

int hasSum(struct node* root, int sum)
{
    if(root == NULL)
        return (sum == 0);

    sum = sum - root->data;

    return hasSum(root->left, sum) || hasSum(root->right, sum);
}

Print all paths from root to leaf in a Binary tree.

Solution #1: To store the path, we need an array and an integer to store the length of the path. Here is the recursive algorithm,

void printAllPaths(struct node* root, int *arr, int len)
{
    if(root == NULL)
        return;

    arr[len++] = root->data;

    if((root->left == NULL) && (root->right==NULL))
    {
        int i=0;
        for(i=0; i < len; i++)
            printf("%d ", arr[i]);
        printf("\n");

        return;
    }

    printAllPaths(root->left, arr, len);
    printAllPaths(root->right, arr, len);
}