Event Emitter

Medium

Asked by:

24 views

Design an EventEmitter class. This interface is similar (but with some differences) to the one found in Node.js or the Event Target interface of the DOM. The EventEmitter should allow for subscribing to events and emitting them.

Your EventEmitter class should have the following two methods:

subscribe - This method takes in two arguments: the name of an event as a string and a callback function. This callback function will later be called when the event is emitted.
An event should be able to have multiple listeners for the same event. When emitting an event with multiple callbacks, each should be called in the order in which they were subscribed. An array of results should be returned. You can assume no callbacks passed to subscribe are referentially identical.
The subscribe method should also return an object with an unsubscribe method that enables the user to unsubscribe. When it is called, the callback should be removed from the list of subscriptions and undefined should be returned.
emit - This method takes in two arguments: the name of an event as a string and an optional array of arguments that will be passed to the callback(s). If there are no callbacks subscribed to the given event, return an empty array. Otherwise, return an array of the results of all callback calls in the order they were subscribed.

Example 1:

Input: 
actions = ["EventEmitter", "emit", "subscribe", "subscribe", "emit"], 
values = [[], ["firstEvent"], ["firstEvent", "function cb1() { return 5; }"],  ["firstEvent", "function cb1() { return 6; }"], ["firstEvent"]]
Output: [[],["emitted",[]],["subscribed"],["subscribed"],["emitted",[5,6]]]
Explanation: 
const emitter = new EventEmitter();
emitter.emit("firstEvent"); // [], no callback are subscribed yet
emitter.subscribe("firstEvent", function cb1() { return 5; });
emitter.subscribe("firstEvent", function cb2() { return 6; });
emitter.emit("firstEvent"); // [5, 6], returns the output of cb1 and cb2

Example 2:

Input: 
actions = ["EventEmitter", "subscribe", "emit", "emit"], 
values = [[], ["firstEvent", "function cb1(...args) { return args.join(','); }"], ["firstEvent", [1,2,3]], ["firstEvent", [3,4,6]]]
Output: [[],["subscribed"],["emitted",["1,2,3"]],["emitted",["3,4,6"]]]
Explanation: Note that the emit method should be able to accept an OPTIONAL array of arguments.

