Monday 7 November 2011

A fresher at Stratify..

After a, I cannot believe its been so long, 7 yrs my association with my first company (Stratify Inc.), comes to an end this Wednesday.

The beauty of a first job, apart from the financial independence it provides, is the enthusiasm associated with it. I distinctly recollect, as they say, the fire in the belly, when I reported for my first day at work and guess what, I have the same feeling as I head into the next leg of my career.

I can recollect many instances where my colleague's actions/words motivated me to go the extra yard, put in that extra night out to meet our deadlines and above all the expectations the team had from me. I also recollect those long hours spent in 'mandir' which not only bonded us closer as individuals but also motivated us to walk in the next day and give our best.

After days sequenced code, smoke, code, smoke, lunch, smoke, code, smoke and then the freakishly competitive foozball we were all setup for the perfect evening  in mandir full of drinks where we all rubbed off each other's energy.. 

I was also blessed with a guardian who always motivated me and warned me when complacency or over-confidence or politics got the best of me, to him I owe more than any words I can put out here.


I believe that your first long stay at a company, and when I say long I am talking atleast 2 years, goes a long way in shaping you as a professional and what I want to take forward from Stratify is the hardwork, honesty, humility and above all the team spirit which my colleagues have instilled in me and I can only hope that my next adventure is as exciting and enriching as my first has been... So long Stratifyans.. so long.

Wednesday 2 November 2011

Sample TRIE implementation in Java

Tried my hands at implementing a TRIE data structure in Java. There are 2 classes posted here, Trie itself and TrieNode which represents a node in a Trie.

Trie class
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * TRIE data structure supporting basic dictionary operations.
 */
public class Trie {

    private final TrieNode root;

    /**
     * Creates a new empty TRIE object.
     */
    public Trie() {
        root = new TrieNode();
    }


    /**
     * Inserts the specified key into this Trie object.
     * @param key
     */
    public void insert(String key) {
        TrieNode currNode = root;
        for (char c : key.toCharArray()) {
            TrieNode child = currNode.traverse(c);
            if (child == null) {
                currNode = currNode.addEdge(c);
            } else {
                currNode = child;
            }
        }
        currNode.setKey(key);
    }

    /**
     * Returns all the keys in the Trie which start with the specified prefix.
     * @param prefix
     * @return
     */
    public List<String> search(String prefix) {
        TrieNode currNode = root;
        for (char c : prefix.toCharArray()) {
            TrieNode child = currNode.traverse(c);
            if (child == null) {
                return Collections.emptyList();
            } else {
                currNode = child;
            }
        }
        List<String> matches = new ArrayList<String>();
        preorderTraverse(currNode, matches);
        return matches;
    }

    /**
     * Does preorder traversal of Trie and add retrieved keys in the specified results list.
     * @param currNode
     * @param results
     */
    private void preorderTraverse(TrieNode currNode, List<String> results) {
        if (currNode == null) return;
        if (currNode.getKey() != null) {
            results.add(currNode.getKey());
        }
        Iterator<TrieNode> children = currNode.getChildren();
        if (children != null) {
            while (children.hasNext()) {
                preorderTraverse(children.next(), results);
            }
        }
    }


    public static void main(String[] args) {
        Trie t = new Trie();
        t.insert("vino");
        t.insert("vinod");
        t.insert("vin");
        t.insert("jyo");
        t.insert("jyotsna");
        t.insert("jyot");
        t.insert("jyots");
        t.insert("jyotsn");
        t.insert("joe");

        System.out.println(t.search("vino"));
        System.out.println(t.search("j"));
        System.out.println(t.search("jy"));
        System.out.println(t.search("joe"));

        System.out.println(t.search("bhalblah"));
    }
}



TrieNode class
import java.util.*;

/**
 * A Trie Node
 */
class TrieNode {


    /**
     * The key stored in this node if any.
     */
    private String key;

    /**
     * the outgoing edges of this node, implemented as a sorted map of character to the child node.
     */
    private SortedMap<Character, TrieNode> edges;


    TrieNode addEdge(char c) {
        if (edges == null) {
            edges = new TreeMap<Character, TrieNode>();
        }
        TrieNode childNode = new TrieNode();
        edges.put(c, childNode);
        return childNode;
    }

    TrieNode traverse(char c) {
        return (edges == null) ? null : edges.get(c);
    }

    TrieNode deleteEdge(char c) {
        return (edges == null) ? null : edges.remove(c);
    }

    Iterator<TrieNode>  getChildren() {
        return (edges == null) ? null : edges.values().iterator();
    }

    void setKey(String key) {
        this.key = key;

    }

    String getKey() {
        return key;
    }

    public int getChildrenCnt() {
        return edges == null ? 0 : edges.size();
    }
}