Ronzii's Blog

Just your average geek's blog

The Longest Consecutive Sequence in an unsorted array

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
void LongestConsecutiveSequence(vector<int> a)
{
    unordered_map<int,bool> h;
    int n = a.size();
    for(vector<int>::const_iterator iter=a.begin(); iter!=a.end(); iter++)
    {
        if(h.count(*iter)==0)
            h.insert(pair<int,bool>(*iter,false));
    }
    int count,left_key,right_key,max=0,lb=0,ub=0;
    for(vector<int>::const_iterator iter=a.begin(); iter!=a.end(); iter++)
    {
        if(!h.find(*iter)->second)
        {
            count = 1;
            left_key = *iter -1;
            unordered_map<int,bool>::iterator temp = h.find(left_key);
            while(temp!=h.end())
            {
                temp->second = true;
                count++;
                temp = h.find(--left_key);
            }
            right_key = *iter + 1;
            temp = h.find(right_key);
            while(temp!=h.end())
            {
                temp->second = true;
                count++;
                temp = h.find(++right_key);
            }
            if(max<count)
            {
                max = count;
                lb = left_key + 1;
                ub = right_key - 1;
            }
        }
    }
    cout<<"Size:"<<max<<endl;
    for(int i=lb; i<=ub; i++)
    {
        cout<<i<<" ";
    }
}
int main ()
{
    int a[] = {101,2,3,104,5,103,9,102};
    int n = sizeof(a)/sizeof(a[0]);
    vector<int> v(a,a+n);
    LongestConsecutiveSequence(v);
    return 0;
}

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

The Least K Numbers

We maintain a max heap of size k and keep inserting/deleting values according the largest value in the heap

#include <iostream>
#include <vector>
#include <set>
using namespace std;
void GetLeastNumbers(const vector<int>& data, multiset< int,greater<int> >& answer, int k)
{
    answer.clear();
    multiset<int, greater<int> >::iterator  leastIterator;
    for(vector<int>::const_iterator iter = data.begin(); iter!=data.end(); iter++)
    {
        if(answer.size()<k)
        {
            answer.insert(*iter);
        }
        else
        {
            leastIterator = answer.begin();
            if(*(answer.begin())>*iter)
            {
                answer.erase(leastIterator);
                answer.insert(*iter);
            }
        }
    }
}
int main()
{
    int a[] = {3,1,23,4,6,2,56,7};
    int size = sizeof(a)/sizeof(a[0]);
    vector<int> v(a,a+size);
    multiset< int,greater<int> > answer;
    int k = 4;
    GetLeastNumbers(v,answer,k);
    for(multiset<int, greater<int> >::iterator  x=answer.begin(); x!=answer.end(); x++)
    {
        cout<<*x<<" ";
    }
    return 0;
}

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

Kruskal’s algorithm

Kruskals Algorithm is used to find the minimum spanning tree for a connected weighted graph and is an ideal greedy algorithm. Additionally, I’ve calculated the total weight of the Minimum Spanning Tree.

Algorithm

1. Take a Forest or a set of edges as input.

2. Create sets for each vertices. What I’ve done is merely kept track of the parent of each list i.e if the parent is same then they belong to the same list.

3. Now, Sort all the edges in non-decreasing order of their weights.

4. Extract the smallest edge (u,v). Compare whether they belong to the same set or not.  If the edge connects two different trees add it to the MST otherwise discard that edge.

The time complexity of this algorithm is O(E log V) where E is number of edges and V is number of vertices.

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#define MAX 10001
#define edge pair<int,int>
using namespace std;
vector< pair<int, edge > > Graph,MST;
int n,e,parent[MAX];
void initialize(int n)
{
    for(int i=1; i<=n; i++)
    {
        parent[i] = i;
    }
    MST.clear();
    Graph.clear();
}
int findSet(int x, int *parent)
{
    if(x!=parent[x])
    {
        parent[x] = findSet(parent[x],parent);
    }
    return parent[x];
}
void kruskal()
{
    sort(Graph.begin(),Graph.end());
    int total = 0;
    for(int i=0; i<e; i++)
    {
        int pu = findSet(Graph[i].second.first,parent);
        int pv = findSet(Graph[i].second.second,parent);
        if(pu!=pv)
        {
            total+=Graph[i].first;
            MST.push_back(Graph[i]);
            parent[pu] = parent[pv];
        }
    }
    cout<<total<<"\n";
}
int main()
{
    cin>>n>>e;
    initialize(n);
    int u,v,w;
    for(int i=0; i<e; i++)
    {
        cin>>u>>v>>w;
        Graph.push_back(pair<int, edge>(w,edge(u,v)));
    }
    kruskal();
    return 0;
}

July 7, 2011 Posted by | C++ | , , , | Leave a comment

Dijkstra’s algorithm using STL

Dijkstra’s algorithm requires a priority queue so I have used STL’s inbuilt priority queue functions. The class Prioritize ensures that the queue remains sorted according to the first value of the pair<int,int> object

Algorithm
1. Assign to every node a distance value: set it to zero for our initial node and to infinity(999) for all other nodes. Mark all nodes as unvisited.
2. Set initial source as current.
3.  Consider all its unvisited neighbors and calculate their distance. For example, if current node (A) has distance of 1, and an edge connecting it with another node (B) is 2, the distance to B through A will be 1+2=3
4.When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal
5. The next current node will be the node with the lowest distance in the unvisited set that is the topmost element of the priority queue.

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define pp pair<int,int>
using namespace std;
class Prioritize
{
public:
    int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second < p2.second;
    }
};
int main()
{
    priority_queue<pp, vector<pp > , Prioritize > Q;
    int n;
    cin>>n;
    vector< pp > G[n+1];
    int e,u,v,w;
    cin>>e;
    for(int i=0;i<e;i++)
    {
        cin>>u>>v>>w;
        G[u].push_back(pp(v,w));
        G[v].push_back(pp(u,w));
    }
    int s;
    cin>>s;
    int d[n+1];
    for(int i=1;i<=n;i++)
    {
        d[i] = 999;
    }
    d[s] = 0;
    Q.push(pp(s,d[s]));
    while(!Q.empty())
    {
        u = Q.top().first;
        Q.pop();
        int size = G[u].size();
        for(int i = 0 ; i < size ; i++)
        {
            v = G[u][i].first;
            w = G[u][i].second;
            cout<<u<<" "<<v<<" "<<w<<endl;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push(pp(v,d[v]));
            }
        }
    }
    for(int i=1; i<=n; i++) printf("Node %d, min weight = %d\n", i, d[i]);
    return 0;
}

July 7, 2011 Posted by | C++ | , , , , | 2 Comments