Keep Learning

Free Cheat Sheets for Developers - part 6

2011-09-04T13:54:00.005+03:00

Latest Free Cheat Sheets for Developers:

Node.js: Building for Scalability with Server-Side JavaScript

Spring Roo: Making Java Fun Again

Understanding Lucene: Powering Better Search Results

Apache Hadoop Deployment: A Blueprint for Reliable Distributed Computing

Peg Game explanation

2011-01-09T22:06:00.010+02:00

A lot of people had a lot of question while solving Peg Game problem @ Qualification Round of Facebook Hacker Cup. Here is my understanding of this puzzle. I hope I'm right and my solution will be accepted.

Imagine a game board and try to get "boundary condition"...

where:

blue arrows shows "far left" and "far right" cases;
red arrows shows situation that will never happend (probability 0).

Also imagine "missing of a peg" situation,
where:

blue arrows shows that ball goes forward to the bottom with the same probability as it has before.

Test case from problem description

1st test case from example input

Latest discussions near Data, No SQL, Clouds

2011-01-07T15:51:00.006+02:00

Latest discussions near Data, No SQL, Clouds, etc:

Hadoop Use Cases

Hadoop/MapReduce vs SQL MPP databases/appliances

Publicly Available BigData sets:

Java & J2EE trend

2011-01-07T15:36:00.004+02:00

Java - Skills based demand trend*

J2EE - Skills based demand trend*

* source - JOB Graphs

Hudson CI in real life

2011-01-07T15:28:00.003+02:00

If you had an experience in configuring Hudson CI (or you interested in it) you probably would like to see how it is used in real life projects. So check:

Free Cheat Sheets for Developers - part 5

2011-01-07T14:31:00.003+02:00

Latest Free Cheat Sheets for Developers:

Free Cheat Sheets for Developers - part 4

2010-06-01T21:57:00.005+03:00

Cool Free Cheat Sheets for Developers:

Free Cheat Sheets for Developers - part 3

2010-05-31T21:18:00.005+03:00

Latest Free Cheat Sheets for Developers:

Core Java Concurrency

Free Cheat Sheets for Developers - part 2

2010-05-25T21:24:00.003+03:00

Another set of interesting Free Cheat Sheets for Developers:

Design Patterns

Free Cheat Sheets for Developers

2010-05-24T11:38:00.007+03:00

Recently I reviewed set of Free Cheat Sheets for Developers and found some very interesting:

Scalability & High Availability

Code Jam 2010: Theme Park

2010-05-09T21:32:00.005+03:00

The problem definition could be found at Code Jam web site.

Official Contest Analysis could be found at Code Jam web site.

My solution is published below.

Main functions:

public solve - high-level problem solving
private solve - low -level problem solving

calculateByMap

Helper classes:

Key - ride cache key
Value - ride cache value

public class ThemePark {
    ...
    private Scanner scanner;
    private PrintWriter writer;
    
    public ThemePark(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
    ...
    /**
     * Solve the problem
     */
    public void solve() {
        int t = scanner.nextInt();
   
        for (int i = 1; i <= t; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            // 1 <= R <= 10^8
            long r = scanner.nextInt();
   
            // 1 <= k <= 10^9
            long k = scanner.nextInt();
   
            // 1 <= N <= 1000
            int n = scanner.nextInt();
   
            // 1 <= g[i] <= 10^7
            long g[] = new long[n];
            for (int j = 0; j < n; j++)
                g[j] = scanner.nextInt();
   
            writer.println(solve(r, k, g));
        }
    }
   
    private String solve(long r, long k, long g[]) {
        Queue<Long> queue = new LinkedList<Long>();
        Queue<Long> ride = new LinkedList<Long>();
   
        // queue, ride -> count, euros
        Map<Key, Value> map = new LinkedHashMap<Key, Value>();
   
        for (int i = 0; i < g.length; i++)
            queue.add(g[i]);
   
        BigInteger euros = new BigInteger("0");
        for (int i = 0; i < r; i++) {
            long sum = 0;
            ride.clear();
   
            while ((queue.size() > 0) && (sum + queue.peek() <= k)) {
                ride.add(queue.peek());
                sum += queue.poll();
            }
   
            // prepare key->value pair for caching...
            Key key = new Key(queue.toString(), ride.toString());
            Value value = new Value(ride.size(), sum);
   
            if (!map.containsKey(key)) {
                map.put(key, value);
   
                euros = euros.add(new BigInteger(((Long) sum).toString()));
                queue.addAll(ride);
            } else {
                // the same [ride, queue] found in cache  
                // so calculate euros based on cache
                euros = euros.add(calculateByMap(map, key, r - i));
                break;
            }
        }
        return euros.toString();
    }
   
    private BigInteger calculateByMap(Map<Key, Value> map, Key key, long ridesLeft) {
        long storedSum = 0;
        boolean found = false;
        int foundIndex = 0;
   
        long remainder = 0;
        long remainderSum = 0;
   
        for (Key storedKey : map.keySet()) {
            // if item found - calculate remainder
            if ((!found) && (storedKey.equals(key))) {
                found = true;
                remainder = ridesLeft % (map.size() - foundIndex);
            }
            if (found) {
                // calculate stored sum
                storedSum += map.get(storedKey).getSum();
   
                // calculate remainder
                if (remainder > 0) {
                    remainderSum += map.get(storedKey).getSum();
                    remainder--;
                }
            } else
                foundIndex++;
        }
        long storedCount = map.size() - foundIndex;
        long mult = ridesLeft / (storedCount);
        mult = mult * storedSum + remainderSum;
        return new BigInteger(((Long) mult).toString());
    }
   
    class Key {
        private String queue;
        private String ride;
   
        Key(String queue, String ride) {
            this.queue = queue;
            this.ride = ride;
        }
   
        public String getQueue() {
            return queue;
        }
   
        public String getRide() {
            return ride;
        }
   
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
   
            Key key = (Key) o;
   
            if (!queue.equals(key.queue)) return false;
            if (!ride.equals(key.ride)) return false;
   
            return true;
        }
   
        @Override
        public int hashCode() {
            int result = queue.hashCode();
            result = 31 * result + ride.hashCode();
            return result;
        }
    }
   
