Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • EspaΓ±ol

β€ΊKey Concepts

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Tries

A trie is a variant of an n-ary-tree, in which characters are stored at each node. Each path down the tree may represent a word.

Tries are a relatively advance topic, make sure you come to this section once you feel a bit comfortable with Trees, Graphs and Recursion. Just be aware is quite important to be aware of this, as they come in interviews relatively often.

imagen

The * nodes (also known as "null nodes") are used to indicate completed words, just bear in mind these nodes are not always used. Sometimes people use nul pointers or boolean flags. In the example we have the completed words: many, my, lie, a.

A node in the trie dictionary could range from 1 to the alphabet size + 1 children (or 0 if boolean flags are being used instead of a * node).

Tries are commonly used to store an entire language for quick prefix lookups. While a Hashmap can tell us quickly if a string is a valid word, it can't tell us if a string is a valid prefix of a word.

πŸ‘‰ Problem: Autocompletion

Given a list of words:

['dog', 'dark', 'cat', 'door', 'dodge']

And the input:

input = 'do'

Print or return back a list with all the words that start of the input string.

output = ['dog', 'door', 'dodge']

πŸ‘Ž Bad Solution

public ArrayList badSolution(ArrayList<String> list, String inputWord) {
    ArrayList<String> result = new ArrayList();
    for (String s : list) {
        if (s.contains(inputWord)) result.add(s);
    }
    return result;
}

Majority of people come up with a solution like this, which runs in O(N * K), where N is the size of the input list and K is the size of the string. This is not very efficient at all. Let's have a look at how we could optimise it using Tries.

πŸ‘Š Solution

In order to solve this we will first need to assemble a Trie

imagen

Here is the implementation of the TrieNode and Trie classes:

Node

public class TrieNode {

    private char character;
    private HashMap<Character, TrieNode> children = new HashMap<>();
    private boolean isWord;

    TrieNode() {}

    TrieNode(char c) {
        this.character = c;
    }

    public char getCharacter() {
        return character;
    }

    HashMap<Character, TrieNode> getChildren() {
        return children;
    }

    boolean isWord() {
        return isWord;
    }

    void setWord(boolean word) {
        isWord = word;
    }
}

Don't let this scare you, its mainly boilerplate code - with getters and setters.

As you can see, the node has a HashMap, the key is each Character to which this node points to.

Trie

Every time we input a word into the trie, we perform a check in order to see if the char already exist, if it does, we check with the next character until there is a new one, then we create a new node. Once we know the word has no more chars left, we toggle the flat of the last node to true - indicating the word has ended.

public class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;

        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);

            TrieNode t;
            if (current.getChildren().containsKey(c)){
                t = current.getChildren().get(c);
            } else {
                t = new TrieNode(c);
                current.getChildren().put(c, t);
            }

            current = t;

            if(i==word.length()-1)
                t.setWord(true);
        }
    }
}

Solving the problem

In order to solve this problem, we need to first navigate to the node in which the prefix ends. From there we will be able to a variation of a Depth First Search, in which we will keep adding to the prefix the current character and traversing to each node, until we know the word ends, then we print the full word.

public void printWordsWithPrefix(String prefix) {
    TrieNode t = traverseToNode(prefix);

    printWordsFromNode(t, prefix);
}

private TrieNode traverseToNode(String inputWord) {
    TrieNode current = root;

    TrieNode t = null;
    
    // traverse to the last node of the word
    for (int i = 0; i < inputWord.length(); i++) {
        char c = inputWord.charAt(i);
        if (current.getChildren().containsKey(c)) {
            t = current.getChildren().get(c);
            current = t;
        } else {
            return null;
        }
    }
    return t;
}

private void printWordsFromNode(TrieNode t, String prefix) {
    if (t.isWord()) {
        System.out.println(prefix);
    }

    // Depth First Search until we reach the last node of each word, then we can print it
    for (int i = 0; i < t.getChildren().keySet().size(); i++) {
        char c = (char) t.getChildren().keySet().toArray()[i];
        TrieNode children = t.getChildren().get(c);
        printWordsFromNode(children, prefix + c);
    }
}
Last updated on 3/26/2020
← GraphsSorting β†’
  • πŸ‘‰ Problem: Autocompletion
  • πŸ‘Ž Bad Solution
  • πŸ‘Š Solution
    • Node
    • Trie
    • Solving the problem
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright Β© 2021 Kodr