Understanding Tries data structure

Standard Tries

The standard Trie for a set of strings S is an ordered tree such that

• Each node but the node is labelled with a character
• The children of a node are alphabetically ordered
• The path from external nodes to the root yield the String of S.

For example see following picture -

How would you represent this in code? Each node will have an array of size 26 (assuming all english characters) where each index of array will store pointer to next node which is essentially next character of the string.

Running time for operations

• A standard trie uses O(W) space.
• Operations find, insert, delete take time O(dm) each where
• w = total size of strings in S,
• m = size of string involved in operation
• d = alphabet size

Compressed Tries

•  Trie with nodes of degree at least 2
• Obtained from standart trie by compressing chains of redundant nodes.

 Applications

Trie has many useful applications like

• Find first prefix in a text (pattern matching)
• or auto complete a text (which is why it can be used in a search engine). The index of a search engine is stored into a compressed trie. Each leaf of trie is associated with a word and has a list of pages (URLs) containing that word called occurrence list. Trie is kept in memory while the occurrence lists are kept in external memory and are ranked by relevance.
• Suffix tree (rooted directed tree whose edges are labelled with non empty substrings of S)
  
  
  
  
  
• The suffix tree for a text X of size N from an alphabet of size d stores all the N suffixes of X is O(N) space. NOTE : There might be a case where a suffix is a prefix of another suffix in which case the suffix will end on an internal mode. To counter this case you can end the alphabet with a special character eg. $. Time complexity to build suffix tree - O(N^2)

Related Links

• Trie Wiki

Database Normalization

Background

Database Normalization is a technique to store data in a database in most efficient and organized manner possible. The main aim is to eliminate data redundancies and undesirable characteristics like 

• Insertion Anomaly
• Update Anomaly
• Deletion Anomaly

Database normalization is step by step process which we will look into shortly.

Problems faced without database normalization

Lets say you have following table - 

Employee_ID	Name	Skill level	Team
1	John	A	Team C
2	Sam	A+	Team B
3	Margaret	B	Team A
4	John	A	Team A

 Lets analyze above table data and see whats wrong with it .

• Lets saw a new Employee is hired. When you make entry for him in this table his skill level will be null (as his skill sets are not yet tested ) and also his team (which may be determined by his skill set and level). This will result into Insertion Anomaly.
• Now lets say John has become proficient in work and his skill level need to be updated. We will need to update all rows corresponding to John (He may be part of different teams) to keep the data consistent. This is called Update Anomaly.
• Lets say Sam drops out of a team temporarily then we will have to delete the entire row (which inturn will delete employee details with it). This is called Deletion Anomaly.

Now lets see how we can resolve these anomalies.

Normalization Steps are as follows -

1. First Normal Form (1NF)
2. Second Normal Form (2NF)
3. Third Normal Form (3NF)
4. BCNF 

Now lets see these in detail -

First Normal Form (1NF)

A relation is in first normal form if and only if the domain of each attribute contains only atomic (indivisible) values, and the value of each attribute contains only a single value from that domain. (Wiki)

So basically a column can have set of atomic (cannot be broken down) values and each row can only have a single value from this set. So something like below is not allowed in 1 NF - 

Name	Skill level	Team
John	A	Team C, Team C
Sam	A+	Team B
Margaret	B	Team A

Instead following table is in 1 NF  -

Name	Skill level	Team
John	A	Team C
Sam	A+	Team B
Margaret	B	Team A
John	A	Team A

Second Normal Form (1NF)

 A table that is in first normal form (1NF) must meet additional criteria if it is to qualify for second normal form. Specifically: a table is in 2NF if it is in 1NF and no non-prime attribute is dependent on any proper subset of any candidate key of the table. 

A non-prime attribute of a table is an attribute that is not a part of any candidate key of the table. (Wiki)


In above table which is in 1 NF you can see that the candidate key (primary key consisting of multiple columns) is {Name,Team} However Name -> Skill level. So it violated 2 NF which states a non prime key (Skill level) should not depend on any proper subset of candidate key (Name).

So we split the table with the subset and dependent column to new table. So that the tables now become -

Name	Skill level
John	A
Sam	A+
Margaret	B

and

Name	Team
John	Team C
Sam	Team B
Margaret	Team A
John	Team A

Third Normal Form (3NF)

 3NF ensures the entity is in second normal form, and  all the attributes in a table are determined only by the candidate keys of that table and not by any non-prime attributes. (Wiki)


Consider following table

Name	Skill level	Address	Zip Code
John	A	ADDR 1	123
Sam	A+	ADDR 2	345
Margaret	B	ADDR 3	156

This is in 2 NF but not in 3 NF as Zip Code (non prime key) -> Address (non prime key) (Candidate key - Name )So we need to move this dependency (also called transitive dependency)  to new table with Zip code as primary key.


Resultant tables will be -

Name	Skill level	Zip Code
John	A	123
Sam	A+	345
Margaret	B	156

and

Zip Code	Asdress
123	ADDR 1
345	ADDR 2
156	ADDR 3

Boyce-Codd Normal Form (BCNF)

 For table to be BCNF compliant it should satisfy -

• For any non-trivial functional dependency, X → A, X must be a super-key. OR
• If X → Y is a trivial functional dependency then (Y ⊆ X)

NOTE : A superkey is a combination of columns that uniquely identifies any row within a relational database management system (RDBMS) table. A candidate key is a closely related concept where the superkey is reduced to the minimum number of columns required to uniquely identify each row.


To Sum it up -

Box Ball Logic Problem