    class Value {
        private int size;
        private long sum;
   
        Value(int size, long sum) {
            this.size = size;
            this.sum = sum;
        }
   
        public int getSize() {
            return size;
        }
   
        public long getSum() {
            return sum;
        }
    }
}

See also other posts in Code Jam

Code Jam 2010: Fair Warning

2010-05-09T21:25:00.004+03:00

The problem definition could be found at Code Jam web site.

Official Contest Analysis could be found at Code Jam web site.

My solution is published below.

Main functions:

public solve - high-level problem solving
private solve - low -level problem solving

public class FairWarning {
    ...
    private Scanner scanner;
    private PrintWriter writer;
   
    public FairWarning(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
    ...
    /**
     * Solve the problem
     */
    public void solve() {
        int c = scanner.nextInt();
   
        for (int i = 1; i <= c; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            // 2 <= N <= 1000
            int n = scanner.nextInt();
   
            // 1 <= t[i] <= 10^50
            // collect t[i] into a TreeSet to have them sorted
            NavigableSet<BigInteger> t = new TreeSet<BigInteger>();
            for (int j = 0; j < n; j++)
                t.add(new BigInteger(scanner.next()));
   
            writer.println(solve(t));
        }
    }
   
    private BigInteger solve(NavigableSet<BigInteger> t) {
        // find GCD of all differences between
        Iterator i = t.descendingIterator();
        BigInteger prev = null;
        BigInteger div = null;
        while (i.hasNext()) {
            if (prev == null)
                prev = (BigInteger) i.next();
            else {
                BigInteger diff = prev.subtract((BigInteger) i.next()).abs();
                if (diff.equals(BigInteger.ZERO))
                    continue;
                if (div == null)
                    div = diff;
                else
                    div = div.gcd(diff);
            }
        }
   
        // calculate slarboseconds 
        BigInteger mod = prev.mod(div);
        if (mod.equals(BigInteger.ZERO))
            return BigInteger.ZERO;
        return div.subtract(mod);
    }
}

See also other posts in Code Jam

Code Jam 2010: Snapper Chain

2010-05-09T20:44:00.013+03:00

The problem definition could be found at Code Jam web site.

Official Contest Analysis could be found at Code Jam web site.

Dynamic programming could be used:

state[j] - state of j-Snapper
power[j] - is j-Snapper powered
power[j+1] - do we have power after j-Snapper
state[i][j] - state of j-Snapper after i-snaps
power[i][j] - is j-Snapper powered after i-snaps
state[i][j] = (power[i-1][j]) ? !state[i-1][j] : state[i-1][j]
power[i][j+1] = power[i][j] && state[i][j]

state[i][j], where i-rows, j-columns
  0  0 0 0 0 0 0 0 0 0 0 
  1  1 0 0 0 0 0 0 0 0 0 
  2  0 1 0 0 0 0 0 0 0 0 
  3  1 1 0 0 0 0 0 0 0 0 
  4  0 0 1 0 0 0 0 0 0 0 
  5  1 0 1 0 0 0 0 0 0 0 
  6  0 1 1 0 0 0 0 0 0 0 
  7  1 1 1 0 0 0 0 0 0 0 
  8  0 0 0 1 0 0 0 0 0 0 
  9  1 0 0 1 0 0 0 0 0 0 
 10  0 1 0 1 0 0 0 0 0 0 
 11  1 1 0 1 0 0 0 0 0 0 
 12  0 0 1 1 0 0 0 0 0 0 
 13  1 0 1 1 0 0 0 0 0 0 
 14  0 1 1 1 0 0 0 0 0 0 
 15  1 1 1 1 0 0 0 0 0 0 
 16  0 0 0 0 1 0 0 0 0 0 

power[i][j], where i-rows, j-columns
  0  1 0 0 0 0 0 0 0 0 0 0 
  1  1 1 0 0 0 0 0 0 0 0 0 
  2  1 0 0 0 0 0 0 0 0 0 0 
  3  1 1 1 0 0 0 0 0 0 0 0 
  4  1 0 0 0 0 0 0 0 0 0 0 
  5  1 1 0 0 0 0 0 0 0 0 0 
  6  1 0 0 0 0 0 0 0 0 0 0 
  7  1 1 1 1 0 0 0 0 0 0 0 
  8  1 0 0 0 0 0 0 0 0 0 0 
  9  1 1 0 0 0 0 0 0 0 0 0 
 10  1 0 0 0 0 0 0 0 0 0 0 
 11  1 1 1 0 0 0 0 0 0 0 0 
 12  1 0 0 0 0 0 0 0 0 0 0 
 13  1 1 0 0 0 0 0 0 0 0 0 
 14  1 0 0 0 0 0 0 0 0 0 0 
 15  1 1 1 1 1 0 0 0 0 0 0 
 16  1 0 0 0 0 0 0 0 0 0 0

But this idea requires 30 x 10^8 array which is not possible.
If we check state[i][j] then we could find that it is just binary representation of i-number. So are not required to store it.
power[i][j+1] could be calculated only based on state[i][j].

My solution is published below.

Main functions:

solve - solves the problem
snapper - returns power after j-Snapper after i-snaps

public class SnapperChain {
   ...
    private Scanner scanner;
    private PrintWriter writer;
   
