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.

Data Structures & Algorithms (DSA) Module 19

Range queries and tree queries interview questions

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

19 questions: 5 warm-ups and 14 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher to mid

    Why can a sparse-table query use two overlapping blocks for a minimum but not for a sum?

    Answered in the lesson Sparse tables for static range queries

  2. Fresher to mid

    When is a sparse table the wrong choice for range queries?

    Answered in the lesson Sparse tables for static range queries

  3. Fresher to mid

    What does position i of a Fenwick tree store, and why does a prefix query read only O(log n) positions?

    Answered in the lesson Fenwick trees (binary indexed trees)

  4. Fresher to mid

    When do you need a segment tree rather than a Fenwick tree?

    Answered in the lesson Segment trees: build, query, update

  5. Fresher to mid

    Why must a node push its lazy tag to its children before an update or a query visits them?

    Answered in the lesson Segment trees with lazy propagation

Questions with model answers

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

  1. Mid to senior

    A monitoring service keeps 1 million fixed sensor readings as 4-byte integers and must answer 50,000 range-minimum queries a second. The index may use at most 64 MB. Does a full sparse table fit? If not, what would you build, and what does each query cost?

    What it tests
    Sizing a sparse table exactly, knowing structures that trade memory for query time, and checking a query rate against the cost of each query.
    First step
    Count the entries before choosing anything. Levels 0 to 19 are needed, because 2¹⁹ ≤ 1,000,000 < 2²⁰, and level k holds n − 2ᵏ + 1 entries, so the table holds about 19 million numbers. At 4 bytes each that is about 76 MB, over the budget, so look for a structure that keeps queries cheap in far less memory.
    Follow-ups

    From the lesson Sparse tables for static range queries

    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 3 minutes

  2. Fresher to mid

    A teammate turns the team's range-minimum sparse table into range sums by replacing min with addition. The dashboards now show totals that are too high on every range. Explain exactly how much too high, and give two correct fixes with their costs.

    What it tests
    Why the overlap of the two blocks needs an idempotent operation, how to quantify the error, and choosing between prefix sums and disjoint blocks.
    First step
    Write out what the query adds: the block of 2ᵏ values that starts at the left end plus the block of 2ᵏ values that ends at the right end, with k = ⌊log₂ length⌋. They cover the range and share 2ᵏ⁺¹ − length values in the middle, which are added twice. Work it on a range of 5 values.
    Follow-ups

    From the lesson Sparse tables for static range queries

    In the answer:

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

  3. Mid to senior

    A live quiz has 500,000 players with integer scores from 0 to 10,000,000. Scores change about 20,000 times a second, and after every change the player sees their current rank. Which structure do you use, what does each change cost, and how much memory does it need?

    What it tests
    Turning a rank into a prefix count, sizing a Fenwick tree over a range of values, and handling ties and very large value ranges.
    First step
    A rank is a count: one plus the number of players with a higher score. Keep a Fenwick tree of counts indexed by score. A change moves one player from the old score to the new one, and a rank is the number of players minus a prefix count.
    Follow-ups

    From the lesson Fenwick trees (binary indexed trees)

    In the answer:

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

  4. Mid to senior

    A billing service gives discounts to ranges of customer IDs from 1 to 2,000,000, thousands of times a day, and finance asks for the total discount given to any range of IDs at any moment. How do you make both operations O(log n), and how do you convince a reviewer that your formula is right?

    What it tests
    Range updates with range sums on Fenwick trees, deriving the two-tree formula, and testing it against a brute force.
    First step
    Write the discount of one ID as the prefix sum of a difference array d, so that a range discount touches d in only two places. Then expand the sum of the first i discounts in terms of d and look for two prefix sums that trees can keep.
    Follow-ups

    From the lesson Fenwick trees (binary indexed trees)

    In the answer:

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

  5. Fresher to mid

    Your service keeps the prices of 1 million products in a Fenwick tree to answer range sums. Product now also wants the lowest price in any range of product IDs, and prices go both up and down. Can the Fenwick tree answer it? What would you use instead, and what does it cost?

    What it tests
    Why a Fenwick range query needs an operation that can be undone, what a tree of prefix minimums can and cannot do, and choosing a segment tree.
    First step
    A Fenwick range total is prefix(r) minus prefix(l - 1), which works because subtraction undoes addition. Ask what would undo a minimum: nothing does, so look at what the tree can still answer for minimums and where it breaks.
    Follow-ups

    From the lesson Fenwick trees (binary indexed trees)

    In the answer:

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

  6. Mid to senior

    An analytics page shows the highest fare in any range of the last 1,000,000 trips. Fares are corrected after disputes a few thousand times a minute, and 20,000 range questions arrive every second. Which structure do you choose, how much memory does it take, and what does each operation cost?

    What it tests
    Matching a maximum with updates to a segment tree, sizing it, checking the query rate, and keeping a sliding window of trips in a fixed array.
    First step
    List what the data does: values change, the question is a maximum, and maximum cannot be undone. That rules out prefix sums, sparse tables and Fenwick trees, and points to a segment tree over the trips. Then size it and check 20,000 queries a second against its cost per query.
    Follow-ups

    From the lesson Segment trees: build, query, update

    In the answer:

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

  7. Mid to senior

    A dashboard needs both the total and the maximum of any range of 500,000 sensor readings that keep changing. A colleague proposes a Fenwick tree for the totals and a separate segment tree for the maximums. What would you build instead, and what does your design save?

    What it tests
    Designing node values that carry several results, comparing memory and update paths of one structure against two, and keeping both answers consistent.
    First step
    Both questions combine whole ranges, and a segment-tree node can hold more than one number. Store the total and the maximum of its range in every node and work out the combine step, then compare one update path with the two the colleague's design needs.
    Follow-ups

    From the lesson Segment trees: build, query, update

    In the answer:

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

  8. Fresher to mid

    A teammate changed mid = (lo + hi) // 2 to mid = (lo + hi + 1) // 2 in a recursive segment tree "to balance the halves". Now every input with more than one value crashes with RecursionError. Explain exactly why, and what a version that rounds up must change.

    What it tests
    Tracing the recursion on the smallest failing input, the invariant that every child is smaller than its parent, and testing every small size.
    First step
    Trace the build on the smallest failing input, two values: lo = 0 and hi = 1. Compute mid with the new formula and write down the ranges of the two children. Check whether each child is smaller than its parent.
    Follow-ups

    From the lesson Segment trees: build, query, update

    In the answer:

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

  9. Mid to senior

    A catalogue of 1,000,000 products must support "set the price of products l to r to x", "add x to the price of products l to r" and the total price of a range, all mixed. Design the lazy tags, show how two pending updates on one node combine, and give the cost per operation.

    What it tests
    Composing tags of two kinds in the order the updates happened, applying a tag to a sum, and costing the operations.
    First step
    Write down what an add of d and an assignment of c do to one value x, and look for one form that covers both, so that two pending updates on the same node can be merged into one. Then check the merged form on "assign 7, then add 3".
    Follow-ups

    From the lesson Segment trees with lazy propagation

    In the answer:

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

  10. Mid to senior

    A lazy segment tree passes every unit test, but after a few hours of mixed range updates the range totals in production drift away from a nightly recount. How do you find the bug, and which bugs do you suspect first?

    What it tests
    Using a brute-force oracle with random small cases, shrinking a failure, and knowing the usual lazy-propagation bugs and the inputs that expose them.
    First step
    Do not start in production logs. Build an oracle, a plain list that applies each update position by position, and run thousands of tiny random cases that mix every operation kind against both. Keep the first failing case and shrink it until it is a few operations long.
    Follow-ups

    From the lesson Segment trees with lazy propagation

    In the answer:

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

  11. Senior to staff

    A billing system needs range add and range sum over 5 million accounts at 10,000 operations a second. A teammate proposes a lazy segment tree; you suggest two Fenwick trees. Compare them in memory, speed and risk of bugs, and say what would make you switch to the lazy tree.

    What it tests
    Weighing two correct designs by memory, constants and code risk, and knowing which future requirements only a lazy segment tree can meet.
    First step
    Both are O(log n) per operation, so compare what each stores: the lazy tree keeps a sum and a tag in up to 4n slots each, two Fenwick trees keep n + 1 numbers each. Then count the lines of code each needs and where bugs hide.
    Follow-ups

    From the lesson Segment trees with lazy propagation

    In the answer:

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

  12. Mid to senior

    A discussion app stores replies as a tree: every post has one parent, and a thread can be a chain 200,000 replies deep. It must answer "how many replies apart are these two posts?" 5,000 times a second while new replies keep arriving. Design the structure, give its memory, and say what breaks in a recursive version.

    What it tests
    Turning a distance into an LCA query, sizing binary lifting, adding leaves online, and knowing the recursion limit of the language.
    First step
    The distance between two posts is depth(a) + depth(b) − 2 × depth(LCA), so the question is an LCA query. Check what each new reply needs: it is a new leaf whose parent is already in the tree, so whatever is stored for it should come from its parent's entries.
    Follow-ups

    From the lesson Lowest common ancestor: lifting and Euler tours

    In the answer:

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

  13. Senior to staff

    A logistics network's 1,000,000 depots are joined by roads that form a tree, and a nightly batch must answer 10,000,000 route-length queries between depots. Compare binary lifting, an Euler tour with a sparse table, and Tarjan's offline method in time and memory, and choose one.

    What it tests
    Comparing three LCA methods with numbers, recognising an offline batch, and weighing memory against time per query.
    First step
    Every route length is a distance from the root to each depot minus twice the distance to their LCA, so the batch is 10 million LCA queries. Write down, for each method, its preparation, its cost per query and its memory for a million nodes, then ask whether the batch being offline changes the choice.
    Follow-ups

    From the lesson Lowest common ancestor: lifting and Euler tours

    In the answer:

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

  14. Mid to senior

    An org-chart service answers "who is the lowest manager over both of these people?" with binary lifting. A colleague wants to switch to an Euler tour with a sparse table for O(1) queries. The service also answers "who is the manager k levels above this person?". What do you advise, and why?

    What it tests
    Knowing what each LCA method can and cannot answer, k-th ancestors with lifting, and judging whether O(1) queries are worth a second structure.
    First step
    List every question the service answers and check each method against each question. An Euler tour turns LCA into a range minimum, but nothing in it says which node is k levels above another; the lifting table answers that by the bits of k.
    Follow-ups

    From the lesson Lowest common ancestor: lifting and Euler tours

    In the answer:

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

All Data Structures & Algorithms (DSA) interview questions · The Data Structures & Algorithms (DSA) track