Bird
Raised Fist0

What is the time complexity of notifying observers in the thread-safe observer pattern implementation where observers are stored in a dictionary mapping event types to sets of observers, and a snapshot list is created during notification?

medium🪤 Complexity Trap Q13 of Q15
OOP & Design Patterns - Observer Pattern - Event System, Publish-Subscribe
What is the time complexity of notifying observers in the thread-safe observer pattern implementation where observers are stored in a dictionary mapping event types to sets of observers, and a snapshot list is created during notification?
AO(n) where n is total number of all observers across all event types
BO(k) where k is the number of observers subscribed to the notified event type
CO(k + n) where k is observers for event type and n is total observers
DO(1) constant time due to hash set usage
Step-by-Step Solution
Solution:

  1. Step 1: Identify the data structure and notification process

    Observers are stored per event type in sets. Notification locks and copies only the observers for the specific event type.

  2. Step 2: Analyze complexity of notify()

    Notify creates a snapshot list of observers for the event type (size k) and iterates over it, so time is proportional to k, not total n.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Notify cost depends only on observers for that event type [OK]
Quick Trick: Notify complexity depends on observers for event type only [OK]
Common Mistakes:
MISTAKES
  • Assuming notify iterates over all observers regardless of event type
Trap Explanation:
PITFALL
  • Many think notify scans all observers (n), but it only processes k subscribed to event type.
Interviewer Note:
CONTEXT
  • Tests understanding of complexity in event-filtered observer notification.
Master "Observer Pattern - Event System, Publish-Subscribe" in OOP & Design Patterns

2 interactive learning modes - each teaches the same concept differently

SolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More OOP & Design Patterns Quizzes
Adapter vs Facade vs Proxy - Structural Pattern Comparison - Adapter vs Facade vs Proxy - Structural Pattern Comparison - Quiz 5medium Decorator Pattern - Wrapping Behaviour Without Subclassing - Decorator Pattern - Wrapping Behaviour Without Subclassing - Quiz 14medium Decorator Pattern - Wrapping Behaviour Without Subclassing - Decorator Pattern - Wrapping Behaviour Without Subclassing - Quiz 12easy Design Snake and Ladder Game - LLD End-to-End - Design Snake and Ladder Game - LLD End-to-End - Quiz 6medium Design Snake and Ladder Game - LLD End-to-End - Design Snake and Ladder Game - LLD End-to-End - Quiz 8hard Design Snake and Ladder Game - LLD End-to-End - Design Snake and Ladder Game - LLD End-to-End - Quiz 5medium Iterator & Composite Pattern - Traversal Abstractions - Iterator & Composite Pattern - Traversal Abstractions - Quiz 11easy Liskov Substitution Principle - Subtype Behavioural Contract - Liskov Substitution Principle - Subtype Behavioural Contract - Quiz 7medium Open/Closed Principle - Open for Extension, Closed for Modification - Open/Closed Principle - Open for Extension, Closed for Modification - Quiz 13medium Polymorphism - Compile-Time (Overloading) vs Runtime (Overriding) - Polymorphism - Compile-Time (Overloading) vs Runtime (Overriding) - Quiz 14medium