    public SnapperChain(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
   ...
    private static final int MAX_SNAPPER = 30;
   
    /**
     * Solve the problem
     */
    public void solve() {
        int t = scanner.nextInt();
   
        for (int i = 1; i <= t; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            // The light is plugged into the Nth Snapper.
            // 1 <= N <= 30;
            int n = scanner.nextInt();
   
            // I have snapped my fingers K times
            // 0 <= K <= 10^8;
            long k = scanner.nextInt();
   
            boolean light = snapper(n, k);
            writer.println((light) ? "ON" : "OFF");
        }
    }
   
    private boolean snapper(int n, long k) {
        boolean[] power = new boolean[MAX_SNAPPER + 1];
   
        power[0] = true;
        for (int j = 0; j < MAX_SNAPPER; j++) {
            boolean state = ((k >> j) & 0x01) == 0x01;
            power[j + 1] = power[j] && state;
        }
        return power[n];
    }
}

See also other posts in Code Jam

Code Jam 2010: Qualification Round - Solutions & Analysis

2010-05-09T08:45:00.003+03:00

Solutions & Analysis of problems from Qualification Round of Google Code Jam 2010 could be found below
http://code.google.com/codejam/contests.html

Code Jam 2010: Qualification Round

2010-05-08T23:44:00.004+03:00

Today I took part in Qualification Round of Google Code Jam 2010.
Successfully solved all problems with Small datasets.
Now I'm waiting for the end of the contest to verify my solutions with Large datasets.

I plan to publish my solutions later...

Graph Search Algorithms

2010-05-03T19:24:00.004+03:00

In this post next graph search algorithm are discussed:

Class diagram:

Main methods of a class Graph:

dfs - Depth-First Search
bfs - Breadth-First Search
dijkstra - Dijkstra's algorithm

Methods definition could be found below:

public class Graph {
   
   ...
   
    public List<Node> dfs(Node node) {
        clearVisited();
   
        return dfs(node, new LinkedList<Node>());
    }
   
    private List<Node> dfs(Node node, List<Node> dfsNodes) {
        if (isVisited(node))
            return dfsNodes;
   
        visit(node);
        dfsNodes.add(node);
   
        for (Edge edge : node.getEdges())
            dfsNodes = dfs(edge.getNode(), dfsNodes);
        return dfsNodes;
    }
   
    public List<Node> bfs(Node node) {
        clearVisited();
   
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(node);
   
        return bfs(queue, new LinkedList<Node>());
    }
   
    private List<Node> bfs(Queue<Node> queue, List<Node> bfsNodes) {
        while (!queue.isEmpty()) {
            Node node = queue.remove();
   
            if (!isVisited(node)) {
                visit(node);
                bfsNodes.add(node);
   
                for (Edge edge : node.getEdges())
                    queue.add(edge.getNode());
            }
        }
        return bfsNodes;
    }
   
    public Map<Node, Integer> dijkstra(Node current) {
        Map<Node, Integer> weights = new HashMap<Node, Integer>();
        for (Node node : getNodes())
            weights.put(node, Integer.MAX_VALUE);
        weights.put(current, 0);
   
        clearVisited();
        do {
            int minWeight = Integer.MAX_VALUE;
            Node minNode = null;
   
            for (Edge edge : current.getEdges()) {
                Node node = edge.getNode();
                int weight = weights.get(current) + edge.getWeight();
   
                if (weight < weights.get(node))
                    weights.put(node, weight);
   
                if ((weight < minWeight) && (!isVisited(node))) {
                    minWeight = weight;
                    minNode = node;
                }
            }
            visit(current);
            current = minNode;
        } while (current != null);
        return weights;
    }
}

Dynamic Programming: Longest Common Subsequence

2010-05-01T21:50:00.005+03:00

The idea how to solve Longest Common Subsequence problem by Dynamic Programming could be found here:

My implementation is published below.

/**
 * Longest Common Subsequence.<BR>
 * <pre>
 *           | ls(i-1,j-1) + 1,             if a[i]=b[j]
 * ls(i,j) = |
 *           | max(ls(i-1,j), ls(i,j-1)),   else
 * Boundary conditions: let think that   ls[i][-1] = 0,   ls[-1][j] = 0
 * </pre>
 */
public class LongestCommonSubsequence {
    public LongestCommonSubsequence(String a, String b) {
        this.a = a;
        this.b = b;
   
        initDp();
    }
   
    // strings a, b
    private String a;
    private String b;
   
    // ls(i,j) - maximum length of common subsequence that end at a[i] and b[j].
    private int ls[][];
   
    // specifies which neighboring cell ls(i,j) it got its value
    Direction direction[][];
   
