Solve stock, BFS path, and merge intervals
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: 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.
Best Stock Trade with One Transaction
Return [max_profit,buy_day,sell_day], or [0,-1,-1] if no profitable trade exists.
Examples
Input: ([7, 1, 5, 3, 6, 4],)
Expected Output: [5, 1, 4]
Explanation: Buy day 1 sell day 4.
Input: ([7, 6, 4],)
Expected 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
Input: (5, [(1, 2), (1, 3), (2, 5), (3, 5)], 1, 5, [])
Expected Output: [1, 2, 5]
Explanation: Tie chooses path through 2.
Input: (4, [(1, 2), (2, 4), (1, 3), (3, 4)], 1, 4, [2])
Expected 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
Input: ([[1, 3], [3, 5], [8, 9]],)
Expected Output: [[1, 5], [8, 9]]
Explanation: Touching intervals merge.
Input: ([],)
Expected Output: []
Explanation: Empty input.