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 2

Arrays, strings and in-place techniques interview questions

Interview questions on arrays, strings and in-place techniques: warm-ups, then what each harder question tests and how a good answer starts.

40 questions: 11 warm-ups and 29 with model answers · Levels: Fresher to senior

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher

    Why is reading a[i] O(1) in an array but O(i) in a linked list?

    Answered in the lesson Arrays in memory: indexing, layout and cost

  2. Fresher

    What is the difference between a Python list and an array.array?

    Answered in the lesson Arrays in memory: indexing, layout and cost

  3. Fresher

    What is the difference between a dynamic array's size and its capacity?

    Answered in the lesson Dynamic arrays: capacity, growth and append

  4. Fresher to mid

    What does "amortised O(1)" promise, and what does it not promise?

    Answered in the lesson Amortised analysis: aggregate, accounting, potential

  5. Fresher

    What does "in place" mean for an array algorithm, and is reversing with items[::-1] in place?

    Answered in the lesson In-place techniques: reverse, rotate, partition

  6. Fresher

    How does a difference array apply many range increments at once?

    Answered in the lesson Prefix sums and difference arrays

  7. Fresher to mid

    A matrix with R rows and C columns is stored row-major in one flat array. Where is cell (i, j), and how do you find the row and column of index k?

    Answered in the lesson Matrices and 2-D arrays

  8. Fresher to mid

    In Kadane's algorithm, why does the running total start again when it drops below zero, and not when it drops below the best total seen so far?

    The running total is the best total of a stretch that ends at the current position. The best stretch ending at the next value is either that value alone or the current stretch extended by it, and extending adds the running total to the value: when the running total is negative, the value alone is larger, so the stretch must start again there. Falling below the best total so far is no reason to restart, because a stretch whose total is not negative can still grow past the best: on [5, −1, 4] the total after −1 is 4, below the best of 5, yet extending reaches 8. Restarting on a total of exactly 0 changes only ties, giving the same total with a later start.

    From the lesson Maximum subarray: from O(n³) to Kadane's O(n)

  9. Fresher to mid

    Why does a fixed window of k items over n items take O(n) time in total, whatever k is, when adding up every window from scratch takes O(n·k)?

    Answered in the lesson Sliding windows: fixed and variable size

  10. Fresher to mid

    Why can the same emoji have a length of 1 in Python, 2 in JavaScript and 4 in Go?

    Answered in the lesson Strings: immutability, Unicode and building text

  11. Fresher to mid

    How do you check that a phrase is a palindrome, ignoring spaces, punctuation and case, with O(1) extra memory?

    Answered in the lesson String techniques: palindromes, parsing, counting

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

    A monitoring service keeps 50 million sensor readings, whole numbers from 0 to 100,000, in a Python list, and its container hits a 2 GB memory limit. Estimate what the list costs, what an array.array would cost, and what else changes if you switch.

    What it tests
    Estimating memory from the layout of references and objects, choosing a typecode from the value range, and the trade-offs of typed storage.
    First step
    Split the list into its two parts: the array of references, 8 bytes per reading on 64-bit CPython, and the int objects the references point to, about 32 bytes each for numbers above 256. Multiply both by 50 million, then size an array by the bytes per value that the range 0 to 100,000 needs.
    Follow-ups

    From the lesson Arrays in memory: indexing, layout and cost

    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

    A C++ function reads v[i] where i can equal v.size() on one rare path. All tests pass and production has run for months. Explain how that can happen, what can go wrong, and how you would catch it before the next release.

    What it tests
    Undefined behaviour of operator[], the difference between size and capacity, and the tools that turn a silent bug into a loud one.
    First step
    Say what the language promises: operator[] checks nothing, so reading past size() is undefined behaviour, not an exception. Then explain why it often looks harmless: the read may land in spare capacity or in the next allocation, which belongs to the program, so nothing crashes and a plausible number comes back.
    Follow-ups

    From the lesson Arrays in memory: indexing, layout and cost

    In the answer:

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

  3. Fresher to mid

    A homegrown vector adds 1,000 slots whenever it is full. Loading 10 million records into it takes minutes, while loading 1 million took a couple of seconds. Explain the numbers and fix it.

    What it tests
    Counting the copies of a growth policy, telling linear from quadratic growth from two measurements, and the geometric argument for growing by a factor.
    First step
    Count the copies. Each growth copies everything stored so far, and a growth comes every 1,000 records, so the copies are 1,000 + 2,000 + 3,000 and so on up to n: about n² ÷ 2,000. Work that out for 1 million and 10 million records and compare the ratio with the ratio of the load times.
    Follow-ups

    From the lesson Dynamic arrays: capacity, growth and append

    In the answer:

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

  4. Mid to senior

    A service appends every incoming event to an in-memory growable array. Appends normally take nanoseconds, but now and then one request stalls for tens of milliseconds while the process's memory briefly jumps. The team says append is O(1). What is happening, and what would you change?

    What it tests
    The difference between amortised and worst-case cost, sizing the stall of one growth, and ways to remove or hide the long operation.
    First step
    Separate the average from the single operation. An append to a full block copies every element into a new block while both blocks are alive, so one append costs O(n) time and briefly needs the old and the new block together. Estimate the copy at the array's size to see whether it explains tens of milliseconds.
    Follow-ups

    From the lesson Dynamic arrays: capacity, growth and append

    In the answer:

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

  5. Mid to senior

    A Go helper receives a slice, appends one element and returns the result. Callers report that their own data sometimes changes after the call and sometimes does not. Explain when it happens, and how you would make the helper safe.

    What it tests
    The slice header of pointer, length and capacity, append's reuse rule, and fixes with copying or the full slice expression.
    First step
    Write down what a slice is: a pointer into an array, a length and a capacity. append writes into the existing array whenever the capacity allows, and only takes a new array when it does not. So ask what the caller passed: a slice with spare capacity, such as a prefix of a longer slice, shares the slots the append writes.
    Follow-ups

    From the lesson Dynamic arrays: capacity, growth and append

    In the answer:

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

  6. Mid to senior

    A job queue is built from two stacks. Its dequeues average 2 µs, but one dequeue in production took 80 ms, and a reviewer says the O(1) claim is wrong. Is it? Explain with numbers, then say what you would change if that slow dequeue matters.

    What it tests
    Separating amortised from worst-case cost, sizing the one expensive operation, and choosing between accepting it, spreading it out and redesigning.
    First step
    Say which claim is true. Each element is pushed onto the inbox once and moved to the outbox at most once, so the moves never exceed the enqueues: O(1) amortised holds. Then find the expensive dequeue: the one that finds the outbox empty and moves the whole inbox. Estimate how many elements an 80 ms move implies.
    Follow-ups

    From the lesson Amortised analysis: aggregate, accounting, potential

    In the answer:

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

  7. Fresher to mid

    Prove that n increments of a binary counter that starts at 0 flip fewer than 2n bits. A teammate then adds a decrement operation and says the same bound still holds for any mix of the two. Show a sequence that breaks it, and give its cost.

    What it tests
    The aggregate argument per bit, why amortised bounds depend on the set of operations, and building an adversarial sequence.
    First step
    Count per bit, not per increment. Bit 0 flips on every increment, bit 1 on every second, bit i on every 2^i-th, so n increments flip at most n + n/2 + n/4 + … bits. Then look for a state where an increment and a decrement are both expensive, and alternate between them.
    Follow-ups

    From the lesson Amortised analysis: aggregate, accounting, potential

    In the answer:

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

  8. Mid to senior

    A hash table doubles its buckets when the load factor reaches 1 and halves them when it falls below 1/2. A workload inserts and deletes one key in turn, again and again. Find the state where this hurts, give the cost per operation with a million keys, and fix the thresholds.

    What it tests
    Spotting resize thrashing at a boundary, costing a resize with numbers, and the gap between grow and shrink thresholds that restores amortised O(1).
    First step
    Find a size where one insert triggers a doubling and the following delete triggers a halving. After the table doubles at load factor 1, it sits at load factor just above 1/2, so a delete drops it below 1/2 at once. Count what each of the two resizes re-inserts.
    Follow-ups

    From the lesson Amortised analysis: aggregate, accounting, potential

    In the answer:

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

  9. Mid to senior

    An array of 100 million 4-byte integers must be rotated right by k, with at most 50 MB of memory beyond the array. Compare copying into a new array, three reversals and the cycle method by memory, writes and speed, and choose one.

    What it tests
    Estimating memory against a budget, counting writes, and knowing that memory access patterns often matter more than the number of writes.
    First step
    Start with the budget: the array is 400 MB, so a full copy needs another 400 MB and is out, and even copying the k items that wrap round fits only while k is below 12.5 million. Then compare the two in-place methods by their writes, about 2n against n, and by how they walk through memory.
    Follow-ups

    From the lesson In-place techniques: reverse, rotate, partition

    In the answer:

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

  10. Fresher to mid

    A report groups student records by grade with an in-place three-way partition. Staff complain that students with the same grade no longer appear in roll-number order, as they did before. Explain why, and give two fixes with their time and memory.

    What it tests
    Stability, why swapping partitions lose the order of equal keys, and the time and memory of stable alternatives.
    First step
    Name the property: the partition is not stable, because a swap moves an item past others with the same grade. Trace a few records, such as roll numbers 101 to 108 with grades B, A, C, B, A, C, B, A, to show a group coming out in a new order. Then look for a method that never moves an item past an equal one.
    Follow-ups

    From the lesson In-place techniques: reverse, rotate, partition

    In the answer:

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

  11. Mid to senior

    A device keeps 10 million readings in flash memory, where a write costs about 100 times a read. About 0.1 % of the readings are invalid and must be removed in place. Compare two methods by the number of writes, and say when the cheaper one is not allowed.

    What it tests
    Counting writes of two removal methods, the role of order, and turning an operation count into a cost estimate.
    First step
    Count writes for both. Read and write indices keep the order, and once the first invalid reading has been passed, every valid reading after it is written one place earlier. Filling each hole with the last reading writes once per removal. Put numbers on both for 10 million readings and 10,000 removals.
    Follow-ups

    From the lesson In-place techniques: reverse, rotate, partition

    In the answer:

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

  12. Fresher to mid

    A booking system holds 200,000 bookings, each reserving a range of seats on a coach of 100,000 seats, and must report how many bookings cover each seat. A loop that adds 1 to every seat of every booking takes too long. Explain the cost with numbers and fix it.

    What it tests
    Costing a nested loop by the total length of the ranges, the difference array as the fix, and the off-by-one at the end of each range.
    First step
    Cost the loop by the seats it touches: the sum of all booking lengths. If a booking covers on average a third of the coach, that is 200,000 × 33,000, about 6.7 × 10⁹ increments. Then look for a way to record a booking without visiting its seats.
    Follow-ups

    From the lesson Prefix sums and difference arrays

    In the answer:

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

  13. Mid to senior

    A dashboard must return the total of any rectangle of a 2,000 × 2,000 grid of daily sales figures, each up to 1,000,000, about a million times a day, using at most 64 MB. Choose the structure, its element type and its memory with numbers.

    What it tests
    Two-dimensional prefix sums, sizing the largest total to choose the element type, and checking the memory against a budget.
    First step
    Find the largest number the table must hold: the whole grid, 4 million cells of up to 10⁶, so up to 4 × 10¹². That rules out 32-bit integers. Then multiply the table's cells, 2,001 × 2,001 with a border of zeros, by the bytes of a type that holds 4 × 10¹², and compare with 64 MB.
    Follow-ups

    From the lesson Prefix sums and difference arrays

    In the answer:

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

  14. Mid to senior

    Range increments now arrive interleaved with point queries, about 100,000 of each, on 1,000,000 positions: a query asks for one position's current value. Why does a difference array stop working, and what would you use instead? Compare the costs.

    What it tests
    Why a difference array needs all updates before any read, costing the alternatives with numbers, and choosing a structure that serves updates and queries mixed together.
    First step
    Say what a query needs: the current value of one position is the running total of the difference array up to it, so with interleaved queries every query would recompute a prefix of up to 10⁶ marks. Count that for 100,000 queries, then look for a structure that keeps prefix totals of a changing array cheap.
    Follow-ups

    From the lesson Prefix sums and difference arrays

    In the answer:

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

  15. Mid to senior

    An image filter sums every pixel of a 4,096 × 4,096 grid of 32-bit values stored row by row. After a refactor swapped its two loops, the same arithmetic runs many times slower. Explain why with numbers, and how you would confirm the cause before changing the code.

    What it tests
    Memory layout, cache lines and vector instructions, estimating the cost with numbers, and measuring before and after a fix.
    First step
    Write down where cell (i, j) lives: row-major, so index i × 4,096 + j. With i innermost, consecutive reads are 4,096 × 4 bytes = 16 KB apart, so every read lands in a different cache line. Count the line loads of both orders before guessing at anything else.
    Follow-ups

    From the lesson Matrices and 2-D arrays

    In the answer:

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

  16. Fresher to mid

    Rotate an n × n matrix a quarter turn clockwise using O(1) extra memory. Prove that your method is correct, count how many cells it writes, and say what changes for a 3 × 5 matrix.

    What it tests
    An in-place algorithm on a matrix, a correctness argument that follows one value, counting the work, and seeing when in place is impossible.
    First step
    Write the target first: the value at (i, j) must end at (j, n − 1 − i). Then look for moves that only swap pairs of cells, such as a transpose and a reversal of each row, and follow one value through them.
    Follow-ups

    From the lesson Matrices and 2-D arrays

    In the answer:

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

  17. Fresher to mid

    Your spiral-order function passes every square test in the suite but lists some cells twice in production. Which matrix shapes break the usual four-bound loop, why, and how would you change the tests so that the bug cannot come back?

    What it tests
    Boundary handling in a loop with four indices, reasoning with an invariant, and building tests from small and extreme shapes.
    First step
    Trace the loop by hand on a single row, 1 × 3. After the top row is listed, top is already past bottom, so a step that lists a bottom row without checking top ≤ bottom lists the same row again.
    Follow-ups

    From the lesson Matrices and 2-D arrays

    In the answer:

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

  18. Mid to senior

    A Java job runs Kadane's scan over a day of per-second changes, each at most 50,000, and reports a best stretch whose total looks reasonable, but an offline tool finds a stretch with about twice that total. The data is correct. What is the likely bug, how do you prove it, and how do you prevent it?

    What it tests
    Integer overflow in a running total, how wrapped arithmetic misleads the scan, bounding totals from the limits, and choosing types and tests.
    First step
    Bound the total from the limits before reading any code: 86,400 seconds × 50,000 = 4.32 × 10⁹, about twice the int limit of 2,147,483,647. A Java int addition that overflows wraps round silently, so check the declared types of the running total and the best total first.
    Follow-ups

    From the lesson Maximum subarray: from O(n³) to Kadane's O(n)

    In the answer:

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

  19. Mid to senior

    Readings arrive one per second without end. After each one a dashboard shows the best stretch so far, with its first and last second, in O(1) memory. Can Kadane's scan do that, and what changes if the dashboard must show the best stretch that ends now and lasts at most an hour?

    What it tests
    Recognising an online algorithm and the invariant that makes it one, then the windowed variant with prefix sums and a monotonic deque.
    First step
    Kadane's state is two totals and two positions, updated from the previous state and the new reading alone, so it already works online. For the last hour, write the best stretch ending now as the current prefix sum minus the smallest prefix sum inside the window.
    Follow-ups

    From the lesson Maximum subarray: from O(n³) to Kadane's O(n)

    In the answer:

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

  20. Mid to senior

    A city's heat map has 300 × 300 cells, each a profit or a loss. Find the rectangle of cells with the largest total. Give an algorithm that is fast enough, its exact cost, and how you would check that it is right.

    What it tests
    Reducing a 2-D problem to the 1-D scan, counting the work precisely, and choosing which dimension to pair up.
    First step
    Fix a top row and a bottom row. The columns between them collapse into one row of column totals, and the best rectangle with exactly those rows is the best stretch of that row, which Kadane's scan finds in O(cols).
    Follow-ups

    From the lesson Maximum subarray: from O(n³) to Kadane's O(n)

    In the answer:

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

  21. Mid to senior

    A sensor reports one reading a second, and a calibration offset makes some readings negative. Find the longest run of consecutive seconds whose average is at most a threshold T, for up to 10⁶ readings. Why does a plain variable window fail here, and what do you use instead?

    What it tests
    Turning an average into a total, recognising when a window's rule stops being monotone, and building a prefix-sum solution with a search over earlier prefixes.
    First step
    Subtract T from every reading: a run has an average of at most T exactly when its adjusted total is at most 0. With negative adjusted values that total can fall and rise again, so a window that drops items on the left can lose the answer. Find a counterexample of three values before you change the method.
    Follow-ups

    From the lesson Sliding windows: fixed and variable size

    In the answer:

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

  22. Fresher to mid

    Find the shortest run of consecutive shops whose footfall reaches a target, where every footfall is 0 or more. Prove that the variable window never skips the answer, and say exactly what breaks if a shop may report a negative correction.

    What it tests
    Stating the invariant of a variable window, proving it from monotonicity, and seeing which step of the proof needs values that are never negative.
    First step
    Fix the end of the run. With values that are never negative, a run that reaches the target still reaches it when it grows to the left, so for each end the starts that work form a prefix of the indices, and the window only needs the last of them.
    Follow-ups

    From the lesson Sliding windows: fixed and variable size

    In the answer:

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

  23. Mid to senior

    Your function for the longest run with at most k distinct labels passes every test but times out on a log of 10⁶ labels. List the likely causes, how you would find the real one, and the fix for each.

    What it tests
    Spotting hidden linear work inside a window step, measuring instead of guessing, and keeping each step O(1).
    First step
    Look inside the loop for work that grows with the window: building set(window) or a slice on every step, list.pop(0) to drop the left item, or summing the counts to find how many labels are present. Any of them turns 10⁶ steps into about 10¹¹ operations when the window is long.
    Follow-ups

    From the lesson Sliding windows: fixed and variable size

    In the answer:

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

  24. Mid to senior

    A chat app limits messages to 100 characters. Users writing in Hindi say their messages are cut too early, and emoji users see messages that end in a broken symbol. What should the limit count, how do you truncate safely, and where do you enforce it?

    What it tests
    Choosing between bytes, code units, code points and grapheme clusters, truncating on a boundary, and keeping client and server consistent.
    First step
    Find which unit each side counts. A JavaScript client's length counts UTF-16 units and a database column may count bytes or code points. A broken symbol means a cut fell inside a surrogate pair or a grapheme cluster; an early cut suggests a byte limit, where every Devanagari letter takes 3 bytes.
    Follow-ups

    From the lesson Strings: immutability, Unicode and building text

    In the answer:

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

  25. Fresher to mid

    A Java service builds a 50,000-line CSV report with report += line in a loop and takes several seconds. Explain the cost with numbers, fix it, and say whether the same loop is slow in Python and in Go.

    What it tests
    Immutability and quadratic copying, estimating the characters copied, the builder idiom in three languages, and not relying on a runtime optimisation.
    First step
    Estimate the copying. With lines of about 60 characters, the k-th += copies about 60 × k characters, so 50,000 lines copy about 60 × 50,000² / 2 = 7.5 × 10¹⁰ characters, which alone explains seconds. Then replace the loop with a StringBuilder.
    Follow-ups

    From the lesson Strings: immutability, Unicode and building text

    In the answer:

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

  26. Mid to senior

    Two user names look identical on screen but your database stores them as different users, and a case-insensitive search misses some names. List the likely causes and design a robust comparison that does not change how names are displayed.

    What it tests
    Unicode normalisation, case folding against lower-casing, confusable characters, and keeping a comparison key apart from the stored display form.
    First step
    Print the code points of both names. If one stores é as U+00E9 and the other as e followed by U+0301, they are canonically equivalent but differ as stored, and normalising both to NFC makes them equal. Then check whether the search lower-cases where it should case-fold.
    Follow-ups

    From the lesson Strings: immutability, Unicode and building text

    In the answer:

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

  27. Mid to senior

    A payment form must accept amounts typed by people in several countries, such as 1,234,567.50, 12,34,567.50 and 1.234.567,50. Write the specification you would implement, say which inputs must be rejected, and explain how you would test the parser.

    What it tests
    Writing a specification before code, keeping locale rules apart from parsing, exact money arithmetic, and designing tests from the specification.
    First step
    Decide what the form promises first: one convention per user, chosen in the settings, or a guess from the text. 1.234 is one thousand two hundred and thirty-four in one convention and one point two three four in another, so a parser that guesses cannot be right for everyone.
    Follow-ups

    From the lesson String techniques: palindromes, parsing, counting

    In the answer:

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

  28. Fresher to mid

    You run-length encode log lines as each character followed by its run length, such as a3b2. A bug report shows a log that decodes to something different. What kind of input breaks the format, and how do you change the encoding so that every input survives the round trip?

    What it tests
    Ambiguity in a home-made format, finding the smallest failing input, and designing a format whose decoder cannot misread data.
    First step
    Look for a character the decoder treats specially. Digits mark lengths, so a digit in the data is read as part of a length: the text a1 encodes as a111, which decodes as 111 copies of a.
    Follow-ups

    From the lesson String techniques: palindromes, parsing, counting

    In the answer:

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

  29. Mid to senior

    A service reads one field from each of 10⁶ comma-separated log lines a second with line.split(',')[3], and profiling shows that most of its time goes there. Why is split costly here, what do you replace it with, and how do you check that the change is correct?

    What it tests
    The allocation cost of fields that are thrown away, scanning with find, measuring before and after, and testing a hand-written scanner against the original.
    First step
    Count what split builds: a list and one new string for every field of the line, 20 here, to keep one of them. Finding the third and fourth commas with find and slicing once builds a single string.
    Follow-ups

    From the lesson String techniques: palindromes, parsing, counting

    In the answer:

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

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