Amazon Interview Questions

Background: In Amazon's recommendation system, understanding relationships between products can involve analyzing user interactions through a structured binary tree of products. Finding the lowest common ancestor helps in tracing back relationships efficiently.
Problem statement: Given a binary tree and two nodes, p and q, find their lowest common ancestor (LCA). The LCA is defined as the deepest node that is an ancestor of both p and q. You can assume both nodes exist in the tree and that each node has a unique value.
Function/class signature:

• def lowest_common_ancestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:

Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 itself, as it's one of the nodes.Constraints:

• All nodes' values are unique.


• The tree will not be empty.


• Nodes p and q will always exist in the tree.

Background: Amazon needs caching mechanisms to improve the response time for frequently accessed data, especially in services like product recommendations and order history. An LRU (Least Recently Used) cache is a common strategy for such scenarios, efficiently managing data retrieval and storage.
Problem statement: You are required to implement an LRUCache class that follows the Least Recently Used eviction policy to manage a limited-capacity cache. The cache should support both adding and retrieving values while ensuring that the least recently accessed items are removed when the capacity is exceeded. The class must provide the following methods:

• get(key: int) -> int: Retrieve the value of the key if it exists, otherwise return -1.


• put(key: int, value: int) -> None: Insert or update the value of the key. If the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Function/class signature:

• class LRUCache:

- def __init__(self, capacity: int):
- def get(self, key: int) -> int:
- def put(self, key: int, value: int) -> None:
Example 1:

• Input: cache = LRUCache(2)

cache.put(1, 1)
cache.put(2, 2)
cache.get(1)

• Output: 1


• Explanation: The value for key 1 is retrieved successfully after insertion.

Example 2:

• Input: cache.put(3, 3)

cache.get(2)

• Output: -1


• Explanation: Key 2 has been evicted due to cache capacity.

Constraints:

• Capacity of the cache is in the range 1 <= capacity <= 10^4.


• Operations get and put are only called with keys in the range 1 <= key <= 10^4.

1. Background: Amazon often deals with large sets of data, such as product inventories that may be sorted but could also be rotated for optimization. Efficiently searching through this data is crucial for performance, especially during peak times like Prime Day.
2. Problem statement: Given an array of integers nums sorted in ascending order, which is then rotated at an unknown pivot, and an integer target, write a function to determine if target exists in nums. If it does, return its index; otherwise, return -1. You must use binary search to complete the task efficiently.
3. Function signature:
- def search(nums: List[int], target: int) -> int:
4. Example 1:
- Input: nums = [4,5,6,7,0,1,2], target = 0
- Output: 4
- Explanation: The target 0 is found at index 4 after rotation.
5. Example 2:
- Input: nums = [1], target = 0
- Output: -1
- Explanation: The target 0 does not exist in the array.
6. Constraints:
- 1 <= len(nums) <= 10^5
- -10^4 <= nums[i] <= 10^4
- All integers in nums are unique.
- nums is guaranteed to be rotated at some pivot.

Background: In Amazon's e-commerce platform, it's essential to analyze user input and product descriptions for various patterns, including palindromes that can highlight special offers or categories. Understanding such patterns aids in improving user experience and enhancing search features.
Problem statement: Given a string s, return the count of palindromic substrings in it. A substring is considered palindromic if it reads the same backward as forward. For example, "aba" is a palindrome.
Function/class signature:

• def count_palindromic_substrings(s: str) -> int:

Example 1:

• Input:

"abc"

• Output:

3

• Explanation: There are three palindromic substrings: "a", "b", and "c".

Example 2:

• Input:

"aaa"

• Output:

6

• Explanation: The palindromic substrings are "a", "a", "a", "aa", "aa", and "aaa".

Constraints:

• 1 <= s.length <= 1000


• s consists of lowercase English letters only.

Background: Amazon operates an extensive delivery network to ensure that packages reach customers as quickly as possible. Optimizing delivery routes is crucial to enhance efficiency and reduce transportation costs. This problem relates to routing algorithms used in shipment logistics.Problem statement: You are given a directed graph, where each node represents a delivery station and each edge represents a delivery route with a time cost. Your task is to find the shortest delivery time from a given source station to a destination station using Dijkstra's algorithm. Implement this in the function shortest_delivery_time(n: int, routes: List[Tuple[int, int, int]], source: int, destination: int) -> int, where n is the number of stations, routes is a list of tuples representing directed edges (station1, station2, time), and the result should be the minimum delivery time. If the destination is not reachable, return -1.Function/class signature:

• def shortest_delivery_time(n: int, routes: List[Tuple[int, int, int]], source: int, destination: int) -> int:

Example 1:

• Input: n = 5, routes = [(0, 1, 2), (0, 2, 4), (1, 2, 1), (1, 3, 7), (2, 3, 3)], source = 0, destination = 3


• Output: 9


• Explanation: The shortest path is 0 -> 1 -> 2 -> 3 with a total time cost of 9 (2 + 1 + 3).

Example 2:

• Input: n = 4, routes = [(0, 1, 10), (1, 2, 10), (2, 3, 10)], source = 0, destination = 3


• Output: 30


• Explanation: The only path is 0 -> 1 -> 2 -> 3 with a total time cost of 30.

Constraints:

• 1 <= n <= 1000


• 0 <= routes.length <= 10000


• 0 <= station1, station2 < n


• 1 <= time <= 1000

Background: Depth-first search (DFS) is a fundamental algorithm in graph theory used to traverse or search through nodes in a graph efficiently. Amazon could utilize this technique for various applications, such as network routing or recommendation systems based on user interactions.
Problem statement: Given an n-node directed graph (i.e., a graph where edges have a direction), implement a function that performs a depth-first search starting from a given node and returns all the nodes in the order they were visited.Your function should return a list of integers representing the nodes visited in the DFS order. The graph is represented as an adjacency list, where each index corresponds to a node and contains a list of its connected nodes. Function/class signature:

• def depth_first_search(graph: List[List[int]], start: int) -> List[int]:

Example 1:
Input: graph = [[1, 2], [3], [3], []], start = 0
Output: [0, 1, 3, 2]
Explanation: From node 0, it visits 1 (which connects to 3), then goes back to 0, and then visits 2, leading to the sequence 0 -> 1 -> 3 -> 2.Example 2:
Input: graph = [[1, 2], [3], [3], []], start = 2
Output: [2, 3]
Explanation: From node 2, it directly visits 3, and since 3 has no outgoing edges, it returns just [2, 3].Constraints:

• The graph will have between 1 and 1000 nodes.


• Each node will be connected to at most n - 1 other nodes.


• The graph does not contain cycles.

Background: In systems like Amazon's review monitoring to ensure quality of service, it’s essential to identify connected components within a network of product reviews. This allows Amazon to focus on improving linked products together.
Problem statement: Given an undirected graph represented by a list of edges, write a function to find all the connected components in the graph. Each connected component should itself be a list of connected node identifiers.

• Function/class signature:

- def find_connected_components(n: int, edges: List[Tuple[int, int]]) -> List[List[int]]: return type List[List[int]]
Example 1:

• Input: n = 5, edges = [(0, 1), (0, 2), (3, 4)]


• Output: [[0, 2, 1], [3, 4]]


• Explanation: There are two connected components: one with nodes 0, 1, and 2, and another with nodes 3 and 4.

Example 2:

• Input: n = 3, edges = [(0, 1)]


• Output: [[0, 1], [2]]


• Explanation: Two components, one for nodes 0 and 1 and another for node 2.

Constraints:

• The number of nodes n will be in the range 1 to 1000.


• The edges list length will be at most n(n-1)/2.

Background: Caching is vital for optimizing performance in systems like Amazon Web Services that frequently access the same data. An LRU cache helps to store frequently accessed data items and remove the least recently used ones when the cache reaches its capacity.
Problem statement: Implement a data structure that implements a Least Recently Used (LRU) cache. It should support the following operations: get(key) and put(key, value). The get method retrieves the value of the key if the key exists in the cache, otherwise it returns -1. The put method updates the value of the key if the key already exists in the cache, otherwise, it adds the key-value pair to the cache. If the number of keys exceeds the capacity, it should invalidate the least recently used key before inserting a new key-value pair.

• Function/class signature:

- class LRUCache
- def __init__(self, capacity: int): return type None
- def get(self, key: int) -> int: return type int
- def put(self, key: int, value: int) -> None: return type None
Example 1:

• Input: cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1)


• Output: 1


• Explanation: Returns 1 as it's the value corresponding to key 1.

Example 2:

• Input: cache.put(3, 3)


• Output: None


• Explanation: This will evict key 2 since the cache capacity is 2 and key 2 is the least recently used.