    private void initDp() {
        // init with 0 by default
        ls = new int[a.length() + 1][b.length() + 1];
   
        // so this could be skipped
        for (int i = 0; i <= a.length(); i++)
            ls[i][0] = 0;
        for (int j = 0; j <= b.length(); j++)
            ls[0][j] = 0;
   
        direction = new Direction[a.length() + 1][b.length() + 1];
   
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    ls[i][j] = ls[i - 1][j - 1] + 1;
                    direction[i][j] = Direction.DIAG;
                } else if (ls[i - 1][j] >= ls[i][j - 1]) {
                    ls[i][j] = ls[i - 1][j];
                    direction[i][j] = Direction.UP;
                } else {
                    ls[i][j] = ls[i][j - 1];
                    direction[i][j] = Direction.LEFT;
                }
            }
        }
    }
   
    public void printLs() {
        System.out.printf("%1$2c ", ' ');
        for (int j = 0; j <= b.length(); j++)
            System.out.printf("%1$2c ", (j == 0) ? ' ' : b.charAt(j - 1));
        System.out.printf("\n");
   
        for (int i = 0; i <= a.length(); i++) {
            System.out.printf("%1$2c ", (i == 0) ? ' ' : a.charAt(i - 1));
   
            for (int j = 0; j <= b.length(); j++)
                System.out.printf("%1$2d ", ls[i][j]);
            System.out.printf("\n");
        }
    }
   
    public void printDirection() {
        System.out.printf("%1$2c ", ' ');
        for (int j = 0; j <= b.length(); j++)
            System.out.printf("%1$2c ", (j == 0) ? ' ' : b.charAt(j - 1));
        System.out.printf("\n");
   
        for (int i = 0; i <= a.length(); i++) {
            System.out.printf("%1$2c ", (i == 0) ? ' ' : a.charAt(i - 1));
   
            for (int j = 0; j <= b.length(); j++)
                System.out.printf("%1$2s ", (direction[i][j] == null)? '.' : direction[i][j]);
            System.out.printf("\n");
        }
    }
   
    public String getLcs() {
        StringBuilder sb = new StringBuilder();
   
        int i = a.length();
        int j = b.length();
        while (i > 0 && j > 0) {
            if (direction[i][j] == Direction.DIAG) {
                sb.append(a.charAt(i - 1));
                i--;
                j--;
            } else if (direction[i][j] == Direction.UP)
                i--;
            else
                j--;
        }
        return sb.reverse().toString();
    }
   
    private enum Direction {
        LEFT, UP, DIAG;
   
        @Override
        public String toString() {
            switch (this) {
                case LEFT:
                    return "<";
                case UP:
                    return "^";
                case DIAG:
                    return "\\";
            }
            throw new IllegalStateException("wrong direction");
        }
    }
   
    public static void main(String[] args) {
        LongestCommonSubsequence lcs = new LongestCommonSubsequence("CAGATAGAG", "AGCGA");
        lcs.printLs();
        System.out.printf("\n");
        lcs.printDirection();
        System.out.printf("LCS=%1$s\n\n", lcs.getLcs());
   
        lcs = new LongestCommonSubsequence("BDCABA", "ABCBDAB");
        lcs.printLs();
        System.out.printf("\n");
        lcs.printDirection();
        System.out.printf("LCS=%1$s\n\n", lcs.getLcs());
   
        lcs = new LongestCommonSubsequence("humans", "chimpanzees");
        lcs.printLs();
        System.out.printf("\n");
        lcs.printDirection();
        System.out.printf("LCS=%1$s\n\n", lcs.getLcs());
    }
}

Program output could be found below:

       A  G  C  G  A 
    0  0  0  0  0  0 
 C  0  0  0  1  1  1 
 A  0  1  1  1  1  2 
 G  0  1  2  2  2  2 
 A  0  1  2  2  2  3 
 T  0  1  2  2  2  3 
 A  0  1  2  2  2  3 
 G  0  1  2  2  3  3 
 A  0  1  2  2  3  4 
 G  0  1  2  2  3  4 
   
       A  G  C  G  A 
    .  .  .  .  .  . 
 C  .  ^  ^  \  <  < 
 A  .  \  <  ^  ^  \ 
 G  .  ^  \  <  \  ^ 
 A  .  \  ^  ^  ^  \ 
 T  .  ^  ^  ^  ^  ^ 
 A  .  \  ^  ^  ^  \ 
 G  .  ^  \  ^  \  ^ 
 A  .  \  ^  ^  ^  \ 
 G  .  ^  \  ^  \  ^ 
LCS=AGGA
   
       A  B  C  B  D  A  B 
    0  0  0  0  0  0  0  0 
 B  0  0  1  1  1  1  1  1 
 D  0  0  1  1  1  2  2  2 
 C  0  0  1  2  2  2  2  2 
 A  0  1  1  2  2  2  3  3 
 B  0  1  2  2  3  3  3  4 
 A  0  1  2  2  3  3  4  4 
   
       A  B  C  B  D  A  B 
    .  .  .  .  .  .  .  . 
 B  .  ^  \  <  \  <  <  \ 
 D  .  ^  ^  ^  ^  \  <  < 
 C  .  ^  ^  \  <  ^  ^  ^ 
 A  .  \  ^  ^  ^  ^  \  < 
 B  .  ^  \  ^  \  <  ^  \ 
 A  .  \  ^  ^  ^  ^  \  ^ 
LCS=BDAB
   
       c  h  i  m  p  a  n  z  e  e  s 
    0  0  0  0  0  0  0  0  0  0  0  0 
 h  0  0  1  1  1  1  1  1  1  1  1  1 
 u  0  0  1  1  1  1  1  1  1  1  1  1 
 m  0  0  1  1  2  2  2  2  2  2  2  2 
 a  0  0  1  1  2  2  3  3  3  3  3  3 
 n  0  0  1  1  2  2  3  4  4  4  4  4 
 s  0  0  1  1  2  2  3  4  4  4  4  5 
   
       c  h  i  m  p  a  n  z  e  e  s 
    .  .  .  .  .  .  .  .  .  .  .  . 
 h  .  ^  \  <  <  <  <  <  <  <  <  < 
 u  .  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^ 
 m  .  ^  ^  ^  \  <  <  <  <  <  <  < 
 a  .  ^  ^  ^  ^  ^  \  <  <  <  <  < 
 n  .  ^  ^  ^  ^  ^  ^  \  <  <  <  < 
 s  .  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  \ 
