Google Software Engineer System Design Questions

As Google’s search engine evolves, providing suggestions while users type is critical for enhancing search quality and user experience. Your task is to design an autocomplete system that suggests search terms based on previously entered queries.
Problem statement: Design a class AutocompleteSystem that supports the following operations:
- input(char c: char) -> List[str]: Accepts a character and returns a list of the top 3 suggested terms that start with the current input string based on weighted frequency.
- addSentence(sentence: str, times: int) -> None: Adds a new sentence with its corresponding frequency.Example 1:
Input:
autocompleSystem = new AutocompleteSystem();
autocompleSystem.addSentence("i love you", 5);
autocompleSystem.addSentence("island", 5);
output = autocompleSystem.input('i');
// returns ["i love you", "island"]Example 2:
Input:
autocompleSystem = new AutocompleteSystem();
autocompleSystem.addSentence("hi", 2);
output = autocompleSystem.input('h');
// returns ["hi"]Constraints:
- The input will only be lowercase English letters.
- The total number of sentences will not exceed 1000.
- Each sentence has at most 100 characters.

In optimizing the performance of Google’s services, managing frequently accessed data is key. Implement an LRU Cache for the API calls to minimize latency and server calls.
Problem statement: Implement an LRUCache class with the following methods:
- get(key: int) -> int: Returns the value of the key if the key exists, otherwise return -1.
- put(key: int, value: int) -> None: Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, the least recently used key should be removed.Example 1:
Input:
lruCache = LRUCache(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
output1 = lruCache.get(1); // returns 1
lruCache.put(3, 3); // evicts key 2
output2 = lruCache.get(2); // returns -1 (not found)Example 2:
Input:
lruCache = LRUCache(1);
lruCache.put(2, 1);
output1 = lruCache.get(2); // returns 1
lruCache.put(3, 2); // evicts key 2
output2 = lruCache.get(2); // returns -1 (not found)Constraints:
- The capacity of the cache will be at most 10^4.
- The keys are guaranteed to be unique within the cache.