Amazon Backend Engineer Interview Questions

To handle asynchronous processing in Amazon's services, we need a robust messaging queue service.
Problem statement: Design a MessageQueue class that supports the following methods:
- void send(string message): to add a new message to the queue.
- string receive(): to retrieve and remove a message from the front of the queue, returns an empty string if the queue is empty.
- int size(): returns the number of messages currently in the queue.Example 1:
Input: MessageQueue mq = new MessageQueue();
mq.send("msg1");
Output: null
mq.send("msg2");
Output: null
mq.receive();
Output: "msg1"
mq.size();
Output: 1Constraints:
- The number of messages will not exceed 10^4.

To maintain the performance of APIs across Amazon's services, implementing a rate limiting mechanism is crucial.
Problem statement: Design a RateLimiter class that controls requests to an API. It should allow a maximum of limit requests per second. Implement the following methods:
- bool allowRequest(string userId): returns true if the request should be allowed.
- int getRequestCount(string userId): returns the number of requests made by the user in the last second.Example 1:
Input: RateLimiter rateLimiter = new RateLimiter(5);
rateLimiter.allowRequest("user1");
Output: true
rateLimiter.allowRequest("user1");...
// After 6 calls, the 6th should return false
Output: falseConstraints:
- 1 <= limit <= 100
- 1 <= userId.length <= 30.

In Amazon's catalog, we need to efficiently match variants of products based on their attributes.
Problem statement: Given an array of integers nums, represents product variant IDs, find the length of the longest increasing subsequence. Assume each variant ID is a unique identifier.Example 1:
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], which has a length of 4.Constraints:
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10^4.

Amazon needs efficient delivery routing to ensure timely package delivery across its vast logistics network.
Problem statement: Given a graph represented by an adjacency matrix graph, where each element represents the distance between two delivery hubs, implement a function to determine the shortest path from a starting hub to all other hubs. Return an array containing the shortest distance from the start hub to each hub.Example 1:
Input: graph = [[0, 1, 4, inf], [1, 0, 2, 6], [4, 2, 0, 3], [inf, 6, 3, 0]], start = 0
Output: [0, 1, 3, 6]
Explanation: The shortest distance from hub 0 to hub 1 is 1, to hub 2 is 3, and to hub 3 is 6.Constraints:
- 1 <= number of hubs <= 100
- 0 <= graph[i][j] <= 10^5
- graph[i][i] == 0.