Ronzii's Blog

Just your average geek's blog

Quick Select

Find the kth smallest element of an array using kth order statistic

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int partition(int a[], int left, int right)
{
    int last = left;
    int key = a[left];
    for(int j=left+1; j<=right; j++)
    {
        if(a[j]<key)
        {
            last++;
            swap(a[last],a[j]);
        }
    }
    swap(a[left],a[last]);
    return last;
}
int findRank(int a[],int left, int right, int rank)
{
    int leftEnd  = partition(a,left,right);
    int leftSize = leftEnd - left + 1;
    if(leftSize==rank+1)
        return a[leftEnd];
    else if(rank<leftSize)
        return findRank(a,left,leftEnd-1,rank);
    else
        return findRank(a,leftEnd+1,right,rank-leftSize);
}
int main()
{
    srand(time(NULL));
    int a[] = {3,4,1,7,8,9,34};
    int n = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<n; i++)
        cout<<findRank(a,0,n-1,i)<<" ";
    return 0;
}
Advertisements

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

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

Random Number Generation

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int rand5()
{
    return rand()%5;
}
int rand7()
{
    int vals[5][5] =
    {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}
int main()
{
    srand(time(NULL));
    cout<<rand7();
    return 0;
}

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

Card Shuffling

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
void shuffle(vector<int> &v)
{
    srand(time(NULL));
    int n = v.size();
    for(int i=0; i<n; i++)
    {
        // Cards with index i-1 have already been chosen
        // Discard old cards and calculate new random index using the remaining n-i cards
        int index = i + rand()%(n-i);
        swap(v[i],v[index]);
    }
}
void print(vector<int> v)
{
    for(int i=0; i<v.size(); i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    int a[] = {1,2,3,4,5};
    int size = sizeof(a)/sizeof(a[0]);
    vector<int> v(a,a+size);
    shuffle(v);
    print(v);
    return 0;
}

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