Debt Capital Markets puzzles, solved step by step

Puzzles
100
Traced to a firm
16
Topics
13
Hard
30
Topic
All topicsLeverage, coverage and cash flow9Mental maths and numeracy8Estimation and market sizing7Logic and brainteasers8Cost of capital and valuation riddles7Bond pricing and yield7Compounding, PIK and fees6Issuance and refinancing arithmetic8Credit spreads and default probability8Duration and convexity8Capital structure and recovery8Probability and expected value10Yield curve and forward rates6
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–1 of 1 · filtered from 100Clear filters
  1. 041K investors each send a sorted list of n orders by limit yield. You need one sorted order book. How many comparisons does a naive merge take against a min-heap merge, and why is the heap the right tool as K grows?Logic and brainteasersCoreCitadelNew York · 2026Citadel SecuritiesNew York · 2026

    Try it first

    Merging 64 lists of 1,000 orders: roughly how many comparisons does scanning every list's front order each time take, against a heap?

    Show the worked solution

    A naive scan takes about n K (K minus 1) comparisons; a min-heap takes about n K log2 K. For 64 investors with 1,000 orders each, that is about 4.03 million against 0.384 million, roughly 10 times fewer. The heap holds only each list's current best order, so finding the next order costs a few steps down one branch rather than a look at every list.

    What is the naive way, and where does it waste effort?

    Imagine 64 queues at a bank, each already in order of arrival, and you must call people one at a time in overall order. The naive clerk walks along all 64 queue fronts every time to find the earliest. Every time one order leaves the book, the naive merge re-compares all K front orders, even though only one of them changed. That is K minus 1 comparisons for each of n K orders: 64,000 orders times 63 is 4,032,000 comparisons.

    The other naive route is to merge lists one at a time: merge list 1 and 2, then merge in list 3, and so on. Each merge re-reads everything merged so far, which costs about n times K squared over 2, here about 2.08 million. Better than scanning, but it still grows with the square of K.

    Keep only the K front runners in order, and the merge stays cheap7.42%7.45%7.48%7.50%7.51%7.55%7.60%7.62%next order out:lowest yieldPop the top, push that investor's next order,and re-sort one path: about log2 K = 3 steps here1m2m3m4m216324864K, number of investor lists (n = 1,000 each)scan all heads: 4.03mmin-heap: 0.384m
    A min-heap keeps each investor's best remaining order, with the lowest yield at the top, so each step costs about log2 K comparisons; merging 64 lists of 1,000 orders then takes about 0.384 million comparisons against 4.03 million for scanning every front order.

    Why does a heap fix it?

    A min-heapA tree in which every parent is smaller than its children, so the smallest item is always at the top and can be removed and replaced in a number of steps equal to the tree height. keeps the K front orders only partly sorted: the best is always at the top, and the rest are arranged so that fixing the tree after a change touches one path from top to bottom. Taking the best order and inserting that investor's next one costs about log2 K comparisons instead of K, which is 6 instead of 63 at K of 64. Total work becomes n K log2 K, about 384,000 comparisons.

    The relationship
    scan: nK(K−1)≈4.03mheap: nKlog⁡2K=64,000×6=384,000\text{scan: } nK(K-1) \approx 4.03\text{m} \qquad \text{heap: } nK\log_2 K = 64{,}000 \times 6 = 384{,}000
    norders per investor list, 1,000
    Knumber of investor lists, 64
    \log_2 Kheight of the heap, 6 for 64 lists
    What it says in wordsBoth methods output every order once; the heap makes each output cost the height of a small tree instead of a scan of every list.

    Say where the heap does not matter. With four or five lists, scanning is about as fast and simpler to code, and the orders arrive as fast as a person can read them anyway. The heap earns its place when K is large or the lists do not fit in memory, which is the version in the reported question: arrays read from disk, where only the front of each list is held at once. A careful heap counts about two comparisons per level on the way down, so treat log2 K as the order of the cost, not an exact count.

    Where candidates lose it

    The common miss is proposing to concatenate all the lists and sort them. It works, but costs about n K log2 of n K and throws away the fact that each list is already sorted, which is the whole hint in the question.

    The second loss is naming a heap without saying what sits in it. Say clearly: one entry per list, the current front order, plus which list it came from so you know where to fetch the next one.

    What the interviewer asks next

    • What else does each heap entry need to store besides the yield?
    • How would you merge the lists if they were too large to fit in memory at once?
    • Two orders have the same yield. How do you keep allocation fair in the merged book?

    Asked at Citadel, Equity Capital Markets, New York, 2026 (Wall Street Oasis): I was asked to implement K-way merge of K sorted arrays
    Asked at Citadel Securities, Equity Capital Markets, New York, 2026 (Wall Street Oasis): and the cadidate was expected to use a min heap