Binary tree to Single Linked List containg sum of all nodes at the same level

Problem

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

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

/*Data structures*/
typedef struct TreeNode
{
    struct TreeNode *left, *right;
    int data;
}TreeNode;

typedef TreeNode * Tree;

typedef struct ListNode
{
    struct ListNode *next;
    int data;

}ListNode;

typedef ListNode *List;

/*End of data structures*/

/*
*Function which collapses all the nodes at a level in a binary tree to one Listnode
*/
void BinTreeToLinkedList(Tree t, ListNode *parent)
{
    if(t == NULL)
        return;

    ListNode *node = parent->next;

    if(node == NULL)
    {
        node = calloc(sizeof(ListNode), 1);
        parent->next = node;
    }

    node->data += t->data;
    
    BinTreeToLinkedList(t->left, node); 
    BinTreeToLinkedList(t->right, node);    
}


/*Utilities*/

inline  TreeNode * makeTreeNode(int data)
{
    TreeNode *n = calloc(sizeof(TreeNode), 1);
    n->data = data;

    return n;
}

inline void printList(List l)
{
    while(l)
    {
        printf("%d ", l->data);
        l = l->next;
    }
    printf("\n");
}

int main()
{
    /*level 0*/
    Tree t = makeTreeNode(10);

    /*level 1*/
    t->left = makeTreeNode(20);
    t->right = makeTreeNode(30);


    /*level 2*/
    t->left->left = makeTreeNode(40);
    t->left->right = makeTreeNode(70);
    t->right->left = makeTreeNode(50);
    t->right->right = makeTreeNode(60);

    /*level 3*/
    t->left->right->left = makeTreeNode(70);
    t->right->right->left = makeTreeNode(60);
    t->right->right->right = makeTreeNode(160);

    /*Empty List head*/
    ListNode head = {NULL, 0};

    /*Convert tree to list*/
    BinTreeToLinkedList(t, &head);

    /*print list*/
    printList(head.next);


    return 0;
}

Javascript Set

As Most of the Javascript Set implementations have flaw in comparing objects, as javascript  compares identities of the objects, not actual values. Here is my implementation with true   object  value comparison.

/*Constructor: Takes array or implicit null as an argument*/
function Set(arr)
{
    if(arr == null)
        this._array = [];
    else
    {
        if(arr.constructor == Array)
            this._array = arr;
        else 
            this._array = [arr];
    }
}

Set.prototype = 
{    
    /*Compares the type of the objects and actual values, rather than object identity*/
    _compare : function(i, j )
    {
        var itype = typeof(i);
        var jtype = typeof(j);

        /*Both are primitives, compare directly*/
        if(itype != 'object' && jtype != 'object')
            return i === j;

        /*Both are objects*/
        if(itype == 'object' && jtype == 'object')
        {
            if(i.constructor != j.constructor) /*Check whether, they are of same type */
                 return false;
            
            for(var k in i)  /*For each value compare recursively*/
            {
                if(! k in j || !this._compare(i[k], j[k]))  return false;                
            }
            return true;
        }

        /*comparison of primitive form and object form*/
        if(itype == 'object')
            return i.valueOf() === j;
                
        return i === j.valueOf();
    },

    /*Returns values of the set*/
    values: function()
    {
        return this._array;
    },

    /*Returns the size of the set*/
    size : function()
    {
        return this._array.length;
    },
    
    /*Checks whether Set has an element or not*/
    contains : function(n)    
    {
        for(var i in this._array)
        {
            if(this._compare(this._array[i], n) )
                return true;
        }

        return false;
    },


    /*adds the element to the set, if it is not there */
    add: function(n)
    {
        if(!this.contains(n))
            this._array.push(n);
    },


    /*removes the element from the set, if it is there*/
    remove: function(n)
    {
        for(var i in this._array)
        {
            if(this._compare(this._array[i], n) )
            {
                this._array.splice(i, 1);
                return;
            }
        }
    },

    /*Returns new set containing union of the two*/
    union: function(other)
    {
        var result;
        var arr;

        if(this.size() > other.size())
        {
            result = new Set( this._array.slice(0) );
            arr = other._array;

        }
        else
        {
            result = new Set(other._array.slice(0));    
            arr = this._array;

        }

        for(var i in arr)
        {
            if( !result.contains(arr[i]))
                result.add(arr[i]);
                
        }

        return result;
    },

    /*Returns new set containing intersection of the two*/
    intersection: function(other)
    {
        var result = new Set();
        var arr, set;

        if(this.size() < other.size())
        {
            arr = this._array;
            set = other;

        }
        else
        {
            arr = other._array;
            set = this;

        }

        for(var i in arr)
        {
            if( set.contains(arr[i]))
                result.add(arr[i]);
                
        }

        return result;
    },

    /*Checks this is subset of other*/
    isSubsetOf: function(other)
    {
        for(var i in this._array)
        {
            if(!other.contains(this._array[i]))
                return false;
        }    

        return true;        
    },

    /*Checks whether two sets are equal*/
    equals : function(other)
    {
        return this.isSubsetOf(other) && other.isSubsetOf(this);
    },

    /*Subtracts other from this*/
    minus : function(other)
    {
        var arr = this._array.slice(0);    
    
        for(var i in arr )
        {
            if(other.contains(arr[i]))
                arr.splice(i, 1);
        }

        return new Set(arr);
    }    
};

reverse () in doubly linked list

Problem

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

typedef struct DoubleLinkedListNode
{
    const char *s;
    struct DoubleLinkedListNode *prev, *next;

}DoubleLinkedListNode;

typedef DoubleLinkedListNode *DoubleLinkedList;


DoubleLinkedList insertLastNode(DoubleLinkedList l, const char *elem)
{
    if(!l)
    {
        l = calloc(sizeof(DoubleLinkedListNode), 1);
        l->s = elem;
    }
    else
    {
        DoubleLinkedListNode *node = l;

        while(node->next)
            node = node->next;

        node->next =  calloc(sizeof(DoubleLinkedListNode), 1);
        node->next->s = elem;
        node->next->prev = node;
    }

    return l;
}

void print(DoubleLinkedList l)
{
    while(l)
    {
        printf("%s ", l->s);
        l = l->next;
    }

    printf("\n");
}


DoubleLinkedList reverse(DoubleLinkedList l)
{
    if(l == NULL || l->next == NULL)
        return l;

    DoubleLinkedList l1 = reverse(l->next);
    DoubleLinkedListNode *tmp = l->next;

    tmp->next = l;
    l->next = l->prev;
    l->prev = tmp;


    return l1;
}

DoubleLinkedList reverseIterative(DoubleLinkedList l)
{
    if(l == NULL || l->next == NULL)
    {
        printf("No reverse required");
        return l;
    }

    DoubleLinkedListNode *tmp, *ret;
    while(l)
    {
        tmp = l->next;

        l->next = l->prev;
        l->prev = tmp;

        ret = l;
        l = tmp;
    }


    return ret;
}


int main()
{
    DoubleLinkedList l = NULL;

     l = insertLastNode(l, "geeks");
     l = insertLastNode(l, "for");
     l = insertLastNode(l, "geeks");
     l = insertLastNode(l, "org");
     l = insertLastNode(l, "double");

     print(l);

     l = reverseIterative(l);

     printf("\n\nAfter Reverse \n");

     print(l);
}

concatenation of two strings omitting overlapping string

Problem

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

char *Strcat(char *dst, const char *src)
{
        size_t dstLen = strlen(dst);
        size_t srcLen = strlen(src);


        char *p  = dst + dstLen + srcLen;  /* Pointer to the end of the concatenated string */

        const char *q  = src + srcLen - 1; /* Pointer to the last character of the src */

        char *r  = dst + dstLen - 1;      /* Temp Pointer to the last character of the dst*/

        char *end = r;                  /* Permenent Pointer to the last character of the dst*/

        *p = '';  /*terminating the concatened string with NULL character */


        while(q >= src)   /*Copy src in reverse*/
        {
                if(*r == *q) /*Till it matches with the src, decrement r */
                {
                        r--;
                }
                else

                {

                        r = end;

                        if(*r == *q) 
                        {

                          r--;
                        }
                }
                 *p-- = *q--;         }          while(r >= dst) /*Copy dst, ending with r */                *p-- = *r--;         return p + 1;} int main(){        char a[64] = "hello everyone";        const char *b  = "everyone is good";         printf("%s\n", Strcat(a, b));
   
        return 0;

}

			

find out all the elements in a sorted integer array whose value is equal to index of the array

#include <stdio.h>

int searchindex(int a[], int minindex, int maxindex, int ret[], int index)
{
    if(minindex > maxindex )
        return index;

    int mid = (minindex + maxindex) / 2;

    if(mid == a[mid])
    {
        ret[index++] = mid;
        index = searchindex(a, mid+1, maxindex, ret, index);
        index = searchindex(a,  minindex, mid-1, ret, index);

        return index;
    }
    else if(mid < a[mid])
        maxindex = mid - 1;
    else
        minindex = mid + 1;

    return searchindex(a, minindex, maxindex, ret, index);

}


int main()
{
    int n;

    scanf("%d", &n);

    int a[n];

    int i;


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

    int ret[n];

    int index = searchindex(a, 0, n - 1, ret, 0);

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

    printf("\n");
}

To find best days for sell and buy, if array of stock prices given

Problem: Link

#include <stdio.h>
/* 
 *  buy day j and sell day i where  max(a[i] - a[j]) and i > j
 *  */

typedef struct
{
    int buy, sell, profit;
}Return;

Return maxprofit(int a[], int n)
{
    Return r = {n-1, n-1, 0};

    Return tmp = r;
    n--;

    while(n--)
    {
        if(a[n] < a[tmp.buy])
            tmp.buy = n;

        if(a[n] > a[tmp.sell])
            tmp.buy = tmp.sell = n;

        if(tmp.buy < tmp.sell)
        {
            tmp.profit = a[tmp.sell] - a[tmp.buy];
            if(r.profit < tmp.profit)
                r = tmp;
        }
    }

    return r;
}

int main()
{
    int n;
    scanf("%d", &n);

    int i;
    int a[n];

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

    Return r = maxprofit(a, n);

    printf("buy on: %d and sell on: %d and profit: %d\n", r.buy, r.sell, r.profit);
}

Queue to find min in O(1)

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

/* struct to hold the actual data */
typedef struct node
{
    int data;
    struct node *next;
    struct node *nextMin;

}Node;

/* Queue head */
typedef struct
{
    Node *head;
    Node *tail;
    Node *min;

}Queue;


/* Initialize the queue */
inline void initQueue(Queue *q)
{
    q->tail = q->head = q->min = NULL;
}

/*check for queue empty */
inline int isEmpty(Queue *q)
{
    return !q || q->head == NULL;
}

/* Deallocates the queue */
void endQueue(Queue *q)
{
    if(isEmpty(q))
        return;

    Node *h = q->head;
    Node *tmp;

    while(h)
    {
        tmp = h;
        h = h->next;
        free(tmp);
    }
}

/* inserts element at the end */
void enqueue(Queue *q, int el)
{
    if(!q)
        return;

    Node *node = calloc(sizeof(Node), 1);
    assert(node != NULL);
    node->data = el;

    if(!q->head) /* if Q empty */
    {
        q->min = q->head = q->tail = node;
    }
    else
    {

     
        if(q->min->data >= el) /*Update current min */
        {
            q->min = node;
        }
        else
        {
            Node *min = q->min;
            
            while(min)
            {
                if(!min->nextMin || min->nextMin->data >= el)
                {
                    min->nextMin = node;
                    break;
                }
                min = min->nextMin;
            }
        }
        q->tail->nextMin = q->tail->next = node; /* attach at the end */        q->tail = node; /* move tail */     } } /*pops the element at the beginning */int dequeue(Queue *q, int *el){    if(isEmpty(q))        return -1;     *el = q->head->data;     Node *tmp = q->head;     q->head = q->head->next; /* move head */     if(q->min == tmp) /* if head is the min, move the min */    {        q->min = tmp->nextMin;    }     free(tmp);     return 0;} /* Returns the minimum element in Q */inline int findMin(Queue *q, int *el){    if(isEmpty(q))        return -1;     *el = q->min->data;     return 0;} /* prints the queue to stdout */void printQueue(Queue *q){    if(isEmpty(q))        return;     Node *h = q->head;     while(h)    {        printf("%d ", h->data);        h = h->next;    }    printf("\n");} int main(){    Queue q;     initQueue(&q);     int choice;    int el;     int n;     scanf("%d", &n);     while(n--)    {        scanf("%d", &el);        enqueue(&q, el);    }      while(1)    {        printf("\n\t0: enqueue\n");        printf("\t1: dequeue\n");        printf("\t2: findMin\n");        printf("\t3: printQ\n");        printf("\t4: exit\n");        printf("\tEnter your choice: ");         scanf("%d", &choice);         switch(choice)        {            case 0:                printf("\n\tEnter Element:");                scanf("%d", &el);                enqueue(&q, el);                break;             case 1:                if(dequeue(&q, &el) == 0)                    printf("%d\n", el);                else                    printf("\nQueue empty\n");                 break;             case 2:                if(findMin(&q, &el) == 0)                    printf("%d\n", el);                else                    printf("\nQueue empty\n");                break;             case 3:                printQueue(&q);                break;             case 4:                return 0;        }    }     endQueue(q);}
			

Given array of positive integer, find the largest number c such that c=a+b

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


/* Comparator function */
int intCompare(int *a, int *b)
{
    return *a - *b;
}

int maxsum(int a[], int n)
{
    /* Sort the array */
    qsort(a, n, sizeof(int), intCompare);

    int i, j;

    while(n--)
    {
        i = 0;
        j = n - 1;

        /* Check whether 0 <= i <= n-1, 0 <= j <= n-1 exists such that a[i] + a[j] = a[n] */

        while(i < j)
        {
            int sum = a[i] + a[j];

            if(sum == a[n])
                return sum;

            if(sum > a[n])
                j--;
            else
                i++;
        }
    }

    /* Can't find any such num */
    return -1;
}