MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns Module 8

Stacks and monotonic stacks interview questions

Interview questions on stacks and monotonic stacks: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

27 questions: 4 warm-ups and 23 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher to mid

    How do you recognise that a coding problem wants a stack?

    Answered in the lesson Stack patterns: nesting and undo

  2. Fresher to mid

    In Java, should a stack be a java.util.Stack or an ArrayDeque, and does it matter which end you push to?

    Answered in the lesson Stack patterns: nesting and undo

  3. Fresher to mid

    When is a counter enough to check brackets, and when do you need a stack?

    Answered in the lesson Bracket matching and minimum fixes

  4. Fresher to mid

    What does a monotonic stack keep, and why are the values on it in order?

    It keeps the positions whose answer is still open, in the order they arrived. In a next-greater scan, a position waits on the stack until a later value beats it. The values on the stack never rise from the bottom to the top, because a newer value larger than an older one would already have popped it. That order is what makes the method fast: a new value can only answer a run of the newest positions, at the top, so it pops them and stops at the first position it does not beat. Each position is pushed once and popped at most once, so a whole list costs O(n). Keep positions rather than values: the value is one lookup away, and the answer is often a distance.

    From the lesson Next greater element with a monotonic stack

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

  1. Fresher to mid

    An editor lets people type, delete and paste anywhere in a document of up to 50 MB. Design undo and redo: what does each stack entry store, what happens to the redo stack after a new edit, and how do you keep the history's memory bounded?

    What it tests
    Inverse operations against snapshots, the redo rule after a new edit, grouping keystrokes, and bounding the history's memory with numbers.
    First step
    Compare what an entry could store before choosing. A snapshot of the whole document costs up to 50 MB per step, so 100 steps could need 5 GB. An inverse operation stores only a position and the characters inserted or removed, so it is as large as the edit itself. Choose operations, then list what each kind of edit needs to be reversed exactly.
    Follow-ups

    From the lesson Stack patterns: nesting and undo

    Opening the model answers with your pass…

    Model answers open with any MySmartCoPilot pass.

    • Pro pass · 1 week₹79$2.99
    • 30 days₹179$5.99
    • 1 year₹1,699$45

    One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

    Choose a passI have a licence key

    It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  2. Mid to senior

    Your path simplifier passes every test. A user reports that for a folder reached through a symbolic link, your answer for "../config" is not where the operating system goes. Explain why, say when simplifying the text is still the right choice, and what you would change.

    What it tests
    Lexical against physical resolution of "..", symbolic links, and the security cost of checking a path before it is resolved.
    First step
    Draw the link. Say /srv/app is a symbolic link to /data/releases/v7. As text, /srv/app/../config simplifies to /srv/config. The operating system follows the link first, so ".." from inside it is /data/releases, and the path means /data/releases/config. Simplifying the text treats ".." as "drop the last name", which is right only when that name is a real folder.
    Follow-ups

    From the lesson Stack patterns: nesting and undo

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  3. Mid to senior

    A code editor must underline the first bracket that breaks a file of up to 20 MB, and update the underline within 16 ms of every keystroke. A full rescan is too slow. What do you store, and what does one edit cost?

    What it tests
    Incremental checking: what an edit cannot change, summaries of blocks that combine, and costing a rescan against a frame budget with numbers.
    First step
    Estimate the rescan first: 20 MB at a few hundred megabytes a second is 50 to 100 ms, several frames. Then notice that an edit at position p cannot change the stack before p, so the work should depend on the edit, not on the file.
    Follow-ups

    From the lesson Bracket matching and minimum fixes

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  4. Mid to senior

    A candidate counts the fewest insertions that balance a string of (), [] and {} with a stack: when a closer does not match the top, insert the top's closer. Give an input where this is wrong, a correct method, and its cost for a string of 500 characters.

    What it tests
    Breaking a greedy rule with a small input, the interval dynamic program for mixed brackets, and turning O(n³) into a time estimate.
    First step
    Try the smallest inputs on which the rule has to choose. For (]) it closes the ( early, and then both closers need partners: 3 insertions, while inserting one [ gives ([]). Then ask which choices a correct method must keep open for the first bracket of every piece of the string.
    Follow-ups

    From the lesson Bracket matching and minimum fixes

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  5. Fresher to mid

    A spreadsheet formula uses only round brackets. Remove the fewest brackets so that it becomes valid, and return the result. Explain why no smaller fix exists, and how your answer changes when the formula has 10⁷ characters and memory is tight.

    What it tests
    Marking brackets without a partner, the lower bound behind the count, and a two-pass version that needs no stack of positions.
    First step
    Read from the left, counting open brackets: a ) that arrives with nothing open must go, and so must every ( still open at the end. Before coding, say why each of those removals is forced, using the balance of each prefix: openers minus closers so far.
    Follow-ups

    From the lesson Bracket matching and minimum fixes

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  6. Fresher to mid

    An interviewer points at the while loop inside your for loop and says your next-greater solution is O(n²). Show that it is O(n), and say which input makes the stack largest.

    What it tests
    Aggregate (amortised) analysis by counting pushes and pops, and the worst case of the stack's memory.
    First step
    Count stack operations over the whole run instead of loop iterations per step: ask how many times one index can go onto the stack and how many times it can come off, whatever the input. For the memory, look for an input in which no index is ever popped.
    Follow-ups

    From the lesson Next greater element with a monotonic stack

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  7. Fresher to mid

    Your next-greater code passes the sample tests, but a hidden test fails, and the inputs can repeat values. What do you check first, and which three small tests do you add?

    What it tests
    Reading the tie rule from the statement, matching it to the pop comparison, and minimal tests that pin it down.
    First step
    Start with the statement, not the code: find the words that settle ties, strictly greater or greater than or equal. Then find the one place in your code that decides what an equal value does, and write the smallest input with a repeated value before you change anything.
    Follow-ups

    From the lesson Next greater element with a monotonic stack

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  8. Mid to senior

    A sensor sends one reading a minute for a year, and each reading's wait for a higher one must be reported as soon as it is known. How much memory can the waiting readings take, and how would you bound it?

    What it tests
    Using a monotonic stack online, the worst case of its memory in numbers, and bounding it with a horizon, merged equal readings or storage.
    First step
    A year of minutes is 525,600 readings. A reading leaves the stack only when a higher one arrives, so a stretch in which readings never rise keeps all of them. Size that worst case before designing: at 8 bytes an entry, a minute number and a value, it is about 4.2 MB, small for one sensor and large for a million.
    Follow-ups

    From the lesson Next greater element with a monotonic stack

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  9. Fresher to mid

    A Java min stack keeps a second ArrayDeque<Integer> of minimums. It passes every test with small numbers, but in production, with prices in the thousands, cheapest() sometimes returns a price that was undone. Find the likely bug, explain why the small tests miss it, and fix it.

    What it tests
    Java's boxing rules: == on two Integer objects compares references, the guaranteed cache of -128 to 127, and choosing tests that can fail.
    First step
    Look at every comparison between two values taken from the deques. peekLast() returns an Integer, so == between two of them asks whether they are the same object. Then ask which values Java promises to box into the same object every time.
    Follow-ups

    From the lesson Stacks that know their minimum

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  10. Mid to senior

    A min stack must hold up to 10⁸ 32-bit readings on a device with 1 GB of memory. Compare pairs, a second stack of minimums and the encoded single stack: what does each cost in the worst case, and which do you ship?

    What it tests
    Memory arithmetic with worst cases, how the order of the readings changes the second stack, the encoded trick's width, and how growable arrays allocate.
    First step
    Do the arithmetic before choosing: 10⁸ readings of 4 bytes are 400 MB on their own, and pairs double that to 800 MB. Then ask which order of readings makes the second stack as large as the first.
    Follow-ups

    From the lesson Stacks that know their minimum

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  11. Mid to senior

    Prices arrive one per second, and after each one a dashboard shows the lowest price of the last 600 seconds. Design it with O(1) amortised work per price, prove the bound, and say what the slowest single update costs.

    What it tests
    Building a queue with a minimum from two min stacks, amortised analysis by counting the work per price, and the cost of the worst single update.
    First step
    A window drops its oldest price, so it is a queue, not a stack. Build the queue from two stacks that each know their minimum, then count how many pushes and pops one price causes over its whole life.
    Follow-ups

    From the lesson Stacks that know their minimum

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  12. Mid to senior

    When your histogram stack pops a bar, you compute its width from two indices. Which two, why is that the widest rectangle of the bar's height, and what changes when several bars share a height?

    What it tests
    The invariant of a stack of rising bars, the argument for each boundary, and what ties do to the maximum.
    First step
    Freeze the stack at the moment bar t is popped and write down what you know: which bar caused the pop, which bar now sits under t, and what the order of the stack says about the bars between them. Then argue the left side and the right side separately.
    Follow-ups

    From the lesson Largest rectangle in a histogram

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  13. Fresher to mid

    Your Java histogram solution passes every small test but returns too small an area on a hidden test whose bars are up to 10⁹ tall. What happened, and how do you find every other place where it can happen?

    What it tests
    Integer ranges, how Java evaluates a product of two ints, and checking every intermediate value against the limits.
    First step
    Bound the answer from the limits first: 100,000 bars of 10⁹ make areas up to 10¹⁴, while an int holds at most 2,147,483,647. Then find the first expression that can produce a value that large, and ask in which type Java computes it, not only where the result is stored.
    Follow-ups

    From the lesson Largest rectangle in a histogram

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  14. Mid to senior

    A land-use map has 2,000 × 2,000 cells, each open or built. Find the largest rectangle of open cells: give your plan, its time and memory, and how you would test it.

    What it tests
    Reducing a grid to one histogram per row, costing the plan with numbers, and testing it against a brute force.
    First step
    Fix the row on which the rectangle's bottom edge lies, and look up each column from that row: describe what the open cells above it form, and how that connects to a row of bars. Then cost one row's work and multiply by 2,000 rows.
    Follow-ups

    From the lesson Largest rectangle in a histogram

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  15. Mid to senior

    Your sum of subarray minimums comes out too large whenever the input repeats values. Explain why, fix it, and prove that every subarray is now counted exactly once.

    What it tests
    Contribution counting with nearest smaller elements, a tie rule that counts each subarray once, and a proof that the count is unique.
    First step
    Try the smallest repeat, [1, 1]: its three subarrays have minimum 1 and should add 3, but the solution gives 4. Find which items count the subarray [1, 1], and look at where each item's two boundaries stop when they meet an equal value.
    Follow-ups

    From the lesson Contribution counting with monotonic stacks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  16. Fresher to mid

    The sum of subarray minimums for 300,000 prices of up to 10⁹ must be returned modulo 10⁹ + 7. Where can a Java or JavaScript solution lose exactness, and how do you keep every step exact?

    What it tests
    Bounding intermediate values from the limits, the ranges of 64-bit integers and of exact JavaScript numbers, and where the reductions go.
    First step
    Bound every value from the limits before writing the arithmetic: a price is at most 10⁹, and one element can be the minimum of a great many subarrays. Find the input that makes a single element's share largest, and compare that share with 2⁶³ − 1 and with 2⁵³.
    Follow-ups

    From the lesson Contribution counting with monotonic stacks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  17. Mid to senior

    For an array of daily prices, return the sum over all subarrays of (maximum − minimum), modulo 10⁹ + 7. Give an O(n) method, the cost of the naive one at n = 10⁵, and how you handle the subtraction under the modulus.

    What it tests
    Splitting a sum over subarrays, counting maximums as well as minimums, and subtraction under a modulus.
    First step
    Cost the naive method first: the double loop visits n(n + 1)/2 subarrays, about 5 × 10⁹ at n = 10⁵. Then look for a way to write the sum of all the spreads as sums you already know how to count element by element.
    Follow-ups

    From the lesson Contribution counting with monotonic stacks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  18. Mid to senior

    Explain why deleting a digit that is larger than the digit after it never makes the result worse, and turn that into a proof that the stack method returns the smallest number.

    What it tests
    An exchange or window argument for a greedy rule, the role of the deletion budget, and what equal digits should do.
    First step
    Compare two candidates of the same length at their first difference: the leftmost digits decide. Then ask how far into the code the answer's first digit can lie when only k digits may be deleted, and which of those digits it must be.
    Follow-ups

    From the lesson Greedy choices with a monotonic stack

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  19. Fresher to mid

    Your remove-k-digits solution passes the examples but fails hidden tests. List the edge cases you would test, the bug each one catches, and the smallest input for each.

    What it tests
    Designing edge cases from the exits of the code: deletions left over, leading zeros, an empty result, ties and the budget check.
    First step
    Walk through the code's exits instead of guessing inputs: list every way the loop can end and every form the result can take when it is returned, then give each one the smallest input that reaches it.
    Follow-ups

    From the lesson Greedy choices with a monotonic stack

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  20. Senior to staff

    A code of 10⁹ digits arrives as a stream, and exactly 10⁶ of its digits must be deleted to leave the smallest number, which you write out as you go. How much memory do you need, and when can a digit be written?

    What it tests
    Turning an offline greedy into a streaming one, when a stack entry becomes final under a budget, and memory bounds with numbers.
    First step
    Ask when a kept digit can still be popped: what must happen first to the digits above it, and what that costs from the budget. A digit that can no longer be popped is final and can be written. Then bound, in bytes, how many digits are not yet final when k = 10⁶.
    Follow-ups

    From the lesson Greedy choices with a monotonic stack

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  21. Mid to senior

    Explain why the robots left on your stack can never meet one another, and why settling each new robot moving left against the top of the stack gives the same survivors as the meetings in the order they really happen.

    What it tests
    Stating and keeping a stack invariant for a simulation, the order of meetings, and why independent meetings can be settled in any order.
    First step
    Describe the stack by directions alone: write down, from the bottom up, which ways its robots can be moving, and check that no pair in that pattern can close in. Then check that each kind of newcomer keeps the pattern, and in which order a robot moving left reaches the robots on its left.
    Follow-ups

    From the lesson Stack simulations: collisions and spans

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  22. Senior to staff

    The robots now move at different speeds, and a robot that catches up with a slower one fights it. Which part of the stack solution breaks, what would you use instead, and what does it cost for 200,000 robots?

    What it tests
    Seeing when a nearest-first order no longer holds, choosing a simulation and its data structures for the new order, and updating only what a meeting changes.
    First step
    Find the assumption the stack used: with equal speeds, meetings involve neighbours and happen nearest first, in a known order. Then ask what decides which meeting comes next when speeds differ, and what you would need to find that meeting quickly, again and again.
    Follow-ups

    From the lesson Stack simulations: collisions and spans

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  23. Mid to senior

    A test harness logs the order in which values were pushed to a stack and the order they were popped. Checking a log by simulation works on your tests, but values can repeat. Is the simulation still right? If not, give the smallest failing log and a correct method.

    What it tests
    When a greedy simulation is exact, what repeated values change, and an exact method with its cost.
    First step
    Recall why the simulation is right for distinct values: what would happen to the next value to leave if it were not popped the moment it reaches the top? Then ask whether that argument still holds when another copy of the same value is on the stack or still to be pushed.
    Follow-ups

    From the lesson Stack simulations: collisions and spans

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

All Coding Interview Patterns interview questions · The Coding Interview Patterns track