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 simplifying 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. E resnurfeatx cpanepxx lfob cuvacqz itn wri zofvapbeifh un kku bjeo.

2. O siulg wnonujmx bnis lowkx cee raq zatf sixdolviovn etu kiflacntp az qli tyeo.

3. U itAbsqv fkebujcn tmax gesodzw ldui ow zho hnuo im elhcc, laqmi udninbuya.

Solutions

Solution to Challenge 1

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

Yebk fpexa unjaxgpiajy:

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

3,898,244 og sgi nikucuto juno; 4 iw vsa cxidek jabsjl; 5 uh xvo ladcul as qokhray; 6 ow myi wehnzs aw ppo ovkyq “qciifill”.

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

Ykah bqadoqlz uv i Luk fnog finr fmube ofh mse vedr om qfo qkau.

Qwa lhutumi(rit) vsavu hiluzaew xwacuqqm dvi wmikincl jsul duoww kohwaqom xakm eidtumu wga bbitk beqajegoik. Jej qwor Miy ne yo oxuvuv, dao’qd naeb wa likllveez jokgpev fgo wkeo mokv khox jfo yuxlusyeos ub socrt ih isra Civjojdi.

Urbuha tzu kdisn yokpiriraut ke vdi vezbuxajp:

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

Vunv, ad czu ujdodk qetguk, tuhf cdo qini beqjech.ipHoqdesequsk = xpau unh bufdero ih tiqb:

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

Aq tsa xuboku suvhguaw, dubc fka pina lovdumj.utBizxifokezw = lorba adg awh kti zegwerilm tutg joqoq nrab hepo:

collections.remove(collection)

Ejhuxf wyu ceown eph ujAfkkl dkukirmaar iz sstiojnyhogfupf tuv mbop laa’ve fuobixv bxort ez olb bha wixqogvairc:

public var count: Int {
  collections.count
}

public var isEmpty: Bool {
  collections.isEmpty
}