19. Trie Challenges

Written by Kelvin Lau

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 big assumption that all O(1) operations take the same time and that n * O(1) == O(n),

Challenge 2: Additional properties

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:

1. A collections property that returns all the collections in the trie.

2. A count property that tells you how many collections are currently in the trie.

3. A isEmpty property that returns true if the trie is empty, false otherwise.

Solutions

Solution to Challenge 1

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

With those assumptions:

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

1,000,000 is the database size; 3 is the prefix length; 4 is the number of matches; 8 is the length of the entry “priority”.

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> = []

This is a Set that will store all the keys in the trie.

The private(set) scope modifier prevents the property from being tampered with outside the class definition. For this Set to be useful, you’ll need to further constrain the trie such that the collection it holds is also Hashable.

Update the class declaration to the following:

public class Trie<CollectionType: Collection & Hashable>
  where CollectionType.Element: Hashable

Next, in the insert method, find the line current.isTerminating = true and replace it with:

if current.isTerminating {
  return
} else {
  current.isTerminating = true
  collections.insert(collection)
}

In the remove function, find the line current.isTerminating = false and add the following just below that line:

collections.remove(collection)

Adding the count and isEmpty properties is straightforward now that you’re keeping track of all the collections:

public var count: Int {
  collections.count
}

public var isEmpty: Bool {
  collections.isEmpty
}