Amazon software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
m hubs arranged in a circular ring (Hub 1 is adjacent to Hub m)....Input: Arrayn servers in the network where the security...Input: ArraydeliveryLogs of size n, where each element represents the number of parts delivered in the i-th log. You are also given...Input: Array[start, end] includes both endpoints. Find the maximum number of...Input: Listp 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.def lowest_common_ancestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 3 root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 5 p and q will always exist in the tree.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.class LRUCache: def __init__(self, capacity: int): def get(self, key: int) -> int: def put(self, key: int, value: int) -> None: cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) cache.get(1) 1 cache.put(3, 3) cache.get(2) -1 1 <= capacity <= 10^4.get and put are only called with keys in the range 1 <= key <= 10^4.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.def search(nums: List[int], target: int) -> int:nums = [4,5,6,7,0,1,2], target = 040 is found at index 4 after rotation.nums = [1], target = 0-10 does not exist in the array.1 <= len(nums) <= 10^5-10^4 <= nums[i] <= 10^4All integers in nums are unique.nums is guaranteed to be rotated at some pivot.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.def count_palindromic_substrings(s: str) -> int: "abc" 3 "a", "b", and "c"."aaa" 6 "a", "a", "a", "aa", "aa", and "aaa".1 <= s.length <= 1000 s consists of lowercase English letters only.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:n = 5, routes = [(0, 1, 2), (0, 2, 4), (1, 2, 1), (1, 3, 7), (2, 3, 3)], source = 0, destination = 3 9 n = 4, routes = [(0, 1, 10), (1, 2, 10), (2, 3, 10)], source = 0, destination = 3 30 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]:graph = [[1, 2], [3], [3], []], start = 0 [0, 1, 3, 2] 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: graph = [[1, 2], [3], [3], []], start = 2 [2, 3] 2, it directly visits 3, and since 3 has no outgoing edges, it returns just [2, 3].Constraints: 1 and 1000 nodes. n - 1 other nodes. def find_connected_components(n: int, edges: List[Tuple[int, int]]) -> List[List[int]]: return type List[List[int]]n = 5, edges = [(0, 1), (0, 2), (3, 4)][[0, 2, 1], [3, 4]]n = 3, edges = [(0, 1)][[0, 1], [2]]n will be in the range 1 to 1000.n(n-1)/2.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.class LRUCache def __init__(self, capacity: int): return type Nonedef get(self, key: int) -> int: return type intdef put(self, key: int, value: int) -> None: return type Nonecache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1)1cache.put(3, 3)Noneget(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.def get(self, key: int) -> int:def put(self, key: int, value: int) -> None:cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3);1cache.put(4, 4); cache.get(2);-11 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^4EC2:t3.micro:instance-second or S3:STANDARD:GB-hour. Each rate has an inclusive effective timestamp and an integer price in micro-USD per unit. One USD equals 1,000,000 micro-USD. Rates may be inserted out of chronological order. Repeating an identical rate is a no-op; changing the price at an existing effective timestamp raises ValueError.ValueError without storing the event. Otherwise, freeze the calculated charge at acceptance time; subsequently inserted rates never reprice stored events.false, even if the rate schedule has since changed. Reusing its ID with any different payload raises ValueError. A newly accepted event returns true.(meter, region), summing quantities and their frozen charges. Sort invoice lines lexicographically by meter, then region. Each line contains meter, region, quantity, and subtotal_micro_usd.{"account_id": string, "lines": list, "total_micro_usd": integer, "total_cents": integer}. Sum exact charges before rounding: total_cents = (total_micro_usd + 5000) // 10000, which rounds nonnegative amounts to the nearest cent with ties upward. An empty interval has no lines and zero totals. Invoice calls do not modify state; start >= end raises ValueError.Class APIAWSUsageBilling(account_id: str) — construct an empty ledger for one account.set_rate(meter: str, region: str, effective_at: int, unit_price_micro_usd: int) -> None — register a rate version using the conflict rules above.record_usage(event_id: str, meter: str, region: str, timestamp: int, quantity: int) -> bool — accept a new event or handle its retry atomically.invoice(start: int, end: int) -> dict[str, object] — return the invoice structure specified above.billing = AWSUsageBilling("acct-1")
billing.set_rate("EC2:t3.micro:instance-second", "us-east-1", 0, 7500)
billing.set_rate("S3:STANDARD:GB-hour", "us-east-1", 0, 2000)
billing.record_usage("e1", "EC2:t3.micro:instance-second", "us-east-1", 100, 2)
billing.record_usage("e1", "EC2:t3.micro:instance-second", "us-east-1", 100, 2)
billing.record_usage("e2", "S3:STANDARD:GB-hour", "us-east-1", 110, 5)
billing.invoice(100, 111)true, false, and true. The invoice is:{
"account_id": "acct-1",
"lines": [
{"meter": "EC2:t3.micro:instance-second", "region": "us-east-1", "quantity": 2, "subtotal_micro_usd": 15000},
{"meter": "S3:STANDARD:GB-hour", "region": "us-east-1", "quantity": 5, "subtotal_micro_usd": 10000}
],
"total_micro_usd": 25000,
"total_cents": 3
}2 × 7500 = 15000 micro-USD and S3 costs 5 × 2000 = 10000. The combined charge is 2.5 cents, rounded once to 3 cents.Constraints(meter, region) pairs, and 1,000 rate versions per pair.[0, 10^12]; quantities are in [1, 10^9]; prices are in [0, 10^9] micro-USD per unit.billing = AWSUsageBilling("acct-2")
billing.set_rate("EC2:t3.micro:instance-second", "us-east-1", 0, 7500)
billing.record_usage("a", "EC2:t3.micro:instance-second", "us-east-1", 120, 2)
billing.set_rate("EC2:t3.micro:instance-second", "us-east-1", 100, 4000)
billing.record_usage("a", "EC2:t3.micro:instance-second", "us-east-1", 120, 2)
billing.record_usage("b", "EC2:t3.micro:instance-second", "us-east-1", 130, 1)
billing.invoice(120, 131)true, false, and true. The invoice is:{
"account_id": "acct-2",
"lines": [
{"meter": "EC2:t3.micro:instance-second", "region": "us-east-1", "quantity": 3, "subtotal_micro_usd": 19000}
],
"total_micro_usd": 19000,
"total_cents": 2
}a retains its frozen charge of 2 × 7500 = 15000. Event b uses the newly registered rate and costs 1 × 4000 = 4000. Their grouped quantity is 3, but multiplying that quantity by either single rate would be incorrect.Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free