A real-time suggestion service, which enable users to search for known and frequently searched terms. It tries to predict the query based on the characters the user has enteredand gives a list of suggestions to complete the query.
docker build . -t typeaheadsuggestiondocker container run -p 80:80 typeaheadsuggestionSince we've got to serve a lot of queries with minimum latency, we need to come up with a scheme that can effeciently store our data such that it can be queried quickly. We can't depend upon some database for this, we need to store our index in memory in a highly efficient data structure.
One of the most appropriate data structures that can serve our purpose is the Trie
- Space : O(n)
- Search : O(n)
- Insert : O(n)
- Delete : O(n)
To compute the k most relevant elements, we can use a Heap (Priority Queue), to be able to do it during the search in an efficient way O(nlog(k)).
For dev env you can use the swagger page accessible using this url : https://localhost/swagger
- Zakaria Maaraki - Initial work - zakariamaaraki