Autocomplete prefixes against Shakespeare's complete works

This approach uses a Trie and a Priority Queue

How it works

1. Setup a buffered I/O Reader to scan for words
2. Discarded words w/ nonalphabetic characters
3. Split words into a list of characters
4. Insert characters into Trie tracking frequency until all valid words are consumed
5. Start HTTP server and wait for GET
6. After successful request validation, get prefix's sub-Trie
7. To find up to 25 of the sub-Trie's most frequent words, firstly initialize a Priority Queue whose comparator is frequency
8. Preorder traverse the sub-Trie and insert into the Queue when node's frequency is greater than 0(denoting end-of-word)
9. Finally return at most 25 from the Priority Queue

Requirements

• HTTP GET request w/ prefix as a URL parameter
• Ignore non-word entities
• Top 25 results ordered by frequency
• Only use the Golang standard library

Getting Started

1. Clone the repo
2. Install Golang: brew update && brew install golang
3. Run the service with make run

Running Unit Tests

After cloning the repo and installing Golang, run the test scripts: make test

Supported HTTP Requests

GET /autocomplete?prefix=<prefix>

Response:

{
  "words": []string,
}

This gets the 25 most frequent words starting with the prefix

Example CURL Command

Once the server is running:

curl -X GET http://localhost:9000/autocomplete\?prefix\=th

Default port of 9000 can be modified in the makefile

Example Prefixe Results

sample data: ["th", "fr", "pi", "sh", "wu", "ar", "il", "ne", "se", "pl"]

My findings:

To follow along, run make examples which will call a shell script and display results to stdout