Autocomplete Storage System

Design a system where you have a function which takes in words and stores them somewhere, and a function which behaves like an autocomplete feature (store "abc", "abd", "bcd"; prefix "a" returns "abc", "abd").

Asked in the Onsite tech 3 stage.

Implement a word store with two operations: add(word) inserts a word, and autocomplete(prefix) returns all stored words that start with prefix.

Function signature

def autocomplete_system(operations):

operations is a list of operations, where each operation is either ("add", word) or ("autocomplete", prefix). Return a list of results for each autocomplete operation, in the same order.

Requirements

1. Store duplicate insertions without breaking future lookups.
2. Return matching words in lexicographic order.
3. If no word matches a prefix, return an empty list.