Finding a tech job at the start of 2023 is difficult, and filled with obstacles. Many of these still to this day, to my frustration, seem to be arbitrarily imposed roadblocks in getting a job in an industry that is already saturated with incredible number of opposing languages, frameworks, tools and an equally large amount of applicants. This is further exacerbated by a post-COVID tech slump where even the big players like Amazon, Meta, and Google are jettisoning staff like a sinking ship would do with its cargo.
To my chagrin, the corporate coding interview, for the most part, has refused to test me against any popular framework or tool, or anything remotely related to the job I am applying for. Instead, the challenges presented are always litmus tests for general programming language knowledge, data structures, and application of native libraries in languages to solve problems irrelevant to the position. Best case scenario: you are given a problem where the solution is to “reinvent the wheel.” Worst case, it’s an “esoteric” problem, one with a premise and goal so unusual that you can hardly imagine any scenario where you might encounter even something remotely similar to it. To top it all off, in every scenario, you will always have a very limited amount of time to hastily code a solution.
While I am a big proponent of fully understanding every nook and cranny of a programming language, I hate the idea that my abilities are subject to the metric what amounts to a Rorschach inkblot test. If I am applying to a backend role, test my knowledge on the ORMs the team uses, the notable problems the team faces day-to-day, or task me with developing an API service reflecting such work. If I am applying to web development, test my knowledge on the tools and frameworks used to create web apps. These metrics have greater insight into how I might be a good fit for the position I feel.
Nevertheless, we are forever beset by these questions until a paradigm shift happens. With appropriate knowledge of a programming language, data structures, and algorithms, most of these trials can be overcome. However, often times we forget to apply the same methodologies that grant us success when tackling these frustratingly out-of-scope coding challenges. We need to remember to apply ourselves and take care not to throw away tried-and-true methods that ensure success, even in the midst of outlandish problems and egregious time limits.
The Problem
The coding challenge presented to me recently, to the best of my recollection, went something like this.
A function is presented that accepts two arguments. The first argument is a list of objects, (or dictionaries in the case of Python) whose keys are strings, and have heterogeneous data for corresponding values. These values can be either integers, strings, lists of integers, or nested objects. The nested objects again, have strictly strings for keys, and integers, strings, lists of integers, or nested objects. This is the arrayOfObjects.
[
{
"a": 1,
"b": [1,2],
"c": "abc",
"d": {
"e": "cat"
}
},
{
"a": 2,
"b": [3,4],
"c": "def"
"d": {
"e": "dog"
}
},
# ...
]The second argument is an object that reflects the structure of the objects listed in the first. It has the same keys, but its values are a small number of strings that indicate operations to perform on data by key. This argument is given the name strategies.
{
"a": "add",
"b": "append",
"c": "concatenate",
"d": {
"e": "concatenate"
}
}Given both of these arguments, write the function that applies the strategies across the keys in each object and returns the result as an object with that same structure.
func(arrayOfObjects, strategies) -> resultingObject
The resulting object for the above example arguments would be this:
{
"a": "3",
"b": [1,2,3,4],
"c": "abcdef",
"d": {
"e": "catdog"
}
}There were a few constraints given as well from what I recall:
- There are four possible strategies that can be carried out on the key-value data of the objects.
- add – Basic summation of integer values, restricted to only integer values
- append – List/Array only operation, appends elements in array to the end of array.
- prepend – List/Array only operation, like prepend, but adds inserts elements from one array to the start of the resulting array
- concatenate – String concatenation, limited only to strings. {“a”: “cat” }, {“a”: “dog”}, {“a”: “bird”} -> {“a”: “catdogbird”}
- Number of objects in array of size n limited, n < 10000.
A general skeleton and function signature were given in a collaborative IDE. Both interviewers (head developer and CTO) would watch and sometimes ask that I comment on what I was doing.
Reflecting on My Performance and Decision-Making in My Initial Attempt
Long story short: not good. I achieved only a small portion of the test cases. I tried to code at a break neck speed, worried about the time limit, and began to dispense with programming methodologies one-by-one. I started off by defining the strategies, which can be just functions mapped to string values.
STRATEGIES = {
"add": operator.add
"concat": lambda x, y: x + y,
"append": lambda x, y: x.append(y)
"prepend": lambda x, y: x.insert(0, y)
}General trouble I had was figuring out nested recursion. Trivial case, you are presented with a object array consisting of only objects that contain no nested objects within them. Very few test cases were like this. Some of them had Matroshka doll level nesting.
# Trivial case
[
{
"a": 1,
"b": "cat",
"c": [1,2,3]
},
{
"a": 2
# ...
},
# ...
]
# Nested Case Example
[
{
"a": 1,
"b": {"x" : 1 }
"c": {"y": 1 }
},
{
"a": 2
"b": {"x": 2}
# ...
},
# ...
]
# Matroshka Doll Edge Case
[
{
"a": {
"b": {
"c": {
"d": {
# ...
{
"z": "abc"
}
}
}
}
}
},
{
"a": {
"b": {
"c": {
"d": {
# ...
{
"z": "def"
}
}
}
}
}
},
# ...
]
My code could only handle the trivial cases at the end of it all. My aim was to handle the trivial cases and then go back and implement a solution that handled some level of nesting. In the end, I was not able to handle the nested cases at all. The script needed a lot of changes to retrofit into a recursive function. I would comment more about how I initially implemented this, but the code is lost to the temporary IDE environment, so all I have is a faulty memory that elects most of the time not to remember every terrible solution.
After failing to get all test cases and solve the issue regarding arbitrarily nested objects, I sought to redo the problem the day after the interview with a different approach, and email my would-be future employers to show my commitment and true potential to writing a solution to whatever I may encounter in the future.
Reflecting on my performance during the interview, I realized that I never used any object-oriented programming, not a single self-defined class. This is not to say that I never use OOP methodology or any classes to solve programming problems. Often times interview problems consisting of non-native data types in languages, like binary search trees, require such syntax. But this problem in particular dealt with simple hash-mapped objects, lists, arrays, strings, integers. Types that are found natively in most modern day languages, so technically you could solve this problem with no self-defined classes. However, I think this mindset is rather juvenile, and bereaves oneself of all the benefits of OOP, like code organization, syntactical sugar, and elegant solutions that require less code.
I am not treading any new ground saying such things, I know (in fact older, experienced developers might be ready to close this tab upon hearing such “sky is blue” rhetoric). I speak more to the demographic of a younger developer, or perhaps a developer in the heat of a coding interview, who, due to being under-the-gun, with 40 minutes remaining, may eschew creating a class in favor of shitting out a messy script and hoping that it passes all test cases. The truth is that OOP is a good investment regardless of whether or not you are working under the strict time limits of an interview. The following is supporting evidence for that sort of claim.
2nd Attempt: Simple Custom Iterator & reduce
As I have stated previously, one of the main reasons why I failed to pass all test cases for this problem was that I failed to account for arbitrarily nested objects with the object array. Discussing with both my interviewers, the obvious answer to handle the nested objects would be recursion. This I understood. It was the actual implementation that difficult for me, and was made worse by a script that never accounted for any recursion from the start. What also confused me is the reasoning behind why I was recommended to use the reduce function from the functools native Python library. Looking at the documentation for this function in particular reveals something:
reduce(...)
reduce(function, iterable[, initial]) -> value
Apply a function of two arguments cumulatively to the items of a sequence
or iterable, from left to right, so as to reduce the iterable to a single
value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5). If initial is present, it is placed before the items
of the iterable in the calculation, and serves as a default when the
iterable is empty.
reduce is certainly very applicable here, but we only have one piece of the puzzle to use it. While we can easily define callable functions (in this case, our strategies), how can we define the correct iterable to allow us to iterate over a composite array of objects? With this in mind, I sought to use the iterator OOP methodology for this attempt, to both account for recursion and leverage the reduce function.
Defining Iteration
Custom iteration in Python can be done in quite a few ways. There are both function and class-based approaches to custom iteration.
from typing import List
def odd_iterator(l: List[int]):
for el in l:
if el % 2 != 0:
yield el
class EvenIterator:
def __init__(self, l: List[int]):
self.l = l
def __iter__(self):
for el in self.l:
if el % 2 == 0:
yield el
def main():
example_list = [1,2,3,4,5,6]
# This loop uses default iteration of lists, element by element
# 1 2 3 4 5 6
for el in example_list:
print(el, end=" ")
# This loop uses the function approach, supplying generator, iterates
# over all even elements only goes from odd number to odd number
# 1 3 5
for el in odd_iterator(example_list):
print(el, end=" ")
# This loop uses class based iterator approach, iterates through evens
# 2 4 6
for el in EvenIterator(example_list):
print(el, end=" ")
if __name__ == "__main__":
main()We have options, both the function and class approaches are perfectly fine. We can supply either to reduce or any function with that requires an Iterable argument to go over specific elements in a list to perform a Callable over them.
# 1 + 3 + 5 = 9
odd_sum = reduce(lambda x, y: x + y, odd_iterator(example_list))
# 2 + 4 + 6 = 12
even_sum = reduce(lambda x, y: x + y, EvenIterator(example_list))This implements the trivial add strategy required for this problem, but only over a simple list of integers with reduce. What we need is a way to apply our strategy, a Callable function, over a possibly complex dictionary object that may have key values deeply nested, in an array specified by an Iterable that will apply the strategy only over the key-values that require add strategy.
This is where implementation can differ, and it all depends on what you calculate, when you calculate, and how you implement recursion to work with iteration. I sought to apply strategies to key-values in objects one at a time. This had some time complexity issues later on, which I will expand on later, but it was an approach that worked out in the end.
To account for the nested dictionaries, I also needed to parameterize the iterator by passing a context specific argument that tells the iterator to go to a certain depth deep within each object, key_path. This would play into the recursive stack of the function I would define later. This “key pathing” approach resolves the nested objects with repeated hash table lookups to find the nested values in the array. In some sense, it acts like a linked list iteration, going from pointer to pointer in a C implementation, navigating from memory address to memory address.
example_obj_array = [
{
"a": 1,
"b": "cat",
"c": {
"d": 10
}
},
{
"a": 2,
"b": "cat",
"c": {
"d": 20
}
},
{
"a": 3,
"b": "cat",
"c": {
"d": 30
}
}
]
class ObjArrayReducerIterator:
def __init__(self, obj_array: Dict, key_path: List[str]):
self.obj_array = obj_array
self.key_path = key_path
def __iter__(self):
for obj in self.obj_array:
scope = obj
for key in self.key_path:
scope = scope[key]
yield scope
# Key pathing iterator for list of possibly nested dictionary objects
# Iterator is parameterized, requiring a specific key path to a value
# within each object
# Naive case for elements residing at top level dictionary, only require one hashmap lookup
# 1 2 3
for val in ObjArrayReducerIterator(example_obj_array, ["a"]):
print(val)
# The recursive case, where iterating requires multiple hashmap lookups to
# resolve values deeply nested
# 10, 20, 30
for val in ObjArrayReducerIterator(example_obj_array, ["c", "d"]):
print(val)This iterator can readily be applied with reduce and our callable strategies, but what remains is how to tie it all together and process each key-value pair.
Defining Recursion
With a succinct method of iterating through a Python nested dictionary array key value by key value dealt with. The next problem to tackle the issue of implementing this iteration with a recursive operation that will allow us to descend the depth of any nested dictionary that resides in the array, and apply an appropriate strategy as a Callable to the reduce function.
Recursive functions constitute two things: a base case, and a recursive case. The recursive case here is when we encounter nested dictionaries for key-value pairs, and need to “descend the depths” of these nested structures. The base case is where we encounter actual values that we can compute with strategies.
[
{
# Base case
"a": ...
# Recursive case
"b": {
# Base case
"c": ...
# Recursive case
"d": {
}
}
},
# ...In a sense, our recursive case will only apply in the case where the data type of a value is Dict. In all other cases, int | str | List[int] | List[str] will dictate base case. In another sense, one could look at the corresponding strategies object, and notice that it not only maps out a format and possible data types for result, but also execution of recursive work, where values in the strategies object that are str would be considered base case, and those that are Dict are recursive case. While both do map out the execution of recursion, I elected to use the strategies argument to walk through base and recursive steps.
The iterator we created has a good indicator of how this might be implemented together with the idea of a recursive function. The parameter for the iterator, key_path, can act as a context driven LIFO stack of sorts rather than a list (perhaps it would be more transparent to write it as such). Such data structures are key to any recursion, and in fact a process stack is very thing that makes such programming possible.
# Example: Given
arrayOfObjects = [
{
"a": 1,
"b": {
"c": "abc"
}
},
{
"a": 2,
"b": {
"c": "abc"
}
},
# ...
]
# Picture this as LIFO stack, indicates where
# we are in the depths of a nested dictionary
key_path: List[str] = []
# Encounter base case "a", str, int, etc for value
# push and iterate
key_path.append("a")
res = reduce(
STRATEGIES[strategy],
ObjArrayReducerIterator(arrayOfObjects, key_path)
)
# Pop stack once done with base case
key_path[:-1]
# To "descend depths", push onto the stack in case of recursive
# step, keep that on stack and push again with base or recursive step
key_path.append("b")
# Is this recursive step for "b"? - Yes
# isinstance(val of b, dict)
key_path.append("c")
res = reduce(
STRATEGIES[strategy],
ObjArrayReducerIterator(arrayOfObjects, key_path)
)
# pop base case "c"
key_path[:-1]
# pop recursive step and nested context "b"
key_path[:-1]
# ...Keys within the objects in array are pushed onto it, given to the parameterized iterator we have as argument to collect values across array, then that is passed to reduce with the appropriate strategy, where the same key path is used to determine correct strategy with strategies.
Together with the LIFO stack, the determination of recursive step or base case with isinstance and strategies, together with parameterized iterator and reduce, my recursive function look like this.
# Note that key_path acts less like a list and more like a deque or similar LIFO structure,
# Better rewritten to be such. STRATEGIES is dictionary of callables
def obj_array_reduce(
arrayOfObjects: List[Dict],
strategyObject: Dict,
key_path: List[str]=[]
):
results_map = {}
for key, strategy in strategyObject.items():
key_path.append(key)
# Determination of base/recursive step, true mean recursive step
if isinstance(strategy, dict):
obj = obj_array_reduce(arrayOfObjects, strategy, key_path)
results_map[key] = obj
continue
# Base case
results_map[key] = reduce(
STRATEGIES[strategy],
ObjArrayReducerIterator(arrayOfObjects, key_path)
)
# LIFO stack pop
key_path = key_path[:-1]
return results_mapThis is remarkably short. Especially compared to that of my original script, which easily went over 120 lines. The solution I ended up with after applying these solutions never broke 100 lines. The reason why it is as short as it is, and why recursion seemed to easy is thanks to OOP!
Analysis of Solution
The code above, as far as I can remember, would satisfy all test cases given, since it implements the recursion necessary to handle deeply nested objects. It also handles the possible scenario of same named keys that may reside in different levels of nested objects by attributing key paths, which would make these values distinguishable from each other. Such a case seems trivial to handle here due to key pathing, but I feel that an alternate approach to this problem might find such a scenario difficult to handle. It also is pretty clean, succinct, and easy to read, consisting of around 82 lines of code. Even if I were to fail an edge case or two here, at the very least, my interviewers would understand that I understood OOP principles, and knew how to make readable, reusable, evolvable code, rather than a messy one-time script.
Is this script optimal? Far from it. The general problem with this code is that it is way too slow, and it is quite visible when you look at how many times I iterate through the given object array alone. In general, I think the optimal solution to this problem would only iterate through the array once. O(n), with n being the object array size, would be the goal here, but my code does cannot be characterized as such. Due to the way I worked with reduce, I only calculate one value at a time in a dictionary of say, m values. I call reduce, initialize my iterator with given key path, and pass the appropriate strategy m times, and each time reduce uses that iterator to iterate through and calculate a single value for a key path, iterating through the array m times. The algorithm is then O(mn) or really just O(n^2) – asymptotically quadratic in terms of time. Not ideal. In addition to this, values for keys belonging to nested objects cannot be accessed in O(1), but rather have to suffer a linked list like lookup speed that is bound O(n), since multiple hash table lookups are required for finding such values, but this would be a given for most solutions that do not flatten or alter the given objects in the array.
If one were to optimize this script, it would start by reducing the number of complete iterations of the array of objects. One could program reduce to accept a more complicated callable that returns a dictionary of computed reduced values across a variety of different strategies. Downside to that a far more complex Callable that you need to adapt and pass to reduce. To keep your strategy operations simple, perhaps it may be best to iterate through the array only by the limited amount of strategies that are possible (there are only 4 in this context, not too many, and these are not liable to change as dictated per problem) and go with a Visitor OOP design. Doing so may reduce O(n^2) -> O(4n).
How I Learned to Play it Cool in Coding Interviews
Although I emailed this 2nd solution to my potential employers in less than a day after the initial interview. It turns out that I did not get the job. Regrettable, but I feel as though I have gained new insight that will allow me to take it slow and treat the problem with same integrity as I do with any other project. With such problems and time limits, it does not help us to dispense with object-oriented design just because the clock is ticking. If anything, these methods save time, and may even allow us to succeed rather than fail gracelessly with ad-hoc shotgun wedding scripts.
Keep the faith. keep the integrity. Aim to code in such a way in interviews that the solution will be just evolvable and maintainable as production code. Even if you do fail to get all test cases, you will be able to say something more about your failure than if you dispensed with such important programming methodologies.
Leave a Reply