What is the stock span problem and how do you solve it efficiently?
This question involves calculating the span of stock prices over consecutive days. It tests monotonic stack applications and pattern recognition.
Why Interviewers Ask This
The stock span problem is a classic example of applying stacks to find the nearest greater element to the left. It demonstrates the candidate's ability to optimize a naive O(N^2) solution to O(N).
How to Answer This Question
Define the span as the number of consecutive days before the current day where the price was lower. Use a monotonic decreasing stack to store indices of prices. For each new price, pop elements smaller than the current price and calculate the span based on the index of the remaining top element.
Key Points to Cover
- Define span correctly
- Use monotonic decreasing stack
- Pop smaller elements
- Calculate span using indices
Sample Answer
The span is the count of consecutive days prior to today where the price was less than or equal to today's price. I can solve this using a stack to store indices. For each day, I pop indices from the stack where the price is less than the current price. The span is the difference between the current index and the index at the top of the stack.
Common Mistakes to Avoid
- Using a brute force nested loop
- Forgetting to push current index
- Handling equal prices incorrectly
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
How do you find a triplet where a squared equals b squared plus c squared?
Medium
AmazonExplain the concept of graph components in computer science?
Medium
Microsoft CorporationHow do you count ongoing events for multiple query times?
Hard
GoogleWhat is the optimal path to maximize collected rocks in a grid?
Hard
Goldman SachsWhy are you suitable for this specific role at Amazon?
Medium
AmazonDesign a 'Trusted Buyer' Reputation Score for E-commerce
Medium
Amazon