Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

Before You Begin

Section 0: 6 chapters

Section I: Introduction

Section 1: 3 chapters

Section II: Elementary Data Structures

Section 2: 6 chapters

19. Trie Challenges Written by Kelvin Lau

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now