LCS=hmans

Dynamic Programming: Longest Common Substring

2010-04-27T20:48:00.010+03:00

The idea how to solve Longest Common Substring problem by Dynamic Programming could be found here:

My implementation is published below.

Next ideas additionally could be used to reduce the memory usage:

Keep only the last and current row
Store only non-zero values in the rows (hash tables)

/**
 * Longest Common Substring.<BR>
 * <pre>
 *           | ls(i-1,j-1) + 1,   if a[i]=b[j]
 * ls(i,j) = |
 *           | 0,                 else
 * Boundary conditions: let think that   ls[i][-1] = 0,   ls[-1][j] = 0
 * </pre>
 */
public class LongestCommonSubstring {
    public LongestCommonSubstring(String a, String b) {
        this.a = a;
        this.b = b;
   
        initDp();
    }
   
    // strings a, b
    private String a;
    private String b;
   
    /**
     * ls(i,j) - maximum length of common strings that end at a[i] and b[j].
     */
    private int ls[][];
   
    // max ls - stores max length
    private int maxLs;
    private int maxI;
    private int maxJ;
   
    private void updateMaxLs(int ls, int i, int j) {
        if (maxLs < ls) {
            maxLs = ls;
            maxI = i;
            maxJ = j;
        }
    }
   
    private void initMaxLs() {
        maxLs = 0;
        maxI = -1;
        maxJ = -1;
    }
   
    private void initDp() {
        initMaxLs();
   
        // init with 0 by default
        ls = new int[a.length() + 1][b.length() + 1];
   
        // so this could be skipped
        for (int i = 0; i <= a.length(); i++)
            ls[i][0] = 0;
        for (int j = 0; j <= b.length(); j++)
            ls[0][j] = 0;
   
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                ls[i][j] = (a.charAt(i - 1) != b.charAt(j - 1)) ? 0 : ls[i - 1][j - 1] + 1;
                updateMaxLs(ls[i][j], i, j);
            }
        }
    }
   
    public void printLs() {
        System.out.printf("%1$c ", ' ');
        for (int j = 0; j <= b.length(); j++)
            System.out.printf("%1$c ", (j == 0) ? ' ' : b.charAt(j - 1));
        System.out.printf("\n");
   
        for (int i = 0; i <= a.length(); i++) {
            System.out.printf("%1$c ", (i == 0) ? ' ' : a.charAt(i - 1));
   
            for (int j = 0; j <= b.length(); j++) {
                System.out.printf("%1$d ", ls[i][j]);
            }
            System.out.printf("\n");
        }
    }
   
    public String getLcs() {
        int size = ls[maxI][maxJ];
        char sb[] = new char[size];
   
        for(int l=0; l<size; l++)
            sb[l] = a.charAt(maxI-size+l);
        return new String(sb);
    }
   
    public static void main(String[] args) {
        LongestCommonSubstring lcs = new LongestCommonSubstring("hello", "aloha");
        lcs.printLs();
        System.out.printf("LCS=%1$s\n\n", lcs.getLcs());
   
        lcs = new LongestCommonSubstring("baba", "abba");
        lcs.printLs();
        System.out.printf("LCS=%1$s\n\n", lcs.getLcs());
   
        lcs = new LongestCommonSubstring("Quick Search algorithm", "Tuned Boyer-Moore algorithm");
        lcs.printLs();
        System.out.printf("LCS=%1$s\n\n", lcs.getLcs());
    }
}

Program output could be found below:

    a l o h a 
  0 0 0 0 0 0 
h 0 0 0 0 1 0 
e 0 0 0 0 0 0 
l 0 0 1 0 0 0 
l 0 0 1 0 0 0 
o 0 0 0 2 0 0 
LCS=lo

    a b b a 
  0 0 0 0 0 
b 0 0 1 1 0 
a 0 1 0 0 2 
b 0 0 2 1 0 
a 0 1 0 0 2 
LCS=ba

    T u n e d   B o y e r - M o o r e   a l g o r i t h m 
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
Q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
u 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
i 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 
c 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
k 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
  0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
e 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
a 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
r 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 
c 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
  0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
a 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 
l 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 
g 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 
o 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 5 0 0 0 0 0 
r 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 6 0 0 0 0 
i 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 
t 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 
h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 
m 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 
LCS= algorithm

Dynamic Programming

2010-04-26T18:06:00.004+03:00

Introductions to the Dynamic Programming (DP) could be found here:

Main characteristics of DP are:

To solve DP problem we need to do next steps:

define what we are calculating;
define recursion formula;
define boundary condition;
define calculation order.

DP problems are often used in Programming Contests

http://codeforces.com/blog/entry/325

Google Code Jam: Egg Drop Solution

2010-04-11T08:25:00.014+03:00

The problem definition could be found at Code Jam web site.

Dynamic programming:

