Solve stock, BFS path, and merge intervals

Q: Solve stock, BFS path, and merge intervals

This is a Coding & Algorithms interview question from Amazon for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Solve stock, BFS path, and merge intervals

Comments (0)