~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

Locks

Reader-writer and modal locks

Many readers or one writer; fairness so writers don't starve.

Notes

Recognise it when: many readers and occasional writers share data; "shared vs exclusive" modes; lock modes that can coexist (a mode-compatibility matrix).

class RWLock:
    def __init__(self):
        self.cond = threading.Condition()
        self.readers = 0
        self.writer = False
        self.waiting_writers = 0

    def acquire_read(self):
        with self.cond:
            # Writer preference: new readers wait while a writer is queued.
            self.cond.wait_for(lambda: not self.writer and self.waiting_writers == 0)
            self.readers += 1

    def release_read(self):
        with self.cond:
            self.readers -= 1
            if self.readers == 0:
                self.cond.notify_all()

    def acquire_write(self):
        with self.cond:
            self.waiting_writers += 1
            self.cond.wait_for(lambda: not self.writer and self.readers == 0)
            self.waiting_writers -= 1
            self.writer = True

    def release_write(self):
        with self.cond:
            self.writer = False
            self.cond.notify_all()

Fairness: reader preference starves writers, and writer preference starves readers. FIFO fairness means a ticket number or a queue of waiters, where each waiter proceeds only when it's at the front and compatible with the current holders.

Gotchas: notify_all after every release, releasing exactly as many times as you acquired, and upgrading a read lock to a write lock deadlocks if two readers try it at once.

3 problems

Concurrency

Locks Mutexes, lock ordering, readers and writers.

Reader-writer and modal locks

esc