The main idea is to understand dependency between current drop and next/prev drops.
Let F(D, B) - function returning Fmax number of floors in a building when Solvable(F, D, B) is true.
Let do a drop. We know the result for this drop: egg has been dropped or egg has not been dropped. So we covered +1 floor. Now we have D-1 drops left.
If egg has not been dropped then we still have B breaks left and for all floors from 1 to current egg will not be dropped as well. To get value of Fmax we only need to estimate how many floors upstairs we could cover to have Solvable(F, D, B) as true. We could think that we are on the ground and required value could be evaluated by F(D-1, B).
If egg has been dropped then we have B-1 breaks left. The situation below current floor is still unknown but to estimate how many floors downstairs we could cover and have Solvable(F, D, B) as true we could use F(D-1, B-1).
Taking all above into an account we have F(D, B) = 1 + F(D-1, B) + F(D-1, B-1)

Implementation:

Next facts could help to have efficient implementation.
F(D, 1) = D - because to have Solvable(F, D, B) = true we should start from 1-st floor and continue dropping from next floor one by one.
F(1, B) = 1 - because to have Solvable(F, D, B) = true we should start from 1-st floor and no more drops left after first attempt.
F(x, x) = 2^x -1 - because to have Solvable(F, D, B) = true and to have optimal solution we should use divide and conquer approach
F(x, y) = F(x, x), for all y > x - the same as for (4) and more possible breaks don't affect the result.
We need to calculate F(D, B) only for B=1..32, because all other values could be evaluated by (5) or will be -1, because they will be greater then 2^32 (4294967296)
It is enough to have array[1..Z][1..32], where F(Z, 2) > 4294967296 values to have fast, cache-based implementation of F(D, B).
(I don't know how to calculate Z theoretically, but practically Z=10000 is not enough and Z=100000 is enough)

F(D, B) - Illustration of facts discussed above

My solution is published below.

Main functions:

solve - solves the problem
initFCache - inits F-cache
getF - gets Fmax from F-cache
getD - gets Dmin based on F-cache
getB - gets Bmin based on F-cache

public class EggDrop {
   ...
   
    private Scanner scanner;
    private PrintWriter writer;
   
    public EggDrop(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
   ...
   
    private static final long MAX_F_VALUE = 4294967296l;
    private static final int LARGE_F_VALUE = -1;
    private static final int MAX_B_INDEX = 32;
   
    private static final int F_CACHE_SIZE = 100000;
    private long[][] fCache;
   
    /**
     * Solve the problem
     */
    public void solve() {
        fCache = new long[F_CACHE_SIZE][MAX_B_INDEX];
        initFCache();
   
        int n = scanner.nextInt();
   
        for (int i = 1; i <= n; i++) {
            // int is enough to store all numbers
            // see Integer.MAX_VALUE, 2,000,000,000 < 2,147,483,647
            int F = scanner.nextInt();
            int D = scanner.nextInt();
            int B = scanner.nextInt();
   
            writer.print("Case #");
            writer.print(i + ": ");
   
            long Fmax = getF(D, B);
            int Dmin = getD(F, B, D);
            int Bmin = getB(F, D, B);
   
            writer.printf("%1$d %2$d %3$d\n", Fmax, Dmin, Bmin);
        }
    }
   
    /**
     * Get Fmax from F cache
     *
     * @param d D
     * @param b B
     * @return Fmax
     */
    private long getF(int d, int b) {
        if (b > MAX_B_INDEX)
            b = MAX_B_INDEX;
   
        if (b == 1)
            return d;
   
        if (d > F_CACHE_SIZE)
            return -1;
   
        return fCache[d - 1][b - 1];
    }
   
    /**
     * Get Dmin based on F cache
     *
     * @param f F
     * @param b B
     * @param dMax D
     * @return Dmin
     */
    private int getD(long f, int b, int dMax) {
        for (int d = 1; d <= dMax; d++) {
            long maxF = getF(d, b);
            if ((maxF == LARGE_F_VALUE) || (maxF >= f))
                return d;
        }
        throw new IllegalStateException(String.format("D not found, F=%1$d, B=%2$d, Dmax=%3$d", f, b, dMax));
    }
   
    /**
     * Get Bmin based on F cache
     *
     * @param f F
     * @param d D
     * @param bMax B
     * @return Bmin
     */
    private int getB(long f, int d, int bMax) {
        for (int b = 1; b <= bMax; b++) {
            long maxF = getF(d, b);
            if ((maxF == LARGE_F_VALUE) || (maxF >= f))
                return b;
        }
        throw new IllegalStateException(String.format("B not found, F=%1$d, D=%2$d, max B=%3$d", f, d, bMax));
    }
   
    /**
     * Init F cache. DP.<BR>
     * F(D, B) = F(D-1, B) + 1 + F(D-1, B-1)<BR>
     * if F(D, B) > 4294967296 then F(D, B) = -1
     */
    private void initFCache() {
        Arrays.fill(fCache[0], 1);
   
        for (int d = 1; d < F_CACHE_SIZE; d++) {
            fCache[d][0] = d + 1;
            for (int b = 1; b < MAX_B_INDEX; b++) {
                if ((fCache[d - 1][b] == LARGE_F_VALUE) || (fCache[d - 1][b - 1] == LARGE_F_VALUE))
                    fCache[d][b] = LARGE_F_VALUE;
                else {
                    fCache[d][b] = fCache[d - 1][b] + 1 + fCache[d - 1][b - 1];
                    if (fCache[d][b] >= MAX_F_VALUE)
                        fCache[d][b] = LARGE_F_VALUE;
                }
            }
        }
    }
}

See also other posts in Code Jam

Google Code Jam: Always Turn Left Solution

2010-04-01T21:54:00.015+03:00

The problem definition could be found at Code Jam web site.

Idea

walk through maze in one direction room by room according the path
update maze room properties, we know entry and exit sides of each room
turn back, for example turn right 2 times
walk through maze in another direction room by room according the path
update maze room properties
as a result we know properties of each room

My solution is published below.

Helper classes:

MazeOptions - maze room properties
MazeCoordinates - maze coordinates and walk logic
MazeDirection - maze directions

Main function is solve.
Main "walking" function is solveOneWay.

Class diagram:

Source code:

public class AlwaysTurnLeft {

    private Scanner scanner;
    private PrintWriter writer;

    public AlwaysTurnLeft(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
   
   ...
   
    private static final int mazeSize = 2 * (int) Math.sqrt(10000);
    private MazeOptions maze[][];
   
    public void solve() {
        initMaze();
   
        int n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            writer.print("Case #");
            writer.println(i + ": ");
   
            char[] entranceToExit = scanner.next().toCharArray();
            char[] exitToEntrance = scanner.next().toCharArray();
   
            cleanOptions();
   
            MazeCoordinates mc = new MazeCoordinates(0, 0, MazeDirection.SOUTH);
            mc = solveOneWay(mc, entranceToExit);
   
            MazeDirection exitMd = mc.getMd();
   
            mc.turnBack();
            mc = solveOneWay(mc, exitToEntrance);
   
            writer.print(getOptionsCode(mc, exitMd));
        }
    }
   
    private void initMaze() {
        maze = new MazeOptions[mazeSize][2 * mazeSize];
   
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[i].length; j++)
                maze[i][j] = new MazeOptions();
    }
   
    private MazeCoordinates solveOneWay(MazeCoordinates mc, char[] path) {
        for (int i = 0; i < path.length; i++) {
            switch (path[i]) {
                case 'W':
                    updateOptionsExit(mc);
                    mc.walk();
                    updateOptionsEnter(mc);
                    break;
   
                case 'L':
                    mc.turnLeft();
                    break;
   
                case 'R':
                    mc.turnRight();
                    break;
            }
        }
        return mc;
    }
   
    private String getOptionsCode(MazeCoordinates enterMc, MazeDirection exitMd) {
        int minY = 1;
        int maxY = enterMc.getMaxY();
   
        int minX = enterMc.getMinX();
        int maxX = enterMc.getMaxX();
   
        switch (exitMd) {
            case NORTH:
                // nothing, already 1
                break;
   
            case EAST:
                maxX--;
                break;
   
            case SOUTH:
                maxY--;
                break;
   
            case WEST:
                minX++;
                break;
        }
        return getOptionsCode(minY, maxY, minX, maxX);
    }
   
    private String getOptionsCode(int minY, int maxY, int minX, int maxX) {
        StringBuilder sb = new StringBuilder();
        for (int y = minY; y <= maxY; y++) {
            for (int x = minX; x <= maxX; x++) {
                MazeOptions mo = getMazeOptions(x, y);
                sb.append(mo.toString());
            }
            sb.append("\n");
        }
        return sb.toString();
    }
   
    private void cleanOptions() {
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[i].length; j++)
                maze[i][j].clean();
    }
   
    private void updateOptionsExit(MazeCoordinates mc) {
        MazeOptions mo = getMazeOptions(mc.getX(), mc.getY());
        mo.canWalkOnExit(mc);
    }
   
    private void updateOptionsEnter(MazeCoordinates mc) {
        MazeOptions mo = getMazeOptions(mc.getX(), mc.getY());
        mo.canWalkOnEnter(mc);
    }
   
    private MazeOptions getMazeOptions(int x, int y) {
        return maze[y][mazeSize + x];
    }
   
   
    private class MazeOptions {
        private boolean canWalkNorth;
        private boolean canWalkSouth;
        private boolean canWalkWest;
        private boolean canWalkEast;
   
        public MazeOptions() {
            clean();
        }
   
        public void clean() {
            canWalkNorth = false;
            canWalkSouth = false;
            canWalkWest = false;
            canWalkEast = false;
        }
   
        public void canWalkOnExit(MazeCoordinates mc) {
            switch (mc.getMd()) {
                case NORTH:
                    canWalkNorth = true;
                    break;
   
                case EAST:
                    canWalkEast = true;
                    break;
   
                case SOUTH:
                    canWalkSouth = true;
                    break;
   
                case WEST:
                    canWalkWest = true;
                    break;
            }
        }
   
        public void canWalkOnEnter(MazeCoordinates mc) {
            switch (mc.getMd()) {
                case NORTH:
                    canWalkSouth = true;
                    break;
   
                case EAST:
                    canWalkWest = true;
                    break;
   
                case SOUTH:
                    canWalkNorth = true;
                    break;
   
                case WEST:
                    canWalkEast = true;
                    break;
            }
        }
   
        @Override
        public String toString() {
            int north = (canWalkNorth) ? 1 : 0;
            int south = (canWalkSouth) ? 2 : 0;
            int west = (canWalkWest) ? 4 : 0;
            int east = (canWalkEast) ? 8 : 0;

            int result = north | south | west | east;
            return Integer.toHexString(result);
        }
    }
   
   
    private class MazeCoordinates {
        private int x;
        private int y;
   
        private MazeDirection md;
   
        private int minX;
        private int maxX;
   
        private int minY;
        private int maxY;
   
        public MazeCoordinates(int x, int y, MazeDirection md) {
            this.x = x;
            this.y = y;
            this.md = md;
   
            minX = x;
            maxX = x;
   
            minY = y;
            maxY = y;
        }
   
        public MazeCoordinates(MazeCoordinates mc) {
            this.x = mc.x;
            this.y = mc.y;
            this.md = mc.md;
   
            this.minX = mc.minX;
            this.maxX = mc.maxX;
   
            this.minY = mc.minY;
            this.maxY = mc.maxY;
        }
   
        public void walk() {
            switch (md) {
                case NORTH:
                    y--;
                    break;
   
                case EAST:
                    x++;
                    break;
   
                case SOUTH:
                    y++;
                    break;
   
                case WEST:
                    x--;
                    break;
   
                default:
                    throw new IllegalStateException("Illegal walk");
            }
            updateMinMax();
        }
   
        private void updateMinMax() {
            if (minX > x)
                minX = x;
            if (maxX < x)
                maxX = x;
            if (minY > y)
                minY = y;
            if (maxY < y)
                maxY = y;
        }
   
        public void turnLeft() {
            md = md.turnLeft();
        }
   
        public void turnRight() {
            md = md.turnRight();
        }
   
        public void turnBack() {
            md = md.turnRight();
            md = md.turnRight();
        }
   
        public int getX() {
            return x;
        }
   
        public int getY() {
            return y;
        }
   
        public int getMinX() {
            return minX;
        }
   
        public int getMaxX() {
            return maxX;
        }
   
        public int getMinY() {
            return minY;
        }
   
        public int getMaxY() {
            return maxY;
        }
   
        public MazeDirection getMd() {
            return md;
        }
   
        @Override
        public String toString() {
            return "x: " + x + ", y: " + y + ", " + md;
        }
    }
   
   
    private enum MazeDirection {
        NORTH, SOUTH, WEST, EAST;
   
        public MazeDirection turnLeft() {
            switch (this) {
                case NORTH:
                    return MazeDirection.WEST;
   
                case EAST:
                    return MazeDirection.NORTH;
   
                case SOUTH:
                    return MazeDirection.EAST;
   
                case WEST:
                    return MazeDirection.SOUTH;
            }
            throw new IllegalStateException("Illegal turn left");
        }
   
        public MazeDirection turnRight() {
            switch (this) {
                case NORTH:
                    return MazeDirection.EAST;
   
                case EAST:
                    return MazeDirection.SOUTH;
   
                case SOUTH:
                    return MazeDirection.WEST;
   
                case WEST:
                    return MazeDirection.NORTH;
            }
            throw new IllegalStateException("Illegal turn right");
        }
    }
}