Constraints:

• The capacity of the cache will be between 1 and 3000.


• All keys and values are integers within the range of 0 to 10^4.

1. Background: In Amazon's e-commerce platform, efficient data retrieval is crucial for providing a seamless user experience. An LRU (Least Recently Used) cache helps reduce access time and improve performance by storing the most frequently accessed items in memory.
2. Problem statement: Implement a data structure that supports the following operations: get(key) - gets the value of the key if the key exists in the cache, otherwise returns -1. put(key, value) - updates or inserts the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. The get and put operations should be done in O(1) time complexity.
3. Function/class signature:
- def get(self, key: int) -> int:
- def put(self, key: int, value: int) -> None:
4. Example 1:
- Input: cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3);
- Output: 1
- Explanation: Returns 1 because key 1 is accessed, and now key 2 is the least recently used.
5. Example 2:
- Input: cache.put(4, 4); cache.get(2);
- Output: -1
- Explanation: Returns -1 because key 2 has been evicted from the cache.
6. Constraints:
- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^4
- Each operation is guaranteed to be valid, meaning the key exists for get operations and the capacity will not be exceeded for put operations.

Amazon needs an efficient way to manage delivery routes across its vast logistics network. This involves determining all potential paths between locations in the network.
Problem statement: Given a directed acyclic graph representing delivery routes between locations, return all possible paths from a starting location start to a destination location end. Each path must be returned in the order they are found.

• List<List<String>> allPaths(String[][] graph, String start, String end) - Returns a list of all paths from start to end.

Example 1:
Input: `graph = [[

Background: Amazon Mobile and Web Services can greatly benefit from an optimized notification system. This system is crucial for enhancing customer experience by managing notifications effectively and ensuring delivery reliability.
Requirements:
1. Create a NotificationSystem class to manage notifications.
2. Allow users to subscribe and unsubscribe to notifications.
3. Enable scheduling notifications for specific times.
4. Provide functionality for sending out notifications to all subscribers.
5. Ensure that notifications can be prioritized based on urgency.
Class API:

• def __init__(self): return type None, initializes the notification system.


• def subscribe(self, user_id: str) -> None: return type None, adds user to subscription list.


• def unsubscribe(self, user_id: str) -> None: return type None, removes user from subscription list.


• def schedule_notification(self, user_id: str, message: str, send_time: datetime) -> None: return type None, schedules a notification.


• def send_notifications(self) -> None: return type None, sends out all scheduled notifications.

Example 1:

• Input sequence: subscribe("user1"); schedule_notification("user1", "Order shipped!", datetime.now())


• Output: None


• Explanation: User 'user1' subscribed and a notification scheduled.

Example 2:

• Input sequence: send_notifications()


• Output: "Notifications sent to all subscribers."


• Explanation: Executes sending notifications to all users.

Constraints:

• The system must handle up to 10000 subscriptions concurrently.


• Notifications can be sent at most once every minute.

Background: Amazon has a vast range of services, and a user-friendly ticket booking system similar to BookMyShow can enhance their entertainment sector's offerings. This system is critical for managing ticket availability and customer satisfaction.
Requirements:
1. Create a class called TicketBooking that manages shows and tickets.
2. The class must allow adding new shows with specific details (name, time, and total seats).
3. Enable booking of tickets while ensuring only available seats are bookable.
4. Provide a method to view available tickets for each show.
5. Implement a method to cancel a booking.
Class API:

• def __init__(self): return type None, initializes the booking system.


• def add_show(self, show_name: str, show_time: str, total_seats: int) -> None: return type None, adds a new show.


• def book_ticket(self, show_name: str, number_of_seats: int) -> str: return type str, books tickets if available.


• def cancel_booking(self, show_name: str, number_of_seats: int) -> str: return type str, cancels booked tickets.


• def available_tickets(self, show_name: str) -> int: return type int, returns remaining tickets.

Example 1:

• Input sequence: add_show("Spider-Man", "2022-10-01 19:00", 100); book_ticket("Spider-Man", 5); available_tickets("Spider-Man")


• Output: 95


• Explanation: 5 tickets booked, 95 remaining.

Example 2:

• Input sequence: cancel_booking("Spider-Man", 3); book_ticket("Spider-Man", 2)


• Output: "Successfully booked 2 tickets."

Constraints:

• The maximum number of shows should not exceed 1000.


• Each show can have a maximum of 500 seats.