Google Interview 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.

In managing large datasets, Google Cloud’s BigQuery requires efficient computations to determine the largest rectangular area defined by 1s in a binary matrix.
Problem statement: Given a m x n binary matrix filled with 0s and 1s, your task is to return the area of the largest rectangle containing only 1s. You must implement maximalRectangle(matrix: List[List[int]]) -> int.Example 1:
Input: matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
Output: 6
Explanation: The largest rectangle has an area of 6.Example 2:
Input: matrix = [[0,0,0],[0,0,0]]
Output: 0
Explanation: There are no 1s in the matrix.Constraints:
- m == matrix.length
- n == matrix[i].length
- Area must be computed in O(m*n) time.

In Google's Maps, real-time navigation requires efficient pathfinding over large graphs representing cities and road networks. Your task is to implement the A* search algorithm to find the shortest path between two points.
Problem statement: You need to implement the method findShortestPath(start: Point, end: Point) -> List[Point], which returns the shortest path as a list of Points from the start to the end. Assumptions include that the environment is represented as a 2D grid where passable and non-passable terrains are indicated.
- Point: A representation of a coordinate with x and y attributes.Example 1:
Input: start = (0, 0), end = (3, 3)
Output: [(0, 0), (1, 1), (2, 2), (3, 3)]
Explanation: The algorithm finds an optimal path through the grid.Example 2:
Input: start = (1, 1), end = (4, 4)
Output: [(1, 1), (2, 2), (3, 3), (4, 4)]
Explanation: Another optimal path is provided based on proximity.Constraints:
- The grid size will be at most N x N with N ≤ 1000.
- Points coordinates will be between 0 and N-1.