See also other posts in Code Jam

Google Code Jam: Alien Numbers Solution

2010-04-01T21:02:00.012+03:00

The problem definition could be found at Code Jam web site.

Idea

get sequence_number of a alien_number in source alien_language
by a sequence_number get alien_number in target alien_language

My solution is published below.
Main function is solve.


public class AlienNumbers {
   
    private Scanner scanner;
    private PrintWriter writer;
   
   ...
   
    public AlienNumbers(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
   
   ...
   
    /**
     * Solve the problem
     */
    public void solve() {
        int n = scanner.nextInt();
   
        for (int i = 1; i <= n; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            char[] alienNumber = scanner.next().toCharArray();
            char[] sourceLanguage = scanner.next().toCharArray();
            char[] targetLanguage = scanner.next().toCharArray();
   
            // long is enough to store sequence number
            // see Long.MAX_VALUE (9223372036854775807 ~ 10^19)
            long sequenceNumber = getSequenceNumber(alienNumber, sourceLanguage);
            char target[] = getAlienNumber(sequenceNumber, targetLanguage);
   
            writer.println(target);
        }
    }
   
    /**
     * Gets sequence number of a alien_number in alien language
     *
     * @param alienNumber   alien number
     * @param alienLanguage alien language
     * @return sequence number
     */
    private long getSequenceNumber(char[] alienNumber, char[] alienLanguage) {
        long result = 0;
        for (int i = 0; i < alienNumber.length; i++) {
            for (int j = 0; j < alienLanguage.length; j++) {
                if (alienNumber[alienNumber.length - i - 1] == alienLanguage[j]) {
                    result += (long) Math.pow(alienLanguage.length, i) * j;
                    break;
                }
            }
        }
        return result;
    }
   
    /**
     * Gets alien_number by a sequence number in alien language
     *
     * @param sequenceNumber sequence number
     * @param alienLanguage  alien language
     * @return alien number
     */
    private char[] getAlienNumber(long sequenceNumber, char[] alienLanguage) {
        StringBuilder alienNumber = new StringBuilder();
   
        for (int i = (int) log(sequenceNumber, alienLanguage.length); i >= 0; i--) {
            long power = (long) Math.pow(alienLanguage.length, i);
            int index = (int) (sequenceNumber / power);
            alienNumber.append(alienLanguage[index]);
            sequenceNumber -= index * power;
        }
        return alienNumber.toString().toCharArray();
    }
   
    /**
     * Base based logarithm of number
     *
     * @param number number
     * @param base   base
     * @return logarithm
     */
    private long log(long number, long base) {
        return (long) (Math.log(number) / Math.log(base));
    }
}

See also other posts in Code Jam

XML API Internals

2009-10-25T20:43:00.004+02:00

XML gurus define 5 styles of XML APIs:

event-based API or streaming API:
- push model: SAX, Xerces Native Interface (XNI);
- pull model: XPP3, StAX;
tree-based API: DOM, JDOM, dom4j;
data-binding API;
query API: XSLT, XPath;

More details could be found here.

Analysis illustrating how XML APIs relate to each other could be found here.

Estimated timeline of Java XML APIs could be found here.

Optimize Queries in MySQL

2009-10-11T18:42:00.004+03:00

List of resources about MySQL query optimization:

Interview Questions

2009-10-11T18:07:00.003+03:00

Below is the list of Interview Questions by Jesse Farmer: