Monday 8 December 2014

Bytelandian gold coins

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?

Input

The input will contain several test cases (not more than 10). Each testcase is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your coin.

Output

For each test case output a single line, containing the maximum amount of American dollars you can make.

Recursion ::

// n < 12 : We may get n or less than n when we do exchange.. so dont exchange when n<12

// 5 : 2+1+1 = 4, 6 : 3+2+1=6

//n >= 12 Similarly : We may get more than n or n when we do exchange.. so do exhange whenever n>=12

//Memoize intermediate results using a map.

package SPOJ;/**
 * Created by seesunda on 12/9/2014.
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
// n < 12 : We may get n or less than n when we do exchange.. so dont exchange when n<12
// 5 : 2+1+1 = 4, 6 : 3+2+1=6

//n >= 12 Similarly : We may get more than n or n when we do exchange.. so do exhange whenever n>=12

//Memoize intermediate results using a map.
class coins {

    static HashMap<Long,Long> map = new HashMap<Long, Long>();

    public static void main(String[] args) throws IOException {
        BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String s = "";
        while((s=inp.readLine())!=null) {
            long n = Long.parseLong(s);
            out.println(getMax(n));
        }
        out.flush();
    }

    public static long getMax(long n) {
        if(n < 12)
            return n;

        if(map.containsKey(n))
            return map.get(n);

        long chg = getMax(n/2) + getMax(n/3) + getMax(n/4);
        map.put(n,chg);

        return chg;
    }
}

Friday 5 December 2014

Disjoint-Set Data Structure UNION-FIND

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. Note that we have discussed an algorithm to detect cycle. This is another method based on Union-Find. This method assumes that graph doesn’t contain any self-loops.

We can keeps track of the subsets in a 1D array, lets call it parent[].

Applications:

Detect Cycle in a an Undirected Graph

Minium Spanning Tree - Kruskals

The implementation of union() and find() is naive and takes O(n) time in worst case.
These methods can be improved to O(Logn) using Union by Rank or Height - Next post.

Union-Find in O(n) :

package g4g.Graph;/**
 * Created by seesunda on 12/6/2014.
 */

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.InputStream;

class UFinN {

    int V;
    int E;
    Edge[] edges;

    UFinN(int v, int e) {
        this.V = v;
        this.E = e;
        this.edges = new Edge[e];
        for(int i=0;i<e;i++)
            edges[i] = new Edge();
    }


    class Edge {
        int src;
        int dest;
    }

    public static void main(String[] args) {
        UFinN u = new UFinN(3,3);

        // add edge 0-1
        u.edges[0].src = 0;
        u.edges[0].dest = 1;

        // add edge 1-2
        u.edges[1].src = 1;
        u.edges[1].dest = 2;

        // add edge 0-2
        u.edges[2].src = 0;
        u.edges[2].dest = 2;

        if(hasCycle(u))
            System.out.println("Detected Cycle");
        else
            System.out.println("No Cycle");

    }


    public static boolean hasCycle(UFinN u) {
        int[] parent = new int[u.V];
        Arrays.fill(parent, -1);

        for(int i=0;i<u.E;i++) {
            int x = find(parent,u.edges[i].src);
            int y = find(parent,u.edges[i].dest);
            //Belongs to same set

            if(x == y) {
                return true;
            }
            union(parent,x,y);

        }
        return false;
    }

    public static int find(int[] parent,int vertex) {
        while(parent[vertex] != -1)
            vertex = parent[vertex];
        return vertex;
    }

    public static void union(int[] parent,int x,int y) {
        int xset = find(parent,x);
        int yset = find(parent,y);
        parent[xset] = yset;
    }
}

Friday 21 November 2014

Java Collections

http://javarevisited.blogspot.in/2011/11/collection-interview-questions-answers.html

http://javarevisited.wordpress.com/2011/11/26/arraylist-hashmap-and-collection-interview-questions-answers-in-java-2/

Java Concurrency and Threading

http://javarevisited.blogspot.in/2014/07/top-50-java-multithreading-interview-questions-answers.html

http://java67.blogspot.sg/2012/08/5-thread-interview-questions-answers-in.html

Sunday 16 November 2014

Longest and Shortest path from a given source vertex to all vertices

Shortest Path:

For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra’s algorithm. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.

We initialize distances to all vertices as infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.

Longest path:
We initialize distances to all vertices as minus infinite and distance to source as 0, then we find topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.
Reference :: GeeksforGeeks

Java implementation:

package g4g.Graph;/**
 * Created by seesunda on 11/15/2014.
 */

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;
import java.io.InputStream;

class AdjNode {
    int v;
    int weight;

    AdjNode(int v,int w) {
        this.v = v;
        this.weight = w;
    }
}

class Pathgraph {
    int v;
    ArrayList<AdjNode>[] alist;
    int[] indegree;

    Pathgraph(int v) {
        this.v = v;
        this.alist = new ArrayList[v];
        this.indegree = new int[v];
    }

    public void initilaize(){
        for(int i=0;i<alist.length;i++)
            alist[i] = new ArrayList<AdjNode>();
    }

    public void addEdge(int u,int v,int weight) {
        AdjNode node = new AdjNode(v,weight);
        alist[u].add(node);
        indegree[v]++;
    }

    public ArrayList<Integer> TopoSort() {
        Queue<Integer> q = new LinkedList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        boolean[] visited = new boolean[alist.length];

        for(int i=0;i<indegree.length;i++) {
            if(indegree[i] == 0) { q.add(i);  visited[i] = true; break;}
        }

        while(!q.isEmpty()) {
            int u = q.poll();

            result.add(u);
            for(int i=0;i<alist[u].size();i++) {
                AdjNode n = alist[u].get(i);
                int v = n.v;
                indegree[v]--;
            }

            for(int i=0;i<alist.length;i++) {
                if(!visited[i] && indegree[i] == 0) { q.add(i); visited[i] = true;}
            }
        }

        return result;
    }

    public int[] longestPath(int s) {
        int[] dist = new int[alist.length];
        Arrays.fill(dist,Integer.MIN_VALUE);

        dist[s] = 0;

        ArrayList<Integer> topoOrder = TopoSort();
        for(int i=s;i<topoOrder.size();i++) {
            int u = topoOrder.get(i);
            //System.out.println(u);
            for(int j=0;j<alist[u].size();j++) {
                AdjNode node = alist[u].get(j);
                int v = node.v;
                int weight = node.weight;
                //System.out.println(v + " " + weight);
                if(dist[v] < dist[u] + weight ) dist[v] = dist[u]+weight;
            }
        }

        return dist;

    }

    public int[] shortestPath(int s) {
        int[] dist = new int[alist.length];
        Arrays.fill(dist,Integer.MAX_VALUE);

        dist[s] = 0;

        ArrayList<Integer> topoOrder = TopoSort();
        for(int i=s;i<topoOrder.size();i++) {
            int u = topoOrder.get(i);
            //System.out.println(u);
            for(int j=0;j<alist[u].size();j++) {
                AdjNode node = alist[u].get(j);
                int v = node.v;
                int weight = node.weight;
                //System.out.println(v + " " + weight);
                if(dist[v] > dist[u] + weight ) dist[v] = dist[u]+weight;
            }
        }

        return dist;

    }

    public static void main(String[] args) {
        Pathgraph g = new Pathgraph(6);
        g.initilaize();
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 6);
        g.addEdge(1, 2, 2);
        g.addEdge(2, 4, 4);
        g.addEdge(2, 5, 2);
        g.addEdge(2, 3, 7);
        g.addEdge(3, 5, 1);
        g.addEdge(3, 4, -1);
        g.addEdge(4, 5, -2);

        int s = 1;
        System.out.println("Longest distances from source vertex " );
        int[] lPath = g.longestPath(s);
        for(int k : lPath)
            System.out.print(k + " ");
        System.out.println();

        Pathgraph g1 = new Pathgraph(6);
        g1.initilaize();
        g1.addEdge(0, 1, 5);
        g1.addEdge(0, 2, 3);
        g1.addEdge(1, 3, 6);
        g1.addEdge(1, 2, 2);
        g1.addEdge(2, 4, 4);
        g1.addEdge(2, 5, 2);
        g1.addEdge(2, 3, 7);
        g1.addEdge(3, 4, -1);
        g1.addEdge(4, 5, -2);
        System.out.println("Shortest distances from given source vertex " );
        int[] sPath = g1.shortestPath(s);
        for(int k : sPath)
            System.out.print(k + " ");
    }
}

