If you’ve spent enough time grinding LeetCode or bombing online assessments on HackerRank, you’ve likely encountered “Design” problems. These problems typically ask you to build a class and implement its functions, requiring you to think beyond simple algorithmic solutions.
“Design” questions are asked in interviews far more often than they appear on LeetCode. When a company proudly advertises that their algorithm interview is “not like LeetCode,” they are almost always asking you their own custom question that could still be classified in the “Design” category.
Encountering these questions in an interview provides a unique opportunity to stand out by showcasing your ability to write clean, efficient, and maintainable code. In this article, I will introduce a technique to achieve this: using dispatch tables to parse inputs in object-oriented design problems.
Input Parsing? Where??
You’ll be asked to parse string inputs pretty frequently in interviews. It’s relatively straightforward to do — so straightforward that the LeetCode platform will do this repetitive grunt work for you.
Though this observation can be made regarding any design problem, we will use the popular 380. Insert Delete GetRandom O(1). In this problem, you are asked to build a data structure that inserts, removes, and retrieves random values from a set — all in O(1) time. LeetCode is generous enough to provide the class and define its functions, and all that needs to be done is implement them!
380. Insert Delete GetRandom O(1) python3 “default code definition” in LeetCode
Looking at this code and then looking at the test cases provided, you’ll notice that the test cases for a Design problem can’t exactly be “plugged into” your code. In this instance, the default testcase (in the problem definition’s “Example 1”) is:
[[],[1],[2],[2],[],[1],[2],[]]
Clearly, LeetCode is doing something under the hood to pass the input into the RandomizedSet class. While platforms like LeetCode and HackerRank have extended this generosity to you, this nicety rarely happens in an interview.
Most of the time, interviewers will simply provide you with a text input, and you must do the input parsing yourself. An interview might present a test case for “Insert Delete GetRandom O(1)” as:
In this scenario, you need to create a function that takes this input array, iterates over it, and passes the arguments into the appropriate RandomizedSet methods. This extra step of input parsing can often be a stumbling block if you’re not prepared.
Bad Ways To Parse Inputs
We’ll continue to use “380. Insert Delete GetRandom O(1)” to demonstrate the effective use of a dispatch table when parsing inputs.
I will not go through the specifics of how to solve this problem. I don’t want to spoil the fun if you’ve never solved this problem before, so I strongly recommend going to LeetCode and solving it yourself before coming back to tackle input parsing!
The Instinctual Way
Sitting on the Zoom call for your final Algorithms interview, your gaze wanders over to a small digital clock sitting to the left of your laptop and your heart sinks. 10:20 AM. Without realizing, you’ve already taken up 20 minutes on introductions! Maybe I shouldn’t have rambled too long about my skiing trip last weekend, you think.
Sitting on the Zoom call for your final Algorithms interview, your gaze wanders over to a small digital clock sitting to the left of your laptop and your heart sinks. 10:20 AM. Without realizing, you’ve already taken up 20 minutes on introductions! Maybe I shouldn’t have rambled too long about my skiing trip last weekend, you think.
def solution(inputs: list) -> list:
action_results = []
random_selector = []
item_indices = dict()
for input in inputs:
params = input.split()
if params[0] == ‘INSERT’:
if params[1] in item_indices:
action_results.append(False)
continue
random_selector.append(params[1])
item_indices[params[1]] = len(random_selector) – 1
action_results.append(True)
elif params[0] == ‘REMOVE’:
if params[1] not in item_indices:
action_results.append(False)
continue
temp = random_selector[item_indices[params[1]]]
random_selector[item_indices[params[1]]] = random_selector[-1]
random_selector[-1] = temp
item_indices[random_selector[item_indices[params[1]]]] =
item_indices[params[1]]
del item_indices[params[1]]
random_selector.pop()
action_results.append(True)
elif params[0] == ‘GETRAND’:
output = random_selector[randint(0, len(random_selector) – 1)]
action_results.append(output)
return action_results
Your interviewer runs tests on the code and you’re relieved to see that everything passes. That little celebration goes on in your head until your interviewer asks: “Can we do better?”
The Repetitive If/Elif Chain
You realize that your code needs a lot of decoupling, and that your random_selector should really be its own data structure. Extracting all your logic into a class, you wonder why you didn’t take a moment to ponder the design in the first place:
class RandomizedSet:
def __init__(self):
self._random_selector = []
self._item_indices = dict()
def insert(self, val: str) -> bool:
if val in self._item_indices: return False
self._random_selector.append(val)
self._item_indices[val] = len(self._random_selector) – 1
return True
def _swap(self, arr: list, i1: int, i2: int):
temp = arr[i1]
arr[i1] = arr[i2]
arr[i2] = temp
def remove(self, val: str) -> bool:
if val not in self._item_indices: return False
i1 = self._item_indices[val]
self._swap(self._random_selector, i1, -1)
self._item_indices[self._random_selector[i1]] = i1
del self._item_indices[val]
self._random_selector.pop()
return True
def getRandom(self) -> str:
return self._random_selector[randint(0, len(self._random_selector) – 1)]
def solution(inputs: list) -> list:
outputs = []
randomized_set = RandomizedSet()
for input in inputs:
params = input.split()
if params[0] == ‘INSERT’:
output = randomized_set.insert(params[1])
outputs.append(output)
elif params[0] == ‘REMOVE’:
output = randomized_set.remove(params[1])
outputs.append(output)
elif params[0] == ‘GETRAND’:
output = randomized_set.getRandom()
outputs.append(output)
return outputs
While writing the input parsing portion of solution(), you can’t help but wrinkle your nose at how repetitive the code has become. After you finish your code refactor, the interviewer asks you the open-ended question, “How would you alter this code if it were in production?” You ask yourself:
How would a future developer feel about writing out the same logic repeatedly for each if statement?
What happens when additional operations need to be supported as more features are added to RandomizedSet?
Using A Dispatch Table
As its Wikipedia article succinctly states, a dispatch table is “a table that contains pointers or memory addresses to functions or methods.” Loosely think of it as a hash table where the keys are data values (strings, ints, etc.) and the values are functions.
The most famous example of a dispatch table came from your operating systems class in the form of virtual method tables, or vtables. The compiler constructs a vtable for each object of a class that contains virtual methods.
We can use a dispatch table to eliminate the repetitive code in our long if/elif chain and streamline our solution. Here’s how to do it (adapted from this article by Martin Heinz):
from collections import defaultdict
class RandomizedSet:
## SAME CODE AS ABOVE
def solution(inputs: list) -> list:
outputs = []
randomized_set = RandomizedSet()
“””
A defaultdict takes in a function as its first parameter that
returns the desires default value (another function in our case),
and the dictionary itself as an optional second parameter.
“””
cases = defaultdict(
lambda *args: lambda *a: “Invalid command”,
{
“GETRAND”: randomized_set.getRandom,
“INSERT”: randomized_set.insert,
“REMOVE”: randomized_set.remove
}
)
for input in inputs:
params = input.split()
outputs.append(cases[params[0]](*params[1:]))
return outputs
Now, we have an elegant solution that does not involve repetitive code, making it really easy for other developers to extend upon.
This technique is tempting to memorize because there’s a lot of “boilerplate” code. However, it’s important for you to know all of the python syntax utilized (e.g., what is a lambda, what is defaultdict, what does [1:] do, what does * mean when passing in python parameters). This way, you’ll not only be able to use this technique effectively but also explain your decisions to an interviewer.
I must acknowledge, however, that passing in variadic arguments is dangerous as it assumes that these arguments are valid for the function being called. If the input isn’t valid, this code would run into all sorts of problems at runtime (run this code locally and test it out!).
Thankfully, interviewers almost always provide the assumption that the input is valid. In the real world, you would need to do some preprocessing or have some sort of validate() function for each input to ensure that they are being passed in as expected.
When NOT To Use A Dispatch Table
We’ve seen that using a dispatch table is effective in eliminating repetitive code and envisioning a future where supported operations can be extended easily. However, there are some cases where a dispatch table might not be the best choice. Here are a few scenarios where a dispatch table might be frowned upon:
Finite Operations with No Extensions Needed. If you have a small, finite number of operations to support with no foreseeable need to add more (e.g., UP, DOWN, LEFT, RIGHT or NORTH, SOUTH, EAST, WEST), a dispatch table might be overkill. In such cases, a dispatch table can appear esoteric and confusing to other developers who expect a straightforward approach.
Simplicity and Readability. Sometimes, the simplicity of a straightforward if/elif chain can be more readable and understandable for other developers and even non-technical team members. If the logic is simple and the number of operations is small, using a dispatch table might unnecessarily complicate the code.
Tooling and Static Analysis. Some static analysis tools might not handle dispatch tables as effectively as they handle straightforward control flow structures. This can lead to issues in automated code reviews or static code analysis, potentially flagging valid code as problematic.
Even if you find that using a dispatch table (or any other coding pattern) is the right decision in an interview, it’s important to discuss when not to use that technique too! This builds trust between you and your interviewer by demonstrating that you are deliberate and have justifications for your decisions.
By considering both the advantages and limitations of dispatch tables, you can make more informed decisions and effectively communicate your reasoning. Hopefully, this will prove a great opportunity to showcase your understanding of software design principles.
Closing Thoughts
There are countless small techniques and patterns that can significantly improve code quality. I only stumbled upon dispatch tables after repeatedly writing long if/elif chains in interviews and online assessments, wondering if there was a better way. That’s why asking questions is of paramount importance in pursuing clean, maintainable code.
When you find yourself writing similar code multiple times to solve various problems (e.g., processing inputs, using breadth-first search), you’ve discovered a coding pattern. With coding patterns, if you think there’s a better way to approach a problem, you’re right. The developer community is so expansive that your question has almost certainly been asked, answered, and iterated on by someone with far more expertise.
So ask questions, search for answers, and learn through those who have encountered the same problem before. Continue to do this, and you’re well on your way to enhancing overall code quality that’s critical to your growth as a software engineer.
If you found this article helpful, you’re welcome to subscribe to my Medium as I aim to continue to share learnings from landing Intern/Graduate Software Engineer roles.
Cover Image by Shyam on Unsplash
