Autocoder

D. E. Shaw Coding Round Questions With Solutions

Last updated 2026-11-19

D. E. Shaw screening and coding rounds are commonly described as harder than typical service-company tests: dynamic programming, careful data structures, and problems where a naive solution times out. The eleven practice problems below sit in that range and lean towards the numerical and trading-flavoured themes a quantitative firm likes.

They are practice problems in that style, not real papers. Each has the idea, code, complexity and a typical mistake. For interviews and puzzles see D. E. Shaw interview questions, and for pacing read how to crack a DSA coding round.

What to expect

Reports commonly describe two to three problems at medium to hard difficulty, with strict time limits, so brute force rarely gets full marks. Know dynamic programming on sequences and states, monotonic stacks and deques, heaps, binary search on answers and prefix techniques. Be able to argue correctness, not just run sample cases.

Hiring status

There is no D. E. Shaw page under /hiring on this site, and the only sourced fact we hold is that the firm's fellowships page directs India applicants to deshawindia.com. Use the D. E. Shaw India careers site for current openings, and see how to crack the online assessment for general test strategy.

D. E. Shaw Coding Round Questions With Solutions: questions with worked answers

  1. 1

    Best time to buy and sell a stock with at most k transactions.

    hard

    Let buy[j] be the best balance holding a stock after j transactions and sell[j] the best balance after completing j. For each price update buy[j] = max(buy[j], sell[j-1] - p) and sell[j] = max(sell[j], buy[j] + p). Time O(n k), space O(k). If k is at least n/2 it equals unlimited transactions, so sum all positive differences. Mistake: iterating j upwards while reusing the same price, mixing two transactions on one day; the updates above are safe because buy uses the previous sell value.

    python
    def max_profit(k, prices):
        n = len(prices)
        if n < 2 or k == 0:
            return 0
        if k >= n // 2:
            return sum(max(0, prices[i] - prices[i-1]) for i in range(1, n))
        buy = [float('-inf')] * (k + 1)
        sell = [0] * (k + 1)
        for p in prices:
            for j in range(1, k + 1):
                buy[j] = max(buy[j], sell[j-1] - p)
                sell[j] = max(sell[j], buy[j] + p)
        return sell[k]
  2. 2

    Longest increasing subsequence in O(n log n).

    medium

    Maintain tails, where tails[i] is the smallest tail value of an increasing subsequence of length i + 1. For each number, binary search for its position with bisect_left and replace, or append if larger than all. The length of tails is the answer. Mistake: using bisect_right, which allows equal values and computes the non-decreasing version.

    python
    from bisect import bisect_left
    
    def lis(a):
        tails = []
        for x in a:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)
  3. 3

    Count inversions in an array.

    hard

    Modify merge sort: while merging two sorted halves, when the right element is smaller than the left one, all remaining left elements form inversions with it. Time O(n log n), space O(n). Mistake: using int for the count in Java when n is large; the count can reach n(n-1)/2, so use long.

    python
    def count_inversions(a):
        def sort(arr):
            if len(arr) <= 1:
                return arr, 0
            m = len(arr) // 2
            l, x = sort(arr[:m])
            r, y = sort(arr[m:])
            out, i, j, c = [], 0, 0, x + y
            while i < len(l) and j < len(r):
                if l[i] <= r[j]:
                    out.append(l[i]); i += 1
                else:
                    out.append(r[j]); j += 1
                    c += len(l) - i
            out += l[i:] + r[j:]
            return out, c
        return sort(a)[1]
  4. 4

    Sliding window maximum.

    hard

    Keep a deque of indices whose values are decreasing. For each index, pop from the back while the new value is greater or equal, push the index, drop the front if it left the window, and the front is the maximum. Each index is pushed and popped once: O(n) time, O(k) space. Mistake: storing values instead of indices, so you cannot tell when the front expires.

    python
    from collections import deque
    
    def window_max(a, k):
        dq, out = deque(), []
        for i, x in enumerate(a):
            while dq and a[dq[-1]] <= x:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                out.append(a[dq[0]])
        return out
    java
    static int[] windowMax(int[] a, int k) {
        int n = a.length;
        int[] res = new int[n - k + 1];
        java.util.ArrayDeque<Integer> dq = new java.util.ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
            dq.offerLast(i);
            if (dq.peekFirst() <= i - k) dq.pollFirst();
            if (i >= k - 1) res[i - k + 1] = a[dq.peekFirst()];
        }
        return res;
    }
  5. 5

    Largest rectangle in a histogram.

    hard

    Use a stack of indices with increasing heights. When a bar is shorter than the stack top, pop and compute the area with the popped height, whose width runs from the new stack top plus one to the current index minus one. Append a zero-height sentinel to flush the stack. Time O(n), space O(n). Mistake: forgetting the empty-stack case when computing the width.

    python
    def largest_rect(h):
        st, best = [], 0
        for i, x in enumerate(h + [0]):
            while st and h[st[-1]] >= x:
                height = h[st.pop()]
                left = st[-1] if st else -1
                best = max(best, height * (i - left - 1))
            st.append(i)
        return best
  6. 6

    Running median of a stream.

    hard

    Use a max-heap for the lower half and a min-heap for the upper half. Push into the lower half, move its top to the upper half, then rebalance so the lower half is the same size as the upper half or one larger. The median is the lower top, or the mean of both tops. Insert O(log n), median O(1). Python has only a min-heap, so store negatives for the lower half.

    python
    import heapq
    
    class RunningMedian:
        def __init__(self):
            self.lo, self.hi = [], []   # lo is a max-heap via negatives
        def add(self, x):
            heapq.heappush(self.lo, -x)
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
            if len(self.hi) > len(self.lo):
                heapq.heappush(self.lo, -heapq.heappop(self.hi))
        def median(self):
            if len(self.lo) > len(self.hi):
                return -self.lo[0]
            return (-self.lo[0] + self.hi[0]) / 2
  7. 7

    Edit distance between two strings.

    medium

    dp[i][j] is the cost to convert the first i characters of a into the first j of b. If the characters match, dp[i][j] = dp[i-1][j-1]; otherwise one plus the minimum of insert, delete and replace. Base cases are i and j. O(mn) time, and O(n) space with two rows. Mistake: wrong base cases for empty strings.

    python
    def edit_distance(a, b):
        m, n = len(a), len(b)
        prev = list(range(n + 1))
        for i in range(1, m + 1):
            cur = [i] + [0] * n
            for j in range(1, n + 1):
                if a[i-1] == b[j-1]:
                    cur[j] = prev[j-1]
                else:
                    cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
            prev = cur
        return prev[n]
  8. 8

    Random pick with weights.

    medium

    Build a prefix sum of the weights. To pick, draw a uniform integer in [1, total] and binary search for the first prefix at least the draw. Build is O(n), each pick O(log n). Mistake: drawing from [0, total), which gives a zero draw that lands on the first index with the wrong probability when weights start with zero.

    python
    import random
    from bisect import bisect_left
    from itertools import accumulate
    
    class WeightedPicker:
        def __init__(self, w):
            self.pre = list(accumulate(w))
        def pick(self):
            r = random.randint(1, self.pre[-1])
            return bisect_left(self.pre, r)
  9. 9

    Maximum product subarray.

    medium

    Track both the maximum and minimum product ending at each index, because multiplying by a negative number swaps them. Update with the candidates x, mx times x and mn times x. Time O(n), space O(1). Mistake: tracking only the maximum, which fails on arrays like [-2, 3, -4].

    python
    def max_product(a):
        mx = mn = best = a[0]
        for x in a[1:]:
            cands = (x, mx * x, mn * x)
            mx, mn = max(cands), min(cands)
            best = max(best, mx)
        return best
  10. 10

    Minimum number of jumps to reach the end of an array.

    medium

    Greedy by ranges: track the current reach and the farthest reach. Each time you pass the current reach, you must jump, and the new reach is the farthest seen. Time O(n), space O(1). Mistake: counting a jump at the last index, which is already the target.

    python
    def min_jumps(a):
        jumps = end = far = 0
        for i in range(len(a) - 1):
            far = max(far, i + a[i])
            if i == end:
                jumps += 1
                end = far
                if end >= len(a) - 1:
                    break
        return jumps
  11. 11

    Probability that a knight remains on an n by n board after k random moves.

    hard

    Dynamic programming over steps: p[t][r][c] is the probability of being at the cell after t moves without having left. Each of the eight moves has probability 1/8, and moves that leave the board contribute nothing. The answer is the sum over all cells after k moves. Time O(k n squared times 8).

    python
    def knight_prob(n, k, r, c):
        moves = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]
        cur = [[0.0] * n for _ in range(n)]
        cur[r][c] = 1.0
        for _ in range(k):
            nxt = [[0.0] * n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    if cur[i][j]:
                        for dx, dy in moves:
                            a, b = i + dx, j + dy
                            if 0 <= a < n and 0 <= b < n:
                                nxt[a][b] += cur[i][j] / 8
            cur = nxt
        return sum(map(sum, cur))

Frequently asked questions

How hard is the D. E. Shaw coding round?

Commonly reported as harder than typical campus tests, with dynamic programming and data structure design. The firm does not publish difficulty, so treat this as a guide only.

Which topics should I prioritise?

Dynamic programming, heaps, monotonic stacks and deques, binary search, and probability-based reasoning. See dynamic programming interview questions.

Can I use C++?

Check the platform instructions. C++ and Java are common choices where speed matters.

Do I need quant knowledge for software roles?

Not necessarily, but basic probability and expected value help, since puzzles are commonly reported in interviews.

Related guides

More in Company Interview Questions

See all in this section