Saturday 15 November 2014

Topological Sorting - SPOJ pblm PFDEP Solution in Java

Topological sorting: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Applications:
Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization

Reference Video:
https://www.youtube.com/watch?v=W9cfpsPJwhc&index=50&list=PLLH73N9cB21W1TZ6zz1dLkyIm50HylGyg

Problem from SPOJ:
http://www.spoj.com/problems/PFDEP/

Solution :

public void solve(int testNumber, PFDEPInputReader in, PrintWriter out) {
        //Read inputs and write the main function.
        int n = in.nextInt();
        ArrayList<Integer>[] alist = new ArrayList[n];
        for(int i=0;i<n;i++) alist[i] = new ArrayList<Integer>();
        int[] indegree = new int[n];

        int m = in.nextInt();
        while(m-- > 0) {
            int v = in.nextInt()-1;
            int k = in.nextInt();
            indegree[v] += k;
            while(k-->0) {
                alist[in.nextInt()-1].add(v);
            }
        }
        ArrayList<Integer> result = TopoSort(alist,indegree);
        int i=0;
        for(i=0;i<result.size()-1;i++) out.print(result.get(i) + " ");
        out.print(result.get(i));
    }

    public ArrayList<Integer> TopoSort(ArrayList<Integer>[] alist,int[] indegree){
        Queue<Integer> q = new LinkedList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        boolean[] visited = new boolean[alist.length];

        for(int i=0;i<indegree.length;i++) {
            if(indegree[i] == 0) { q.add(i);  visited[i] = true; break;}
        }

        while(!q.isEmpty()) {
            int u = q.poll();
            result.add(u+1);

            for(int i=0;i<alist[u].size();i++) {
                int v = alist[u].get(i);
                indegree[v]--;
            }

            for(int i=0;i<alist.length;i++) {
                if(!visited[i] && indegree[i] == 0) { q.add(i); visited[i] = true; break;}
            }
        }
        return result;
    }
}

Time Complexity: O(V+E) - V - no of vertices and E - no of Edges

Friday 14 November 2014

Graph : Depth First Traversal and Breadth First Traversal for connected Graphs in Java

Assumption : Given Graph is connected.

PS : For Traversal in Disconnected Graph, refer the post of Detecting Cycle in Graph

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class TGraph {

    int v;
    ArrayList<Integer>[] alist;
    boolean[] visited;


    TGraph(int v) {
        this.v = v;
        this.alist = new ArrayList[v];
        this.visited = new boolean[v];
    }

    public void initList(){
        for(int i=0;i<alist.length;i++)
            alist[i] = new ArrayList<Integer>();
    }

    public void addEdge(int u,int v) {
        alist[u].add(v);
    }

    public void BFS(int u) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(u);
        while(!q.isEmpty()) {
            int v = q.poll();
            visited[v] = true;
            for(int i=0;i<alist[v].size();i++) {
              int n = alist[v].get(i);
                if(!visited[n]) q.add(n);
            }
            System.out.print(v + " ");
        }
    }


    public void DFS(int u) {
        visited[u] = true;
        System.out.print(u + " ");
        for(int i=0;i<alist[u].size();i++) {
            int v = alist[u].get(i);
            if(!visited[v]) DFS(v);
        }
    }

    public static void main(String[] args) {
        TGraph g= new TGraph(4);
        g.initList();
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        System.out.println("Breadth First Traversal (starting from vertex 2)");
        g.BFS(2);
        System.out.println();


        System.out.println("Depth First Traversal (starting from vertex 2)");
        TGraph g1 = new TGraph(4);
        g1.initList();
        g1.addEdge(0, 1);
        g1.addEdge(0, 2);
        g1.addEdge(1, 2);
        g1.addEdge(2, 0);
        g1.addEdge(2, 3);
        g1.addEdge(3, 3);
        g1.DFS(2);
    }


}