# 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:

![](/files/-MJbtqUpSQP3EVG_Xls-)

## 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. 

## 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/tries/exercises.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.