Hard 2: Structures working together

Each problem here combines two of the structures you know, a stack with another stack, a dictionary with a queue, a heap with a counter, to do something neither could do alone. As before, the method is described in words; your job is to build it. Any correct solution passes, including a plain-loop one; the described method is what the problem is there to teach.

A queue made of two stacks

A queue serves the oldest item first; a stack gives the newest. You can build a queue out of two stacks. Call them inbox and outbox. To add an item, push it onto inbox. To take the oldest item: if outbox is empty, pop every item from inbox and push each onto outbox, which reverses their order so the oldest is now on top; then pop from outbox. If outbox already has items, just pop from it.

Write drain(operations) that starts with two empty stacks (plain lists), applies a list of operations, and returns the list of items taken out, in order. Each operation is ("add", item) or ("take",). A take on an empty queue is ignored. Do not use pop(0) or a deque: the point is the two stacks.

drain([("add", "a"), ("add", "b"), ("take",), ("add", "c"), ("take",), ("take",)])  ->  ["a", "b", "c"]

def drain(operations):
    ...

A stack that knows its minimum

A normal stack can tell you its top instantly, but not its smallest item. Keep a second stack alongside, holding the minimum so far: whenever you push a value, also push the smaller of that value and the current minimum; whenever you pop, pop both. The top of the second stack is always the minimum of what is left.

Write min_after(operations) that applies a list of operations to an empty stack and returns a list with the current minimum after each operation, or None when the stack is empty. Operations are ("push", value) and ("pop",). A pop on an empty stack is ignored.

min_after([("push", 5), ("push", 3), ("push", 7), ("pop",), ("pop",)])  ->  [5, 3, 3, 3, 5]

def min_after(operations):
    ...

Evaluate a postfix expression

In postfix notation the operator comes after its two operands: 3 4 + means 3 + 4, and 3 4 + 2 * means (3 + 4) * 2. It can be evaluated with a stack in one pass: read the tokens left to right; push every number; when you meet an operator, pop two numbers, apply the operator with the first-popped as the right-hand operand, and push the result. At the end the stack holds exactly one number, the answer.

Write evaluate(expression) for a space-separated expression using integers and the operators +, -, *. The expression is always valid.

evaluate("3 4 +")       ->  7
evaluate("3 4 + 2 *")   ->  14
evaluate("10 2 3 * -")  ->  4

def evaluate(expression):
    ...

Days until a warmer day

Given daily temperatures, find for each day how many days you have to wait until a warmer one, or 0 if none comes. One way: walk the days left to right keeping a stack of days that are still waiting for a warmer day. When a new day arrives, pop every waiting day that is colder than it; for each one popped, the answer is the distance between them. Then push the new day to wait its turn. Days left on the stack at the end get 0.

Write days_until_warmer(temps) that returns the list of waits. Store positions on the stack, not temperatures, since you need the distances.

days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73])  ->  [1, 1, 4, 2, 1, 1, 0, 0]

def days_until_warmer(temps):
    ...

Largest in every window

Given a list and a window size k, find the largest value in each window of k consecutive items. A direct way is to take max of every slice. Another way uses a deque of positions: before adding a new position, drop positions from the back whose values are smaller than the new value, since they can never be the maximum while the new one is in the window; then add the new position at the back. Drop the position at the front if it has fallen out of the window. The front is always the window's maximum.

Write window_max(nums, k) that returns the list of maximums. k is at least 1 and at most the length of the list. Either method is acceptable.

window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)  ->  [3, 3, 5, 5, 6, 7]

from collections import deque

def window_max(nums, k):
    ...

Top k most frequent

Find the k values that appear most often in a list. Count each value with a dictionary, then rank the (value, count) pairs: highest count first, and when counts tie, the smaller value first. sorted or heapq.nsmallest can do the ranking if you give them a key that returns (-count, value); the minus sign makes bigger counts come first.

Write most_frequent(items, k) that returns the k most frequent values as a list, most frequent first. Ties are broken by the value itself in ascending order. k never exceeds the number of distinct values.

most_frequent(["a", "b", "a", "c", "b", "a"], 2)  ->  ["a", "b"]
most_frequent([3, 1, 3, 1, 2], 2)                 ->  [1, 3]

import heapq

def most_frequent(items, k):
    ...

Merge several sorted lists

Merging two sorted lists uses two positions. For many lists, a heap keeps track of which list currently has the smallest front item. Push one entry per list: (first value, list number, 0). Repeatedly pop the smallest, add its value to the result, and if that list has a next item, push (next value, list number, position + 1). Stop when the heap is empty.

Write merge_all(lists) that returns one sorted list containing every item from every list. Lists may be empty. Do not use sort or sorted.

merge_all([[1, 4, 9], [2, 3], [], [5]])  ->  [1, 2, 3, 4, 5, 9]

import heapq

def merge_all(lists):
    ...

Merge overlapping intervals

Each delivery slot is an interval [start, end]. Overlapping or touching slots should be merged into one. Sort the slots by start. Walk through them keeping the current merged slot: if the next slot starts at or before the current one ends, extend the current end to the larger of the two ends; otherwise the current slot is finished, so record it and start a new one from the next slot.

Write merge_slots(slots) that returns the merged slots as a list of [start, end] lists, sorted by start. Do not change the input.

merge_slots([[1, 3], [2, 6], [8, 10], [15, 18]])  ->  [[1, 6], [8, 10], [15, 18]]
merge_slots([[1, 4], [4, 5]])                     ->  [[1, 5]]

def merge_slots(slots):
    ...

Moving average

A sensor sends readings one at a time, and you want the average of the last k readings after each one arrives (or of all readings so far, while there are fewer than k). A deque with maxlen=k keeps exactly the last k, dropping the oldest by itself.

Write moving_averages(readings, k) that returns a list with the average after each reading, rounded to two decimal places.

moving_averages([10, 20, 30, 40], 2)  ->  [10.0, 15.0, 25.0, 35.0]
moving_averages([3, 6, 9], 5)         ->  [3.0, 4.5, 6.0]

from collections import deque

def moving_averages(readings, k):
    ...

First non-repeating character in a stream

Characters arrive one at a time. After each arrival, report the first character seen so far that has appeared exactly once, or "#" if there is none. Keep a count of each character in a dictionary, and a queue of characters in arrival order. After each arrival, drop characters from the front of the queue while their count is more than one; the front, if any, is the answer.

Write first_unique_stream(text) that returns a string with one answer character per arrival.

first_unique_stream("aabc")  ->  "a#bb"
first_unique_stream("abab")  ->  "aab#"

from collections import deque

def first_unique_stream(text):
    ...

Next: Hard 3: Arrays and pointers.