Ronzii's Blog

Just your average geek's blog

Median in a stream of numbers

The brute force algorithm uses a vector and maintains a sorted list. In this case the complexity of adding an element is O(n). Therefore, for n elements, the worst case is O(n^2).
Instead we maintain 2 priority queues i.e minHeap, maxHeap. We keep adding the numbers in both such that the number of elements in the maxheap is at max 1 greater than number of elements in the minHeap. Maintaining this constraint, allows us to get the median in O(1) time. Also, insertion becomes O(logn). Therefore, overall complexity is O(nlogn).

#include <iostream>
#include <queue>
using namespace std;
void insert(priority_queue<int> &maxHeap,priority_queue<int,vector<int>, greater<int> > &minHeap, int n)
{
    if(maxHeap.size()==minHeap.size())
    {
        if(!minHeap.empty() && n>minHeap.top())
        {
            maxHeap.push(minHeap.top());
            minHeap.pop();
            minHeap.push(n);
        }
        else
            maxHeap.push(n);
    }
    else
    {
        if(n<maxHeap.top())
        {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            maxHeap.push(n);
        }
        else
            minHeap.push(n);
    }
}
double getMedian(priority_queue<int> maxHeap,priority_queue<int,vector<int>, greater<int> > minHeap)
{
    int a = minHeap.size();
    int b = maxHeap.size();
    if(a==0 && b==0) return -1;
    if((a+b)%2==0)
        return (double)(minHeap.top() + maxHeap.top())/2;
    else
        return maxHeap.top();
}
int main()
{
    priority_queue<int> maxHeap;
    priority_queue<int,vector<int>, greater<int> > minHeap;
    int a[] = {7,11,17,8,19,2,3,15,16};
    int n = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<n; i++)
    {
        insert(maxHeap,minHeap,a[i]);
        cout<<getMedian(maxHeap,minHeap)<<endl;
    }
    return 0;
}

March 30, 2012 Posted by | C++ | , , , | 1 Comment

Modular Exponentiation

long long modulo(long long a,long long b,long long c)
{
    long long result=1;
    for(int i=0; i<b; i++)
    {
        result = result*a;
        result = result%c;
    }
    return result;
}

long long mulmod(long long a, long long b , long long c)
{
    long long x=0,y=a%c;
    while(b>0)
    {
        if(b & 1)
        {
            x = (x+y)%c;
        }
        y=(y*2)%c;
        b>>=1;
    }
    return x%c;
}
long long modulo2(long long a,long long b,long long c)
{
    long long y=a,x=1;
    printf("%lld %lld %lld\n",b,x,y);
    while(b>0)
    {
        if(b & 1)
        {
            x = mulmod(x,y,c);
        }
        y = mulmod(y,y,c);
        b>>=1;
    }
    return x%c;
}

March 30, 2012 Posted by | C++ | , , , | Leave a comment

AVL Tree

Check out logic of AVL balancing here

#include<iostream>
using namespace std;
struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
};
typedef struct node Node;
int height(Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

Node* newNode(int key)
{
    Node* node = new Node;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}
Node *rightRotate(Node *y)
{
    Node *x = y->left;
    Node *T2 = x->right;
    // Perform rotation
    x->right = y;
    y->left = T2;
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
    return x;
}
Node *leftRotate(Node *x)
{
    Node *y = x->right;
    Node *T2 = y->left;
    // Perform rotation
    y->left = x;
    x->right = T2;
    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
    return y;
}
int getBalance(Node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
Node* insert(Node* node, int key)
{
    if (node == NULL)
        return(newNode(key));
    if (key < node->key)
        node->left  = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    node->height = max(height(node->left), height(node->right)) + 1;
    int balance = getBalance(node);
    // If this node becomes unbalanced, then there are 4 cases
    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}
void preOrder(Node *root)
{
    if(root != NULL)
    {
        cout<<root->key<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}
int main()
{
    Node *root = NULL;
    root = insert(root, 15);
    root = insert(root, 22);
    root = insert(root, 35);
    root = insert(root, 45);
    root = insert(root, 55);
    root = insert(root, 30);

    /* The constructed AVL Tree would be
              35
             /  \
           22   45
          /  \     \
         15  30    55
    */
    preOrder(root);

    return 0;
}

March 30, 2012 Posted by | C++, Data Structures | , , , , | Leave a comment

Finding duplicates in O(n)

Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.

Goal : To find these repeating numbers in O(n) and using only constant memory space.

#include <iostream>
using namespace std;
void duplicates(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        while(a[a[i]]!=a[i])
            swap(a[a[i]],a[i]);
    }
    for (int i = 0; i < n; i++)
        if (a[i] != i)
            cout<<a[i]<<" ";
}
int main()
{
    int x[] = {1, 2, 3, 1, 3, 0, 6};
    int n = sizeof x / sizeof x[0];
    duplicates(x, n);
    return 0;
}

March 30, 2012 Posted by | C++ | , , , , | Leave a comment

Ceiling and Floor Search

#include <iostream>
using namespace std;
int ceilSearch(int a[], int low, int high, int x)
{
    if(x<a[low]) return low;
    if(x>a[high]) return -1;
    int mid = (low+high)/2;
    if(a[mid]==x) return mid;
    /* If x is smaller than arr[mid], then either arr[mid]
    is ceiling of x or ceiling lies in arr[mid-1...high] */
    else if(x<a[mid])
    {
        if(x>=a[mid-1])
            return mid;
        else
            ceilSearch(a,low,mid-1,x);

    }
    /* If x is greater than arr[mid], then either arr[mid + 1]
        is ceiling of x or ceiling lies in arr[mid+1...high] */
    else
    {
        if(x<=a[mid+1])
            return mid+1;
        else
            ceilSearch(a,mid+1,high,x);

    }
}
int floorSearch(int a[], int low, int high, int x)
{
    if(x<a[low]) return -1;
    if(x>a[high]) return high;
    int mid = (low+high)/2;
    if(x==a[mid]) return mid;
    else if(x<a[mid])
    {
        if(x>=a[mid-1])
            return mid-1;
        else
            floorSearch(a,low,mid-1,x);
    }
    else
    {
        if(x<=a[mid+1])
            return mid;
        else
            floorSearch(a,mid+1,high,x);
    }
}
int main()
{
    int arr[] = {1, 2, 8, 10, 10, 12, 19};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x,index;
    while(1)
    {
        cin>>x;
        index = ceilSearch(arr, 0, n-1, x);
        if(index == -1)
            cout<<"Ceiling of "<<x<<" doesn't exist in array \n";
        else
            cout<<"Ceiling of "<<x<<" is "<<arr[index]<<endl;
        index = floorSearch(arr, 0, n-1, x);
        if(index == -1)
            cout<<"Floor of "<<x<<" doesn't exist in array \n";
        else
            cout<<"Floor of "<<x<<" is "<<arr[index]<<endl;

    }
    return 0;
}

March 30, 2012 Posted by | C++ | , , , , | Leave a comment