Kth Largest from an infinite stream

Problem:
 Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.
For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30 and 23.

Solution:

• Create a min-heap of size K.
• Fill the heap with first K elements from the stream
• Once K elements are filled Build-heap from those elements
• now ROOT will have the smallest of K largest elements of the stream.
• when the next element in the stream is available check NO > ROOT.
• If so, replace ROOT with that Number and call Min-Heapify of ROOT.
• At any point Stream_length >= K we can give the Kth Largest by Returning the ROOT of MIN-HEAP.

Complexity: O(N + log(K) ),where N is the length of Stream

Code:

void MinHeapify(int a[],int i,int n)
{
    int left=0;
    int right=0;
    int max=0;
    while(i<=n/2-1)
    {
        left=2*i+1;
        right=2*i+2;
        max=i;
        if(left<n && a[left]<a[max])
            max=left;
        if(right<n && a[right]<a[max])
            max=right;
        if(max!=i)
        {
            a[max]=a[max]^a[i];
            a[i]=a[max]^a[i];
            a[max]=a[max]^a[i];
        }
        else
            break;
        i=max;
    }
}
 
void BuildMinHeap(int a[],int n)
{
    int i=0;
    for(i=n/2-1;i>=0;i--)
        MinHeapify(a,i,n);
}
 
findKthLargest(int I[],int N,int k)
{
    int i=0;
    int a[k];
    for(i=0;i<N;i++)
    {
        if(i<k-1)
        {
            a[i]=I[i];
        }
        else if(i==k-1)
        {
            a[i]=I[i];
            BuildMinHeap(a,k);
        }
        else
        {
            if(I[i]>a[0])
            {
                a[0]=I[i];
                MinHeapify(a,0,k);
            }
        }
    }
    printf("Kth Largest Element:%d",a[0]);
}

Delete alternate nodes of a Linked List

Problem:

Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->2->3->4->5 then your function should convert it to 1->3->5, and if the given linked list is 1->2->3->4 then convert it to 1->3.
Solution:

•   Have two pointers p and q

• Initially p points head and q points to link of p i.e 2nd node (if exists).
• Make the link of p to point to link of q
• free q
• move p to its link i.e next node
• move q to next node of p
• loop until p or q becomes NULL.

Complexity: O(n)
Code:

List *deletealternative(List *head)
{
    if(head==NULL)
        return NULL;
    List *p=head;
    List *q=p->link;
    
    while(p!=NULL && q!=NULL)
    {
        p->link=q->link;
        free(q);
        p=p->link;
        if(p!=NULL)
            q=p->link;
    }
    return head;
}

A program to check if a binary tree is BST or not

Problem:
 A binary search tree (BST) is a node based binary tree data structure which has the following properties.
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
From the above properties it naturally follows that:
• Each node (item in the tree) has a distinct key.

Solution:

• Start from root with min = -INF and max = + INF
• At each node check whether node's data is in range [min,max]
• If not it violates binary search tree,return 0. 
• you can use the below isbst() trace,

 
Complexity: worst case - when it is a bst, O(n) where n is the  number of nodes.
Code:

int isBSTUtil(Tnode *root,int min,int max)
{
    if(root==NULL)
        return 1;
    if(root->data < min || root->data >= max)
        return 0;
    return isBSTUtil(root->left,min,root->data) && isBSTUtil(root->right, root->data + 1, max);
}
 
int isBST(Tnode *root)
{
    int min=1<<((sizeof(int)*8)-1);
    int max=~min;
    //printf("min=%d max=%d",min,max);
    
    return isBSTUtil(root,min,max);
}

Cut Gold Puzzle

You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? 

Solution: 

            Let us consider the gold  bar like this, 

 Lets split the chain as,

 
           Day 1: Give A.(+1)
           Day 2: Get back A, give B.(-1, +2)
           Day 3: Give A.(+1)
           Day 4:Get back A and B, give C. (-2,-1,+4)
           Day 5:Give A. (+1)
           Day 6:Get back A, give B. (-1,+2)
           Day 7:Give A.(+1)