Question

There are three bags.

1. The first bag has two blue rocks. 
2. The second bag has two red rocks. 
3. The third bag has a blue and a red rock.

All bags are labeled but all labels are wrong.You are allowed to open one bag, pick one rock at random, see its color and put it back into the bag, without seeing the color of the other rock.

How many such operations are necessary to correctly label the bags ?

Solution

Just one!

You pick a ball from the bag labelled "blue and red" ... if its blue then that's the 2 blue rocks bag and likewise for the red. ( since all bags are labelled wrong the one reading blue and red would not actually contain a blue and red ball. So it label will be whatever color of ball comes from it) Next if we get a blue ball from the blue and red labelled bag we know that the bag labelled red has got to be blue and red since we have already used up the blue label and since all bags are labelled wrongly it cannot be red.

Lowest Common Ancestor in a Binary Tree.

Background

In one of the previous posts we saw how to find LCA of two nodes in a Binary search tree. In this post we will repeat the same question but now it's just a binary tree not a BST.

 Solution

    public static BTreeNode findLCA(BTreeNode root, int n1, int n2) {

        if (root == null) {
            return null;
        }

        if (root.getData() == n1 || root.getData() == n2) {
            return root;
        }

        BTreeNode leftNode = findLCA(root.getLeft(), n1, n2);
        BTreeNode rightNode = findLCA(root.getRight(), n1, n2);

        if (leftNode != null && rightNode != null) {
            return root;
        }

        return leftNode != null ? leftNode : rightNode;

    } 

I have posted complete solution with test cases on my GIT repo of interview question. You can find the code -

• LCA Finder Git

Logic is as follows -

• If one of the two nodes is the root, then the root itself is the common ancestor.
• If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
• If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
• Otherwise, root is the Lowest common ancestor.

Related Links

• Lowest Common Ancestor in a Binary Search Tree. (OSFG) 
• LCA Finder Git

Remove repetitive words from a String and return it

Question

Assume you are given a string, write a function that can remove consecutive repeated words in the string and return it. For example,

"Beginning with the first first first first manned Gemini mission in March 1965, commemorative commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only only, only that each individual box containing a medallion bore the word Fliteline."

to

"Beginning with the first manned Gemini mission in March 1965, commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only, only that each individual box containing a medallion bore the word Fliteline."

Make sure you preserving punctuations in the right positions.

Solution

I have written following Java code with various methods that solve variations of above question -

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * 
 * @author athakur
 *
 */
public class RemoveDuplicates {

    public static void main(String args[]) {

        String input = "Beginning with the first first first first manned Gemini mission in March 1965, commemorative commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only only, only that each individual box containing a medallion bore the word Fliteline.";

        System.out.println(removeConsecutiveDuplicates(input));
        System.out.println(removeConsecutiveDuplicatesBetter(input));
        System.out.println(removeAllDuplicates(input));

    }

    public static String removeAllDuplicates(String input) {
        StringBuilder outputBuilder = new StringBuilder();
        Set<String> wordsSet = new HashSet<>();
        StringTokenizer tokenizer = new StringTokenizer(input, " ");
        while (tokenizer.hasMoreTokens()) {
            String word = tokenizer.nextToken();
            if (wordsSet.add(word)) {
                outputBuilder.append(word);
                outputBuilder.append(" ");
            }
        }
        return outputBuilder.toString();
    }

    public static String removeConsecutiveDuplicatesBetter(String input) {

        StringBuilder outputBuilder = new StringBuilder();
        String lastWord = "";
        StringTokenizer tokenizer = new StringTokenizer(input, " ");
        while (tokenizer.hasMoreTokens()) {
            String word = tokenizer.nextToken();
            if (!word.equalsIgnoreCase(lastWord)) {
                outputBuilder.append(word);
                outputBuilder.append(" ");
            }
            lastWord = word;
        }
        return outputBuilder.toString();

    }

    public static String removeConsecutiveDuplicates(String input) {

        if (input == null)
            return null;

        Stack<String> wordsStack = new Stack<>();
        String[] words = input.split(" ");
        for (int i = 0; i < words.length; i++) {
            wordsStack.push(words[i]);
        }

        String lastWord = "";
        String stringWithNoConsecutiveDuplicates = "";

        while (!wordsStack.isEmpty()) {
            String tempPop = wordsStack.pop();
            if (!lastWord.equalsIgnoreCase(tempPop)) {
                stringWithNoConsecutiveDuplicates = tempPop + " "
                        + stringWithNoConsecutiveDuplicates;
            }

            lastWord = tempPop;
        }

        return stringWithNoConsecutiveDuplicates;

    }

}

Note

Couple of points to note. Prefer removeConsecutiveDuplicatesBetter approach as it does not keep all data in memory. So lets say you have a huge file you need to do this operation on you read it line by line and then tokenize it to further process it.

Also note HashSet has add method which returns false if data is already present in the set.

Stack method is more if you want to retain the duplicate consecutive words which are farthest in a line. Irrespective of your approach you need to take care of following -

• Don't keep all the data in the memory (data can be very huge). Using Stack may led to overflow.
• Use minimum space and more efficient lookup. Hashset internally used HashMap to keep the data hence put/get is ~O(1).
• Avoid String concatenation. Use StringBuilder instead.

As you must have already noticed above approaches do not take care of punctuations. You will need separate processing for that.

Related Links

• Difference between StringBuilder and StringBuffer in Java (OSFG)
• IO in Java (Using Scanner and BufferedReader) (OSFG)