Maximum possible score by player 1

Problem: Link

Suppose you are given an array with even number of integers. You and some other player take turns to pick numbers, either the leftmost element or the rightmost element. We have to find the maximum possible score (sum of numbers chosen) by player 1.
For example: if array is 5 8 4 2, then player 1 can choose either 5 or 2. Suppose he chooses 2, then player 2 can choose 5 or 4. Irrespective of what player 2 chooses, in next round player 1 will have chance to choose 8. Thus, maximum possible score by player 1, in this scenario, is (8+2)=10.

Solution:

#include <stdio.h>

#define max(a, b) (a) > (b) ? (a) : (b)
#define min(a, b) (a) < (b) ? (a) : (b)

/* Returns maximum possible score of player1 incase of player2 is dumb */
int maxscoredumb(int a[], int start, int end)
{
    if(start > end)
        return 0;

    if(start == end - 1)
    {
        return max(a[start], a[end]);
    }
    else if(start == end)
    {
        return a[start];
    }

    /* if player1 chooses left */
    int left = a[start];
    {
        int left1 = maxscoredumb(a, start + 2, end); //if player2 chooses start
        int left2 = maxscoredumb(a, start + 1, end - 1); //if player2 chooses end

        left += max(left1, left2); //assuming player2 is dumb, if player2 is smart, we have to take min
    }

    /* if player1 chooses right */
    int right = a[end];
    {
        int right1 = maxscoredumb(a, start + 1, end - 1); //if player2 chooses start
        int right2 = maxscoredumb(a, start, end - 2); //if player2 chooses end

        right += max(right1, right2); //assuming player2 is dumb, if player2 is smart, we have to take min
    }

    return max(left, right);
}


/* Returns maximum possible score of player1 incase of player2 is smart */
int maxscoresmart(int a[], int start, int end)
{
    if(start > end)
        return 0;

    if(start == end - 1)
    {
        return max(a[start], a[end]);
    }
    else if(start == end)
    {
        return a[start];
    }

    /* if player1 chooses left */
    int left = a[start];
    {
        int left1 = maxscoresmart(a, start + 2, end); //if player2 chooses start
        int left2 = maxscoresmart(a, start + 1, end - 1); //if player2 chooses end

        left += min(left1, left2);
    }

    /* if player1 chooses right */
    int right = a[end];
    {
        int right1 = maxscoresmart(a, start + 1, end - 1); //if player2 chooses start
        int right2 = maxscoresmart(a, start, end - 2); //if player2 chooses end

        right += min(right1, right2);
    }

    return max(left, right);
}
int main()
{
    int n;

    scanf("%d", &n);

    int a[n];

    int i;

    for( i = 0; i < n; ++i)
        scanf("%d", a + i);

    printf("Player2 Dumb:  %d\n", maxscoredumb(a, 0, n-1));
    printf("Player2 Smart: %d\n", maxscoresmart(a, 0, n-1));

Given an array of length n, print all sub arrays of length r

#include <stdio.h>

/* Prints all the subarrays of length r */

/* @params: a, given array */
/* @params: n, a length */
/* @params: sub, sub array */
/* @params: r, sub length */
/* @params: i, current index of a */
/* @params: j, current index of sub */

void subarray(int a[], int n, int sub[], int r, int i, int j)
{
    if(j == r) /* current index of sub r, print sub */
    {
        int k;

        printf("( ");

        for(k = 0; k < r; k++)
            printf("%d ", sub[k]);

        printf(")\n");
    }
    else
    {
        if(i < n)
        {
            sub[j] = a[i];

            subarray(a, n, sub, r, i + 1, j + 1); /* Include current element */
            subarray(a, n, sub, r, i + 1, j);     /* Override the current element */
        }
    }

}

int main()
{
    int n, r;

    scanf("%d%d", &n, &r);

    int a[n], sub[r];

    int i;

    for(i = 0 ; i < n; ++i)
        scanf("%d", a + i);

    subarray(a, n , sub, r, 0, 0);
}

To find max palindrome in a given ascii text file

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <ctype.h>

void usage(char *s)
{
    printf("Usage: %s <inputfile>\n", s);
    exit(1);
}

int ispalindrome(const char *s)
{
    const char *p = s + strlen(s) - 1;

    while(s <= p)
    {
        if(*s++ != *p--) return 0;
    }

    return 1;
}

int main(int argc, char* argv[])
{
    if(argc != 2)
        usage(argv[0]);

    int fd = open(argv[1], O_RDONLY);

    if(fd == -1)
    {
        perror(argv[1]);
        exit(1);
    }

    /* Buffer to hold data read from file */
    char buf[64 * 1024];

    /*Buffer to hold current word  */
    char str[4096];

    /*Buffer to hold current max palindrome */
    char palindrome[4096] = {0};
    int maxlen = 0;

    /* Temporay variables */
    char *p = str;
    int n;

    while( (n = read(fd, buf, 64 * 1024)) > 0) /* Read 64k at a time */
    {
        int i = 0;

        while(i < n) /* Divide into words */
        {
            if(isalpha(buf[i])) /*if alpha, Copy to temp buf*/
            {
                *p++ = buf[i];
            }
            else /* end of the word */
            {
                if( ((p - str) > maxlen) && ispalindrome(p) ) /* Check whether it is max palindrome */
                {
                    *p = 0;
                    maxlen = p - str;
                    strcpy(palindrome, str);
                }
                p = str;
            }
            ++i;
        }
    }

    printf("%s %d\n", palindrome, maxlen);
}

internal node count in a binary tree

#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node *left, *right;

}Node;

typedef Node * Tree;

inline int isLeaf(Node *n)
{
    return (n == NULL) || (n->left == NULL && n->right == NULL);
}

int internalNodeCount(Tree t)
{
    if(isLeaf(t))
        return 0;

    return 1 + internalNodeCount(t->left) + internalNodeCount(t->right);

}

minimum depth of a binary tree

#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node *left, *right;
} Node;

typedef Node* Tree;

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

int mindepth(Tree t)
{
    if(t == NULL || (t->left == NULL && t->right == NULL)) return 0;
    return min( 1 + mindepth(t->left), 1 +  mindepth(t->right) );
}

Given an array a[], create another array ar_low[] such that ar_low[i] = number of elements less than or equal to ar[i] in ar[i+1:n-1]

#include <stdio.h>
#include <map>

/* Map to hold an element and its count of number of elements <= */
/* Element is the key and Count of <= is the Value */
typedef std::map<int, int> Map;


/* Inserts the element into map */
/* Returns count of <= */
int insert(Map &m, int el)
{
    /* Find the element >= el */
    Map::iterator mit = m.lower_bound(el);

    /* If el already exists, increment its Count of <= */
    if(mit != m.end() && (mit->first == el ))
    {
        return ++mit->second;
    }

    Map::iterator mit1 = mit;

    /* Increment the count of the greater elements by 1 */
    for(; mit != m.end(); ++mit)
    {
        mit->second++;
    }

    /* Find prev element, set current element count as  prev element count + 1 */
    if(mit1 != m.begin())
    {
        --mit1;
        return m[el] = mit1->second + 1;
    }

    return m[el] = 0;
}

void findCount(int a[], int a_low[], int n)
{
    Map m;

    /* Start from the end */
    while(n--)
    {
        a_low[n] = insert(m, a[n]);
    }
}

int main()
{
    int n;

    scanf("%d", &n);

    int a[n], a_low[n];

    int i;

    for(i = 0; i < n; ++i)
        scanf("%d", a + i);

    findCount(a, a_low, n);

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

    printf("\n");

}

Checking whether given intervals are contiguous or not

Problem: Link

u will be given pairs.. u need to see whether they have any gaps..
ex1: max no:20
pairs: 11-15, 0-5, 18-20, 14-19, 6-13

u can think pairs are like intervals..the above has no gaps..
because 0-5,6-13,11-15,18-20 have all numbers from 0 (min) to 20(max)

ex2: 11-15, 0-5, 18-20, 14-16, 6-13

this have gap as the intervals miss a number from 0 to 20 i.e.,17


Solution:

#include <stdio.h>
#include <stdlib.h>


typedef struct
{
    int minimum, maximum;
}Interval;


/* Compares intervals based on minimum element */
int cmpInterval(const void *a, const void *b)
{
    return ((Interval *)a)->minimum - ((Interval *)b)->minimum;
}


int isIntervalsContiguous(Interval intervals[], int n)
{
        /* Sort the intervals */
        qsort(intervals, n, sizeof(Interval), cmpInterval);


        /* Check whether they are contiguous */
        int i;

        for(i = 1; i < n; i++)
        {
            if(intervals[i].minimum > intervals[i - 1].maximum + 1)
                return 0;
        }

        return 1;
}

int main()
{
    int n;

    scanf("%d", &n);

    Interval intervals[n];

    int i;

    for(i = 0; i < n; ++i)
        scanf("%d%d", &intervals[i].minimum, &intervals[i].maximum);

    printf("isContiguous: %d\n", isIntervalsContiguous(intervals, n));
}

Reverse of a singly linked list using recursion

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int data;
    struct Node *next;
}Node;

typedef Node *list;

list  reverse(list l)
{
    if(!l || !l->next)
        return l;

    list  ret = reverse(l->next);

    l->next->next = l;

    l->next = NULL;

    return ret;

}