const emitter = new EventEmitter();
emitter.subscribe("firstEvent, function cb1(...args) { return args.join(','); });
emitter.emit("firstEvent", [1, 2, 3]); // ["1,2,3"]
emitter.emit("firstEvent", [3, 4, 6]); // ["3,4,6"]

Example 3:

Input: 
actions = ["EventEmitter", "subscribe", "emit", "unsubscribe", "emit"], 
values = [[], ["firstEvent", "(...args) => args.join(',')"], ["firstEvent", [1,2,3]], [0], ["firstEvent", [4,5,6]]]
Output: [[],["subscribed"],["emitted",["1,2,3"]],["unsubscribed",0],["emitted",[]]]
Explanation:
const emitter = new EventEmitter();
const sub = emitter.subscribe("firstEvent", (...args) => args.join(','));
emitter.emit("firstEvent", [1, 2, 3]); // ["1,2,3"]
sub.unsubscribe(); // undefined
emitter.emit("firstEvent", [4, 5, 6]); // [], there are no subscriptions

Example 4:

Input: 
actions = ["EventEmitter", "subscribe", "subscribe", "unsubscribe", "emit"], 
values = [[], ["firstEvent", "x => x + 1"], ["firstEvent", "x => x + 2"], [0], ["firstEvent", [5]]]
Output: [[],["subscribed"],["subscribed"],["unsubscribed",0],["emitted",[7]]]
Explanation:
const emitter = new EventEmitter();
const sub1 = emitter.subscribe("firstEvent", x => x + 1);
const sub2 = emitter.subscribe("firstEvent", x => x + 2);
sub1.unsubscribe(); // undefined
emitter.emit("firstEvent", [5]); // [7]

Constraints:

1 <= actions.length <= 10
values.length === actions.length
All test cases are valid, e.g. you don't need to handle scenarios when unsubscribing from a non-existing subscription.
There are only 4 different actions: EventEmitter, emit, subscribe, and unsubscribe.
The EventEmitter action doesn't take any arguments.
The emit action takes between either 1 or 2 arguments. The first argument is the name of the event we want to emit, and the 2nd argument is passed to the callback functions.
The subscribe action takes 2 arguments, where the first one is the event name and the second is the callback function.
The unsubscribe action takes one argument, which is the 0-indexed order of the subscription made before.

Try coding it in LeetCode

Event Emitter

Medium

Asked by:

24 views

Design an EventEmitter class. This interface is similar (but with some differences) to the one found in Node.js or the Event Target interface of the DOM. The EventEmitter should allow for subscribing to events and emitting them.

Your EventEmitter class should have the following two methods:

subscribe - This method takes in two arguments: the name of an event as a string and a callback function. This callback function will later be called when the event is emitted.
An event should be able to have multiple listeners for the same event. When emitting an event with multiple callbacks, each should be called in the order in which they were subscribed. An array of results should be returned. You can assume no callbacks passed to subscribe are referentially identical.
The subscribe method should also return an object with an unsubscribe method that enables the user to unsubscribe. When it is called, the callback should be removed from the list of subscriptions and undefined should be returned.
emit - This method takes in two arguments: the name of an event as a string and an optional array of arguments that will be passed to the callback(s). If there are no callbacks subscribed to the given event, return an empty array. Otherwise, return an array of the results of all callback calls in the order they were subscribed.

Example 1:

Input: 
actions = ["EventEmitter", "emit", "subscribe", "subscribe", "emit"], 
values = [[], ["firstEvent"], ["firstEvent", "function cb1() { return 5; }"],  ["firstEvent", "function cb1() { return 6; }"], ["firstEvent"]]
Output: [[],["emitted",[]],["subscribed"],["subscribed"],["emitted",[5,6]]]
Explanation: 
const emitter = new EventEmitter();
emitter.emit("firstEvent"); // [], no callback are subscribed yet
emitter.subscribe("firstEvent", function cb1() { return 5; });
emitter.subscribe("firstEvent", function cb2() { return 6; });
emitter.emit("firstEvent"); // [5, 6], returns the output of cb1 and cb2

Example 2:

Input: 
actions = ["EventEmitter", "subscribe", "emit", "emit"], 
values = [[], ["firstEvent", "function cb1(...args) { return args.join(','); }"], ["firstEvent", [1,2,3]], ["firstEvent", [3,4,6]]]
Output: [[],["subscribed"],["emitted",["1,2,3"]],["emitted",["3,4,6"]]]
Explanation: Note that the emit method should be able to accept an OPTIONAL array of arguments.

const emitter = new EventEmitter();
emitter.subscribe("firstEvent, function cb1(...args) { return args.join(','); });
emitter.emit("firstEvent", [1, 2, 3]); // ["1,2,3"]
emitter.emit("firstEvent", [3, 4, 6]); // ["3,4,6"]

Example 3:

Input: 
actions = ["EventEmitter", "subscribe", "emit", "unsubscribe", "emit"], 
values = [[], ["firstEvent", "(...args) => args.join(',')"], ["firstEvent", [1,2,3]], [0], ["firstEvent", [4,5,6]]]
Output: [[],["subscribed"],["emitted",["1,2,3"]],["unsubscribed",0],["emitted",[]]]
Explanation:
const emitter = new EventEmitter();
const sub = emitter.subscribe("firstEvent", (...args) => args.join(','));
emitter.emit("firstEvent", [1, 2, 3]); // ["1,2,3"]
sub.unsubscribe(); // undefined
emitter.emit("firstEvent", [4, 5, 6]); // [], there are no subscriptions

Example 4:

Input: 
actions = ["EventEmitter", "subscribe", "subscribe", "unsubscribe", "emit"], 
values = [[], ["firstEvent", "x => x + 1"], ["firstEvent", "x => x + 2"], [0], ["firstEvent", [5]]]
Output: [[],["subscribed"],["subscribed"],["unsubscribed",0],["emitted",[7]]]
Explanation:
const emitter = new EventEmitter();
const sub1 = emitter.subscribe("firstEvent", x => x + 1);
const sub2 = emitter.subscribe("firstEvent", x => x + 2);
sub1.unsubscribe(); // undefined
emitter.emit("firstEvent", [5]); // [7]

Constraints:

1 <= actions.length <= 10
values.length === actions.length
All test cases are valid, e.g. you don't need to handle scenarios when unsubscribing from a non-existing subscription.
There are only 4 different actions: EventEmitter, emit, subscribe, and unsubscribe.
The EventEmitter action doesn't take any arguments.
The emit action takes between either 1 or 2 arguments. The first argument is the name of the event we want to emit, and the 2nd argument is passed to the callback functions.
The subscribe action takes 2 arguments, where the first one is the event name and the second is the callback function.
The unsubscribe action takes one argument, which is the 0-indexed order of the subscription made before.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data types will the event names be? Can they be strings, symbols, or a combination?
What is the expected behavior if an event is emitted but no listeners are registered for it? Should it be ignored, or should an error be thrown?
How should the order of execution be handled when multiple listeners are registered for the same event? Is it guaranteed to be FIFO?
What is the scope of the event emitter? Is it global or should it be tied to a specific object?
Are there any limitations on the number of listeners that can be registered for a single event?

Brute Force Solution

Approach

The event emitter problem involves managing events and their associated actions. The brute force approach tackles this by exhaustively examining every possible relationship between events and actions. It's like trying every single connection to see what works.

Here's how the algorithm would work step-by-step:

For each possible event, go through the entire list of actions one by one.
Check if the current action is supposed to happen when that event occurs.
If it is, record this connection between the event and the action.
If not, ignore this particular combination and move on to the next possible action for that event.
Repeat this process for every event and every action, building a complete map of which actions respond to which events.

Code Implementation

class EventEmitter:
    def __init__(self):
        self.event_listeners = {}

    def on(self, event_name, listener_function):
        if event_name not in self.event_listeners:
            self.event_listeners[event_name] = []
        self.event_listeners[event_name].append(listener_function)

    def emit(self, event_name, data=None):
        # Check if any listeners are registered for the given event.
        if event_name in self.event_listeners:

            # Iterate through all listener functions for the event.
            for listener_function in self.event_listeners[event_name]:
                listener_function(data)

    def remove_listener(self, event_name, listener_function_to_remove):
        # Filter out listener_function_to_remove from the list
        if event_name in self.event_listeners:

            self.event_listeners[event_name] = [
                listener_function
                for listener_function in self.event_listeners[event_name]
                if listener_function != listener_function_to_remove
            ]

            # If the list is now empty, remove the event.
            if not self.event_listeners[event_name]:
                del self.event_listeners[event_name]

    def remove_all_listeners(self, event_name):
        # Remove all listeners associated with the specified event.
        if event_name in self.event_listeners:

            # Delete the key to remove every listener.
            del self.event_listeners[event_name]

Big(O) Analysis

Time Complexity

O(n*m) – Let 'n' be the number of possible events and 'm' be the number of actions. The algorithm iterates through each of the 'n' events. For each event, it then iterates through all 'm' actions to check if that action should be triggered by the current event. Therefore, for each event, we are potentially examining all actions. This process leads to n * m operations. Thus, the time complexity is O(n*m).

Space Complexity

O(E * A) – The brute force approach, as described, builds a map of events and actions. In the worst case, we need to store, for each event, which actions are associated with it. This requires storing a connection for every event-action pair if there is indeed a connection, where E is the number of possible events and A is the number of actions. This relationship map takes O(E * A) auxiliary space to store. No other significant auxiliary data structures are used in the provided description. Therefore, the space complexity is O(E * A).

Optimal Solution

Approach

The event emitter problem involves creating a system where actions (events) can be announced, and other parts of the system can listen for those announcements. The clever part is using a structure that quickly connects announcements to the right listeners, so that we don't have to search all the listeners every time an announcement happens.

Here's how the algorithm would work step-by-step:

Create a way to store all the connections between event names and the functions that want to know when those events happen. A good way to do this is by organizing these connections by event name.
When someone wants to listen for an event, add their function to the list of functions associated with that event name.
When an event happens, find the list of functions that are listening for that event name.
Go through the list of listening functions and call each one, giving them the information related to the event.
If someone wants to stop listening for an event, remove their function from the list of functions associated with that event name. This prevents them from being called when the event happens in the future.
By organizing the connections by event name, we can quickly find the right listeners without having to check every listener in the system whenever an event is announced.

Code Implementation

class EventEmitter:
    def __init__(self):
        self.listeners = {}

    def on(self, event_name, callback_function):
        # Creates a list for event if it does not exist.
        if event_name not in self.listeners:
            self.listeners[event_name] = []

        self.listeners[event_name].append(callback_function)

    def emit(self, event_name, *args):
        # Prevents error if event does not exist.
        if event_name in self.listeners:

            # Execute each of callback functions for event.
            for callback_function in self.listeners[event_name]:
                callback_function(*args)

    def off(self, event_name, callback_function):
        # Ensures removal only occurs if event exists.
        if event_name in self.listeners:
            # Remove the specific callback function from the event's listeners.
            try:
                self.listeners[event_name].remove(callback_function)
            except ValueError:
                pass

Big(O) Analysis

Time Complexity

O(n) – The event emitter's time complexity depends on the operations: on, emit, and off. The 'on' operation adds a listener to a list associated with an event, which is O(1) on average for hashmap implementations. The 'emit' operation iterates through the listeners for a specific event, where 'n' is the number of listeners for that event, resulting in O(n). The 'off' operation removes a specific listener from the listener list, which requires iterating through the list to find the listener, also resulting in O(n) where 'n' is the number of listeners for that event in the worst case. Therefore, the overall complexity is governed by the emit and off operations with O(n) time complexity.

Space Complexity

O(N) – The space complexity is primarily determined by the storage of event listeners. We store event names and their associated listener functions. In the worst-case scenario, each event has a unique listener, or the same listener is added multiple times to the same event, resulting in a data structure (likely a hash map or similar) that grows linearly with the total number of registered listeners. Therefore, where N is the number of listeners, the auxiliary space required scales linearly with N. The storage of event data passed to the listeners is not considered, as it is input related data, not auxiliary space.

Edge Cases

Case	How to Handle
Event name is null or empty string	Throw an IllegalArgumentException or return immediately as event names are required.
Callback is null	Throw an IllegalArgumentException or skip the callback if it's null to avoid NullPointerException.
Maximum number of listeners reached (if a limit is implemented)	Either throw an exception indicating the limit is reached, or silently drop the new listener.
Event emitted with null or undefined arguments	Handle null or undefined arguments gracefully by either filtering them out or passing them as is to the listeners.
Listener throws an exception during event emission	Catch exceptions within the event emission loop to prevent it from crashing and potentially log the error.
Unsubscribing a non-existent listener	Silently ignore the unsubscribe request or return false to indicate failure to remove the listener.
Emitting an event with a very large number of listeners	Consider using asynchronous processing (e.g., setTimeout) to avoid blocking the main thread for too long.
Circular event emission (event A triggers event B, which triggers event A)	Implement a call stack depth check or a mechanism to detect and prevent infinite recursion to avoid stack overflow.

Event name is null or empty string

How to Handle:

Throw an IllegalArgumentException or return immediately as event names are required.

Callback is null

How to Handle:

Throw an IllegalArgumentException or skip the callback if it's null to avoid NullPointerException.

Maximum number of listeners reached (if a limit is implemented)

How to Handle:

Either throw an exception indicating the limit is reached, or silently drop the new listener.

Event emitted with null or undefined arguments

How to Handle:

Handle null or undefined arguments gracefully by either filtering them out or passing them as is to the listeners.

Listener throws an exception during event emission

How to Handle:

Catch exceptions within the event emission loop to prevent it from crashing and potentially log the error.

Unsubscribing a non-existent listener

How to Handle:

Silently ignore the unsubscribe request or return false to indicate failure to remove the listener.

Emitting an event with a very large number of listeners

How to Handle:

Consider using asynchronous processing (e.g., setTimeout) to avoid blocking the main thread for too long.

Circular event emission (event A triggers event B, which triggers event A)

How to Handle:

Implement a call stack depth check or a mechanism to detect and prevent infinite recursion to avoid stack overflow.