Pub-Sub

easy · observer, topics

Brief-reported interview attribution (unverified): Amazon, Microsoft, Uber

How to approach an LLD round

Requirements

  • Functional: subscribe (one subscriber per topic, duplicates rejected), publish in subscription order, unsubscribe, list topics with subscribers.
  • Non-functional: a publish must deliver to a snapshot (a subscriber that unsubscribes mid-publish still gets that message); delivery is synchronous.
  • Out of scope: async delivery, durable queues, fan-out across processes.

Statement

Design a publish-subscribe system. Subscribers register a callback for a topic; publish(topic, message) delivers the message to every current subscriber of that topic, in subscription order, synchronously. Delivery count is returned.

class PubSub:
    def __init__(self):
    def subscribe(self, topic, subscriber_id, callback):
        # -> True if newly subscribed, False if this subscriber is already on the topic
    def unsubscribe(self, topic, subscriber_id):
        # -> True if the subscription existed, False otherwise
    def publish(self, topic, message):
        # -> number of subscribers the message was delivered to
    def topics(self):
        # -> sorted list of topics that currently have at least one subscriber

Rules. A subscriber may be on several topics. Publishing to a topic with no subscribers delivers nothing and returns 0. Publishing must not break if a callback unsubscribes during delivery (deliver to a snapshot of the subscriber list). topics() lists only topics with subscribers — publishing alone does not create a topic.

Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.

Class design (SOLID)

Subscriber (id + callback; SRP). Topic (subscribers in order + publish to a snapshot; SRP). PubSub orchestrates topics. Pattern: Observer (topic → subscribers).

Public demo

# Public demo: run after implementing the class API above.
p = PubSub()
inbox = []
print(p.subscribe('news', 'alice', lambda message: inbox.append(('alice', message))))
print(p.subscribe('news', 'alice', lambda message: None))

Reference solution and hidden tests

Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.

Concurrency

Publishers and subscribers race: a subscribe during a publish must not corrupt the subscriber list mid-iteration — publish takes a snapshot first, and subscribe/unsubscribe are guarded by one lock per topic. The reference is single-threaded; the lock is described here.

Trade-offs & extensions

Synchronous delivery is simple but a slow subscriber blocks the publisher. Extending: an async Topic (queue + worker) and a Subscriber that filters by message type.

Starter code

class Subscriber:

    def __init__(self, subscriber_id, callback):
        """Initialize the state described in the problem."""
        pass

class Topic:

    def __init__(self, name):
        """Initialize the state described in the problem."""
        pass

    def subscribe(self, subscriber):
        """-> True if newly subscribed, False if this subscriber is already on the topic"""
        pass

    def unsubscribe(self, subscriber_id):
        """-> True if the subscription existed, False otherwise"""
        pass

    def publish(self, message):
        """-> number of subscribers the message was delivered to"""
        pass

class PubSub:

    def __init__(self):
        """Initialize the state described in the problem."""
        pass

    def subscribe(self, topic, subscriber_id, callback):
        """-> True if newly subscribed, False if this subscriber is already on the topic"""
        pass

    def unsubscribe(self, topic, subscriber_id):
        """-> True if the subscription existed, False otherwise"""
        pass

    def publish(self, topic, message):
        """-> number of subscribers the message was delivered to"""
        pass

    def topics(self):
        """-> sorted list of topics that currently have at least one subscriber"""
        pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.

  2. The GraderCharacter joke · No posting date

    Your solution is correct. Your variable names are a crime scene.

  3. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.