Contacts without a Trie

trie_diagramThis entry touches on the use of a Trie to look up complete or partial words from a specified set. In general Tries are typically used to look up completion words for a prefix (perhaps there are simpler and faster ways to implement such task). To learn more about the challenge please take a look at the following link: https://www.hackerrank.com/challenges/contacts.

Before we get into the code, I have copied and annotated part of the text from the following link: https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html.

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time (in other words not a Trie).

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.hashmap_pictorial_representation

If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table.

Following is Java code that passes all fourteen test cases:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.HashMap;

public class Solution {

public static void main(String[] args) throws IOException {

 

HashMap<String, Integer> map = new HashMap<String, Integer>();

// **** open a bufferedReader ****

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

// **** ****

int N = Integer.parseInt(br.readLine());

// **** ****

for (int n = 0; n < N; n++) {

String tokens[]      = br.readLine().split(” “);

String op                   = tokens[0];

String name                 = tokens[1];

// **** add ****

if (op.equals(“add”)) {

for (int j = 1; j <= name.length(); j++) {

String sub = name.substring(0, j);

if (map.get(sub) == null) {

map.put(sub, 1);

} else {

map.put(sub, map.get(sub) + 1);

}

}

System.out.println(“<<< map: ” + map.toString());

// **** find ****

} else {

if (map.get(name) == null) {

System.out.println(0);

} else {

System.out.println(map.get(name));

}

}

}

// **** close the bufferedReader ****

br.close();

}

}

The complete solution is about 55 lines of code including comments. The following input (as suggested in the challenge) is used:

4

add hack

add hackerrank

find hac

find hak

Following is the output of a run for the code:

<<< map: {h=1, hac=1, hack=1, ha=1}

<<< map: {hacke=1, hackerra=1, h=2, hac=2, hack=2, hackerran=1, hackerrank=1, hacker=1, hackerr=1, ha=2}

2

0

Each sub string is stored in the single HashMap map. In a Trie a word (prefix not including a leaf node) is not stored in a node but is determined by following the links from the root node down to the last letter in the prefix. If the node is a leaf a full word is found; otherwise a prefix is encountered. If in the previous example the prefix “hac” is specified, the program correctly returns two (2) because the word “hack” and “hackerrank” are in the map. When the word “hak” is specified, it is not found in the map so zero is returned. It works beautifully for the task at hand.

Now try the word “hacker” and see what happens:

5

add hack

add hackerrank

find hac

find hak

find hacker

<<< map: {hack=1, h=1, ha=1, hac=1}

<<< map: {hack=2, hackerran=1, hackerrank=1, hacke=1, hacker=1, hackerra=1, hackerr=1, h=2, ha=2, hac=2}

2

0

1

solved_stampThe program properly determines it is a partial for “hackerrank”. All is well so far. So using the code as specified would incorrectly assume that “hacker” is a complete word. The code does not have a mechanism to determine what a Trie is able to accomplish. Of course, with some thought, the code could be modified to include an indicator when a leaf node (full word) is stored.incorrect

The code as is solves the task but a Trie is not used and the main case use is not available.

If you have comments or questions, please send me a message.

John

John.canessa@gmail.com

 

Leave a Reply

Your email address will not be published. Required fields are marked *