---
description: This section provides exercises for better understanding in tries.
---

# 5.3. Quiz

Let `L` be a list of country names in `String` where spaces are allowed (e.g., `"United States"`, `"South Korea"`).  Consider a trie where all country names  in `L` and their unique IDs are put as key-value pairs as follows:

![](https://3789221900-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MBbA7_poZwSbBwB2yM0%2F-MJblGir3Ux72MlfCx8W%2F-MJbtqUpSQP3EVG_Xls-%2Ftries-quiz.png?alt=media\&token=1bf92e47-e040-4e81-bc7b-4dfc3a48a30f)

## Implementation

* Create the [`TrieQuiz`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/TrieQuiz.java) class under the [`trie`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/) package that inherits [`Trie`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/Trie.java) by passing `Integer` as the generic type.
* Update the `getEntities()` method that takes an input string and returns the list of [`Entity`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/Entity.java), where each entity consists of the begin index (inclusive) and end index (exclusive) of the first and the last characters of the corresponding country name respectively as well as the ID of the country name.
* See [`TrieQuizTest`](https://github.com/emory-courses/dsa-java/blob/master/src/test/java/edu/emory/cs/trie/TrieQuizTest.java) for an example of how to unit-test your approach.&#x20;

## Report

* Write a report that briefly describe your approach and explains the worst-case complexity of your approach, and save it as `quiz5.pdf`.

## Notes

* Substring matching of country names is not required.  If your dictionary has `"United States"` as a country name and the input string contains `"United Nation"`, the `"United"` should not be matched as a country name.
* Substring matching within input words are expected.  If your dictionary has `"America"` as a country name and the input contains `"American"`, the first 7 characters, `"America"` should be recognized as a country name.
* The worst-case complexity needs to be explained in terms of the number of characters `n` in the input string.
