AutoComplete Engine for Text editor or IDE LLD | Microsoft LLD

Problem statement

• Design and implement the core logic for an auto-complete engine used in a text editor or IDE.

• The engine should suggest completions as the user types text based on previously stored entries and usage context.

• Given a prefix (e.g., pri), suggest the top matching words or symbols (e.g., print, private, printf).

• Return suggestions in sorted order based on frequency of usage or relevance. // need to use strategy pattern

• Create strategy based on frequency of usage or relevance only

Implementation

User in IDE used a specific language like java, python, we can create context based on that that can be used for suggestions
When User search a word It needs to be added in context.
For frequency based strategy we need to update usage counter for each word we have added in our system.

Entities

TrieNode(data structure) to store entries and to traverse them

Context ->  language (java, python, javascript)

WordEntry -> contains metadata and word related details

EntityType (Enum)
KEYWORD, METHOD, VARIABLE, CLASS etc

RankStrategy -> rankEntries(List availableEntries,String prefix)

• Frequency
• Relevance

AutoCompleteEngine (Facade class)

EntityFields :

TrieNode

• children
• isEndOfWord
• usageCount
• Word
• entityType
• Language // for context
  Methods
  insertWord(String word)
  findWord(String word)
  getSuggestions(String prefix)
  deleteSuggestion()

WordEntry

• Word
• Entrytype
• Language
• UsageCount

AutoCompleteEngine

• TrieNode
• RankStrategy
• currentLanguage
• contextHistory
  Methods
  AddWord()
  suggest()
  RecordUsage()
  initializeLanguage()

UML diagram

Video explaination ->