Google Backend Engineer Interview Questions

Google Chat requires a reliable messaging system to handle messages between users effectively. A simple message queue can be implemented to ensure that messages are processed in the order they are received.
Problem Statement: Design a MessageQueue class that allows enqueuing and dequeuing messages, ensuring that all messages are processed in FIFO order.
Class Signature: class MessageQueue:
- def __init__(self): — initializes the message queue.
- def enqueue(self, message: str) -> None: — adds a message to the queue.
- def dequeue(self) -> str: — removes and returns the oldest message from the queue. If the queue is empty, raises an exception.
Example 1:
Input: msg_queue = MessageQueue(); msg_queue.enqueue('Hello'); msg_queue.enqueue('World'); msg_queue.dequeue()
Output: 'Hello'
Constraints:
- The message length is at most 10^5 characters.

As Google Cloud offers APIs to developers, it's essential to manage the rate of requests to prevent abuse. A rate limiter needs to enforce a maximum number of requests per time frame.
Problem Statement: Design a RateLimiter class which limits the number of API requests per second.
Class Signature: class RateLimiter:
- def __init__(self, requests_per_second: int): — initializes the rate limiter with the specified maximum requests per second.
- def allow_request(self, user_id: str) -> bool: — returns True if the request is allowed according to the rate limit, otherwise False.
- def reset(self, user_id: str) -> None: — resets the request count for a specific user.
Example 1:
Input: RateLimiter(2); rate_limiter.allow_request('user1')
Output: True
Input: rate_limiter.allow_request('user1')
Output: True
Input: rate_limiter.allow_request('user1')
Output: False
Input: rate_limiter.reset('user1')
Constraints:
- 1 <= requests_per_second <= 100
- A user can make at least one request.

Google Play wants to provide the best app recommendations based on user preferences. The longest increasing subsequence can be used to find sequences of user interests.
Problem Statement: Given an integer array nums, return the length of the longest increasing subsequence. You need to implement a function that computes this efficiently.
Method Signature: def longest_increasing_subsequence(nums: List[int]) -> int: — returns an integer representing the length of the longest increasing subsequence.
Example 1:
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], so the length is 4.
Constraints:
- 1 <= len(nums) <= 2500
- -10^4 <= nums[i] <= 10^4.

Google Maps needs to find the shortest path between locations efficiently. Imagine you have a graph representing the streets of a city where the nodes are intersections and edges represent the road segments with weights signifying travel time.
Problem Statement: Implement a function that takes a graph represented as an adjacency list and returns the shortest path from a given starting node to all other nodes using Dijkstra's algorithm. The graph is represented as follows: graph: Dict[str, List[Tuple[str, int]]].
Method Signature: def dijkstra(graph: Dict[str, List[Tuple[str, int]]], start: str) -> Dict[str, int]: — returns a dictionary with the shortest distance from the start node to all other nodes.
Example 1:
Input: { 'A': [('B', 1), ('C', 4)], 'B': [('A', 1), ('C', 2), ('D', 5)], 'C': [('A', 4), ('B', 2), ('D', 1)], 'D': [('B', 5), ('C', 1)] }, 'A'
Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Explanation: Starting from A, the shortest path to B is 1, to C is 3, and to D is 4.
Constraints:
- 1 <= len(graph) <= 10^4
- 1 <= number of edges <= 10^4
- All weights are positive integers.