Coding (Python)

Short programs to write yourself, such as a simulation, a backtest or a pricing function.

0 of 3 done

01Running positionEasyAbout 3 min
Write running_position(fills). Each fill is a pair (side, qty) with side "B" for a buy or "S" for a sell and a positive quantity. Return the list of positions after each fill and the largest absolute position along the way. Reject bad input with a clear error.
Hint
One pass with a running total is enough. Track the peak of the absolute value in the same loop.
Answer
Keep a running total, add the quantity for a buy and subtract it for a sell, and store each new total. The peak is the maximum of the absolute totals. One pass, so time O(n) and memory O(n) for the output.
Solution
Start with position 0 and an empty list.
For each fill, check the side and the quantity first, then update the position and append it.
Update the peak with the absolute value of the new position, so a large short counts as much as a large long.
Test the empty list, a position that flips from long to short, and bad input.
def running_position(fills): pos, path, peak = 0, [], 0 for side, qty in fills: if side not in ('B', 'S') or not isinstance(qty, int) or qty <= 0: raise ValueError(f'bad fill: {side!r} {qty!r}') pos += qty if side == 'B' else -qty path.append(pos) peak = max(peak, abs(pos)) return path, peak assert running_position([('B', 5), ('S', 8), ('B', 2)]) == ([5, -3, -1], 5) assert running_position([]) == ([], 0)
02Best single round tripMediumAbout 6 min
Write max_profit(prices) for a list of daily prices. It returns the largest profit from one buy followed by one sell on a later day, and 0 if no trade makes money. The interviewer asks for linear time.
Hint
Walk through the prices once. What is the only fact about the past you need on each day?
Answer
Keep the lowest price seen so far. On each day the best sale today is the price minus that low, so keep the maximum of those differences. This takes O(n) time and O(1) memory.
Solution
Comparing every pair of days works, but it takes O(n^2) time.
For a sale on day j, the best buy is the lowest price before day j. A single running minimum gives it.
Update the minimum first and then the best profit. On a day that sets a new low the profit is 0, which never beats the stored value.
Check it against the slow version on random lists, including empty lists and falling prices.
def max_profit(prices): best, low = 0, float('inf') for p in prices: low = min(low, p) best = max(best, p - low) return best assert max_profit([7, 1, 5, 3, 6, 4]) == 5 assert max_profit([9, 7, 4, 1]) == 0 assert max_profit([]) == 0

03A small order bookHardAbout 20 min

Write a class OrderBook with add(side, price, qty, oid), cancel(oid) and best(side). An incoming order first trades against the other side at the resting prices, best price first and earlier orders first at the same price. Whatever is left rests in the book. add returns the list of trades as (resting id, incoming id, price, qty). Say how fast each operation is.

Hint

Use one heap per side with the key (price, arrival number), with the price negated for bids. For cancel, mark the order as empty and remove it only when it reaches the top.

Answer

Two heaps keyed by price and arrival order give price and time priority. Matching pops from the top of the other side, a cancel sets the quantity to 0 and lazy removal cleans the top. add costs O(log n) per order it touches, cancel O(1) and best O(1) on average.

Solution

Each heap entry is [key, seq, qty, oid, price]. The key is -price for bids and price for asks, so the best order sits on top, and seq breaks ties by time.

An incoming buy trades while the best ask is at or below its limit. Each trade takes the smaller of the two quantities at the resting price.

A canceled or filled entry keeps its place with quantity 0, and _top pops such entries before reading the best price.

Test it against a slow book that keeps plain lists and searches them, with thousands of random orders and cancels.

Follow-ups to expect: modifying an order, many orders at one price level, and what changes when latency matters.

import heapq


class OrderBook:
    def __init__(self):
        self.side = {'B': [], 'S': []}   # heaps of [key, seq, qty, oid, price]
        self.live = {}
        self.seq = 0

    def _top(self, s):
        heap = self.side[s]
        while heap and heap[0][2] == 0:   # drop filled or canceled entries
            heapq.heappop(heap)
        return heap[0] if heap else None

    def best(self, s):
        top = self._top(s)
        return top[4] if top else None

    def add(self, s, price, qty, oid):
        other, trades = ('S' if s == 'B' else 'B'), []
        while qty > 0:
            top = self._top(other)
            if top is None or (s == 'B' and top[4] > price) or (s == 'S' and top[4] < price):
                break
            q = min(qty, top[2])
            trades.append((top[3], oid, top[4], q))
            top[2] -= q
            qty -= q
            if top[2] == 0:
                del self.live[top[3]]
        if qty > 0:
            self.seq += 1
            entry = [-price if s == 'B' else price, self.seq, qty, oid, price]
            heapq.heappush(self.side[s], entry)
            self.live[oid] = entry
        return trades

    def cancel(self, oid):
        entry = self.live.pop(oid, None)
        if entry:
            entry[2] = 0


book = OrderBook()
book.add('S', 101, 5, 'a'); book.add('S', 100, 3, 'b'); book.add('S', 100, 4, 'c')
assert book.add('B', 100, 5, 'd') == [('b', 'd', 100, 3), ('c', 'd', 100, 2)]
book.cancel('c')
assert book.best('S') == 101 and book.best('B') is None

Full collection This category has 15 more questions with worked solutions (5 easy, 5 medium, 5 hard). They open with Pro. See pricing, or sign in to your account.

Compare your own answer with the worked solution.

All roles Interview prep