# 19 Trie Challenges Written by Kelvin Lau

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

### Challenge 1: How much faster?

Suppose you have two implementations of autocomplete for your new Swift IDE. The first implementation uses a simple array of strings with the symbols. The second implementation uses a trie of strings. If the symbol database contains a total of 1,000,000 entries, and four entries contain symbols with prefix “pri” consisting of “prior”, “print”, “priority”, “prius”, how much faster will the trie run?

Note: Make the simplifying assumption that all `O(1)` operations take the same time and that `n * O(1) == O(n)`,

The current implementation of the trie is missing some notable operations. Your task for this challenge is to augment the current implementation of the trie by adding the following:

## Solutions

### Solution to Challenge 1

The answer is that the trie of strings runs “way faster”.

``````1,000,000 * 3 * O(1) / 4 * 8 * O(1) = 93,750 times faster
``````

### Solution to Challenge 2

You’ll implement the `collections` property as a stored property. Inside Trie.swift, add the following new property:

``````public private(set) var collections: Set<CollectionType> = []
``````
``````public class Trie<CollectionType: Collection & Hashable>
where CollectionType.Element: Hashable
``````
``````if current.isTerminating {
return
} else {
current.isTerminating = true
collections.insert(collection)
}
``````
``````collections.remove(collection)
``````
``````public var count: Int {
collections.count
}

public var isEmpty: Bool {
collections.isEmpty
}
``````

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.