list insert(list l, int n)
{
    Node *node = calloc(1, sizeof(Node));
    node->data = n;

    node->next = l;

    return node;
}
void print(list l)
{
    while(l)
    {
        printf("%d ", l->data);
        l = l->next;
    }

    printf("\n");
}




int main()
{
    int n, i;

    scanf("%d", &n);

    list l = NULL;
    for(i = 0; i < n; i++)
        l = insert(l, i);

    printf("Before reverse:\n");
    print(l);

    l = reverse(l);

    printf("After reverse:\n");
    print(l);

}

Construct a binary tree from ancestor matrix

You are given a matrix M[n, n] for a tree with n nodes. In the given matrix M, M[i, j] is true iff node j is an ancestor of node i. Construct the tree from the given matrix.

For example, you are given below matrix.

    1  2  3  4
1  0  1  1  0

2  0  0  1  0

3  0  0  0  0

4  0  1  1  0

You need to construct the below tree. In the constructed tree ancestor relationship should be correct. A node can come on left or right of its parent as you cannot determine this information from the ancestor matrix

Node numbers used in matrix are in bracket
           5(3)
            |     
            |   
          10(2)
         /    \
       /        \
 12(1)          13(4)

Solution:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
}Node;


typedef Node *Tree;

typedef struct Level
{
    int data;
    int level;
    Node *node;
}Level;

int sortLevel(const void *a, const void *b)
{
    const Level *x = a;
    const Level *y = b;

    return x->level - y->level;

}

/*
    constructs a binary tree from ancestor matrix
    returns NULL, if matrix is invalid
*/

Tree constructTreeFromAncestorMatrix(int n, int ancestors[n][n])
{
    //Calculate level of each node (level is the num of ancestor nodes)
    Level levels[n];

    int i, j;

    for(i = 0; i < n; i++)
    {
        levels[i].data = i;
        levels[i].level = 0;

        for(j = 0; j < n; j++)
            levels[i].level += ancestors[i][j];
    }

    //sort nodes based on level
    qsort(levels, n, sizeof(Level), sortLevel);


    //first node level should be zero
    if(levels[0].level != 0)
        return NULL;

    //Construct root node;
    Tree t = (Node *)calloc(1, sizeof(Node));
    t->data = levels[0].data;
    levels[0].node = t;


    //Link nodes to the  ancestor in prev level
    Node *node;

    int prevLevelStart = 0;
    int levelStart = 0;
    int curlevel = 0;

    for(i = 1; i < n; i++)
    {
        //allocate the node
        node = (Node *)calloc(1, sizeof(Node));
        node->data = levels[i].data;
        levels[i].node = node;

        //Check level change
        if(curlevel != levels[i].level)
        {
            prevLevelStart = levelStart;
            levelStart = i;
            curlevel = levels[i].level;
        }

        //find the parent in prev level
        for(j = prevLevelStart; j <levelStart; j++)
        {
            if(ancestors[levels[i].data][levels[j].data])
            {
                //attach to left or right based on free slot
                Node *parent = levels[j].node;
                if(!parent->left)
                {
                    parent->left = node;
                }
                else if(!parent->right)
                {
                    parent->right = node;
                }
                else //invalid binary tree
                {
                    return NULL;
                }

                break;
            }
        }
    }

    return t;
}
void preorder(Tree t)
{
    if(!t) return;

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

    preorder(t->left);
    preorder(t->right);
}


int main()
{
    int n;

    scanf("%d", &n);


    int matrix[n][n];

    int i, j;

    for(i = 0; i < n; ++i)
        for(j = 0; j < n; ++j)
            scanf("%d", &(matrix[i][j]));


    Tree t = constructTreeFromAncestorMatrix(n, matrix);

    preorder(t);

}

Inplace run length encoding of a string

#include <stdio.h>
#include <string.h>

/* 
 * variables 
 * s : pointer pointing to the free slot
 * q : pointer pointing to the starting of the current running character 
 * p : iterator              
 */
void runlength(char *s)
{
    if(!s || !*s)
        return;

    char *q = s, *p = s;

    int len;

    /*iterate while current running character not equal to '' character  */
    while(*q != '')
    {
        /* Advance p while current running character repeats */
        while(*++p == *q);

        /* place the running character in free slot */
        *s++ = *q;

        /* run length */
        len = p - q;

        /* print the run length  */
        if(len > 1)
        {
            if(len < 10)
                *s++ = len + '0';
            else
                s += sprintf(s, "%d", len);
        }

        /*Point q to next character  */
        q = p;
    }

    /*Place '' at the end of s  */
    *s = '';
}



main()
{
    char s[64];

    scanf("%s", s);

    runlength(s);

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