Start free

Beyond A level · 3 exercises

Python data structures

Choose the structure for what you do most: a heap (heapq) gives the smallest item fast, a deque adds and removes at both ends, a dictionary finds by key.

Two heaps, one for each half, keep the middle value of a stream of numbers.

import heapq
h = []
for x in [5, 1, 8, 3]:
    heapq.heappush(h, x)
print(heapq.heappop(h), heapq.heappop(h))  # 1 3

Watch for: heapq keeps the smallest first: for the largest, push -x and turn it back when you pop.

Exercises

  1. Running medianAfter each new number, print the median of all numbers so far, with one decimal.Expert
  2. Cache hitsA cache holds at most k items.Expert
  3. Autocomplete countsRead a list of words, then answer queries: how many of the words start with the givenExpert
Start with “Running median”