โ† Amazon questions

Stock Market Range Minimum Query using Segment Tree

Filed under Amazon

Free read 2 of 3

Confirm if updates are point updates or range updates, and whether deletions/insertions dynamically resize the array.

The question

Design a data structure to maintain stock values over various periods and return the minimum stock value over a given query range, implementing a segment tree to support range minimum queries and point updates.

Constraints

  • Array size n up to 10^5.
  • Operations include point updates and range minimum queries.

Examples

Input
arr = [5, 2, 6, 3, 9, 1], query(1, 4)
Output
2
Why
The minimum value in the range index 1 to 4 is 2.

Approach

  1. Confirm if updates are point updates or range updates, and whether deletions/insertions dynamically resize the array.

Tips

  • What they are testing: Test range queries covering single elements, entire array, and updates at boundary indices 0 and n-1.
  • Common mistake: Incorrect segment tree index calculations or failing to properly propagate updates up the tree.

Follow-ups

  • How would you update the segment tree by deleting an old stock value and inserting a new one for a 6-month period in better than O(n) time?

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.