Coding questions · Amazon
Solve stock, BFS path, and merge intervals
This question evaluates algorithmic problem solving across array scanning, BFS-based constrained shortest-path selection, and interval merging, with emphasis on time/space complexity reasoning, correctness proofs, and thorough edge-case handling. It is commonly asked to assess efficiency guarantees (e.g.
Solve three coding problems; justify complexity and corner cases. A) Best Time to Buy/Sell Stock (one transaction): Given prices[0..n-1] (integers), return (max_profit, buy_day, sell_day). If no profitable trade exists, return (0, -1, -1). Achieve O(n) time, O(1) space. Prove correctness on strictly decreasing arrays and when multiple equal minima/maxima exist; prefer earliest buy when profits tie. B) Shortest path with forbidden nodes: Given an unweighted directed graph G with nodes 1..N (N ≤ 1e5), adjacency list, source s, target t, and a forbidden set F, return the lexicographically smallest shortest path from s to t that avoids F, or [] if none. Use BFS. Explain how to achieve O(N+M) time without sorting neighbors on every expansion, and how you’d adapt if the input edges arrive unsorted. C) Merge half-open intervals: Given intervals [li, ri) with 32-bit integers, merge any that overlap or just touch (e.g., [1,3) and [3,5) ⇒ [1,5)). Return a minimal, start-sorted set. Handle negatives and extremes without overflow, and prove that the total covered measure equals the sum of merged lengths. Provide tests for edge cases.
Best Stock Trade with One Transaction
Return [max_profit,buy_day,sell_day], or [0,-1,-1] if no profitable trade exists.
Examples
Example 1
Input: ([7, 1, 5, 3, 6, 4],)
Output: [5, 1, 4]
Explanation: Buy day 1 sell day 4.
Example 2
Input: ([7, 6, 4],)
Output: [0, -1, -1]
Explanation: No profit.
Lexicographically Smallest Shortest Path Avoiding Forbidden Nodes
Return the lexicographically smallest shortest directed path from source to target while avoiding forbidden nodes.
Examples
Example 1
Input: (5, [(1, 2), (1, 3), (2, 5), (3, 5)], 1, 5, [])
Output: [1, 2, 5]
Explanation: Tie chooses path through 2.
Example 2
Input: (4, [(1, 2), (2, 4), (1, 3), (3, 4)], 1, 4, [2])
Output: [1, 3, 4]
Explanation: Avoid forbidden.
Merge Touching Half-Open Intervals
Merge half-open intervals that overlap or touch and return a minimal start-sorted set.
Examples
Example 1
Input: ([[1, 3], [3, 5], [8, 9]],)
Output: [[1, 5], [8, 9]]
Explanation: Touching intervals merge.
Example 2
Input: ([],)
Output: []
Explanation: Empty input.