When it comes to landing a tech job, more often than not you will need to jump through quite a few hoops to land that job you desire. In Software Engineering the interview process involves quite a few series of challenges that you need to pass. One of these is to be able to pass a technical coding test.
Whilst many people will argue that some of the technical problems that are handed out to interview candidates have nothing to do with the real life tasks that they will undertake once hired, the reality is most companies will have some kind of technical test in place that they will use to give to interviewees.
It's impossible to know before hand the kind of techinical task that you will be given in a job interview, but there are some common techinical problems that come up time and again. I will be creating a series of posts that focus on these interview questions and going through how one can solve each problem.
Now, it goes without saying that there isn't a one single correct solution to these coding problems. As each and every engineer is different there will always be different solutions to the same coding problem. In this solution and upcoming solutions to coding problems, I will show you my way of finding a solution to the given problems.
I will try to make each solution as simple as possible and it won't use fancy terse or one liner code. The idea behind these solutions is so that you understand how to actually solve the problem, how the solution works, and hopefully when you understand how the a solution was arrived at you are able to recall it in an interview.
The first problem that we are going to look at in these series of coding interview questions is how to flatten a value. In particular, how to flatten nested objects and nested arrays. There are a few variations of this question that interviewers ask and we will go through both problems and their solutions.
Now, before we start on the problem I have to declare that the solution will be making use of recursion. As I mentioned already, there are different ways to tackle the same problem, but I found that using recursion for this problem was quite effective and easier to understand in my opinion.
So you will need to have a basic understanding of how recursion works in order to be able to undertsand the solution that I present for this problem. So, without further delay let's start on the problem and it's solution.
Write a flatten function that will take in a value and returns a flattened version of the given value. The function should implement the following:
Primitive values should be left unchanged. For example if we pass it a string hello it should return that value without changing it.
Given an empty array or empty object it should return that value without changing it.
Nested arrays should have their values moved up to the top level array. For example, [1, 2, [3, 4, [5, 6]]] should be flattened to [1, 2, 3, 4, 5, 6].
Likewise nested objects should have their key-value pairs moved up to the top level object. For example, {a: 1, b: {c: 2, d: 3, e: {f: 4}}} should be flattened to {a: 1, c: 2, d: 3, f: 4}. Keys b and e
were completely removed since their values were flattened to the top level object.
You can assume that the values or any nested values will not be functions, and object keys will be strings only.
You cannot use the native Array.prototype.flat() function.
You might have a few ideas already, but I highly recommend that you try to come up with a solution yourself first, as this will make you understand think about the problem deeply. Now as for my solution, I will break it up into a series of code snippets that address each requirement and then I will show you the entire function at the end.
Let's start with the first requirement Primitive values should be left unchanged:
function flatten(value) {
// check for null_
if(value === null) {
return value
}
// test for primitive values_
if(typeof value !== "object") {
return value
}
...
The above code addresses the first requirement, we are checking for primitive values first. In the process we cant simply do a check for only objects, as there is an edge case where null === 'object', and in this case our code will break since null does not obviously have keys and values. This is a JavaScript quirk, and its type should not actually be an object. Anyhow, we need to be aware of this fact and make sure that we account for it accordingly.
After checking for null explicitly, we can then check that the given value is not an object. This will cover all of the primitive values, so if we pass in a number 7 we simply return this value.
Next we're going to test for arrays, the process of checking for the type in JavaScript is called 'Duck Typing'. I.e. If it looks like a duck, swims like a duck, and quacks like a duck, then it probably is a duck. So we're going to do a test for Arrays:
function flatten(value) {
...
// check for empty array_
if(Array.isArray(value) && value.length === 0) {
return value
}
We're first going to check for an array using the Array.isArray() function. This function will return either true or false given a value. So we pass in the value and check that it indeed is an array. If it is an array then the && will take us to the right side and then check if the array is empty. If it is we simply return the empty array.
Next we will tackle if we have arrays that are not empty, also if we have empty arrays that are nested these will be removed:
function flatten(value) {
...
// nested empty arrays are removed_
if(Array.isArray(value)) {
return flattenArray(value)
}
For this we will create a helper function flattenArray that will take in an array value and then flatten it. We can assume here that the value which is passed in is an array. Before moving forward we will need to create the helper function.
This function will take a single argument, an array and then it needs to loop over all of the elements inside the array, if a value is also an array the we will beed to iterate over its values until we get all of the nested arrays. Now this sounds like quite a task to implement, but we can actually achieve this with only a few lines of code:
function flattenArray(arr) {
return arr.reduce((acc, curr) => {
return acc.concat(Array.isArray(curr) ? flattenArray(curr) : curr)
}, [])
}
Let's go through this function line by line. We are taking in an array value as the argument arr. Then we simply call the native reduce function on this array. You can read more about the reduce function on MDN.
The reduce function takes in several arguments, but for our purposes we only need two. That is the accumulator which we have abbreviated to acc and the current value denoted by curr. When calling the reduce function we can optionally pass in an intial value, or accumulator. This is the value that will be passed to each iteration of the elements in the array, this value will contain the previous value on each subsquently iteratio of all elements.
We want to end up with a single flattened array, so we simply pass in an empty array as the accumulator [] as the second argument to the reduce function after our callback.
Now inside the callback body, we do a few things - first we're using the array concact method, this simply merges two or more arrays and returns a new array. Also, if we pass it a non array value, it simply adds that to the final array that we return. You can read more about the concat method again on the MDN site.
Then as argument to the concat method, we check the current value curr, if this value is an array or not. If it's an array we make use of recursion and we call the flattenArray on that value Array.isArray(curr) ? flattenArray(curr) .... Now recursion can be a confusing topic, but in a nutshell, what happens is that if it comes across an array the function calls itself again and then this is adding to the call stack. This is repeated for any instances of nested arrays no matter how deep they are. Once the final nested array is reached the execution goes to the next oart of code which is : curr this will add the returned value to the final concat array that is returned.
Each call to the flattenArray function is then resolved starting with final call all the way back up to the first call to it. We then simply return the final merged array from the concat method. This will work with any number of nested arrays, as long as the recursion is so deep that it breaks the JavaScript recursion stack size limit.
OK, so with or flattenArray helper function created we can now go back to our flatten function. The final part of this function is to now handle objects:
function flatten(value) {
...
return flattenObj(value)
}
At this point we can be assured that when the code execution reaches here the value passed in must be an object, as we have covered all of the other types before it. Again for this, we will need to create a helper function flattenObj that will flatten an object. So let's create that function to complete our solution:
function flattenObj(obj) {
if (Object.keys(obj).length === 0) {
return obj
}
...
}
So the first thing we will check for is if the object has any properties. If it doesn't then we simply return the passed in object as it is. If we do have keys, then we want to iterate over each key and then check the type for it:
function flattenObj(obj) {
...
return Object.keys(obj).reduce((acc, cur) => {
const isArray = Array.isArray(obj[cur])
const isObject = typeof obj[cur] === "object"
const isNull = obj[cur] === null
// if value is an array - flatten it with flattenArray_
if(isArray) {
acc[cur] = flattenArray(obj[cur])
//console.log('>>', cur, acc[cur])
}
...
return acc;
}, {})
}
Again we're making use of the array reduce function here, this time we get the keys using the Object.keys() method, this returns an array of all the keys in the object. We then simply call the reduce function on these keys, and as before we can add an initial value. Now this we want to end up with a one level object, that is an object whose property values are all non objects. In other words, we don't have nested objects.
As we did before we have an accumulator acc and the current value curr. I've created some variables that will hold the type of value, this will make it easier for us to check each type as we go along. So the first variable isArray contains a check for an array, this will be a boolean value. So, if this is true we have an array as the value for current property that we are iterating over. Now for this we can simply make use of our flattenArray helper function we created previously.
This will return the flattened array value and we assign that back to the accumulator using the curr key as the property name acc[cur] = flattenArray(obj[cur]). Notice that we are assigning this to the acc, and we initialized this to be an empty object initially.
Right, so this handles any array values that a propery might have. Next we want to check if we have a nested object as the value for a property:
function flattenObj(obj) {
...
return Object.keys(obj).reduce((acc, cur) => {
const isArray = Array.isArray(obj[cur])
const isObject = typeof obj[cur] === "object"
const isNull = obj[cur] === null
...
// if is object
if (isObject && !isNull && !isArray) {
acc = { ...acc, ...flattenObj(obj[cur]) }
}
return acc
}, {})
}
We make use of the helper variables that we created, if we have an object and it's not null, as null check returns 'object', and it's not an array then this means we have an object. We then spread the results of the previous acc value into a new object and assign that to acc. Now since we have a nested object, we need to flatten that also, so again we call the function itself flattenObj(obj[cur]) and pass in the object that we have as the argument. The flattenObj function will eventually return an object and the simply spread that returned value into our new object. This is making use of recursion, so flattenObj is called again each time we come across an nested object. When there are no more nested objects, the calls to the flattenObj function will resolve and we end up with a flattened object.
Again, this relies on you having an understanding of how recursion works, so again please make sure you have a good understanding of how recursion works. With the recursion bit out of the way we can now move onto the the final parts of our flattenObj function:
function flattenObj(obj) {
...
return Object.keys(obj).reduce((acc, cur) => {
const isArray = Array.isArray(obj[cur])
const isObject = typeof obj[cur] === "object"
const isNull = obj[cur] === null
...
if (isNull) {
acc[cur] = obj[cur]
}
if (!isArray && !isObject) {
acc[cur] = obj[cur]
}
return acc
}, {})
}
We check for a null value, if we have a null value we simply assign that to the top level with the curr as the key for it. We then cover the primitive values, so if it's not an object, not an array and is not null then it must be a primitive value. We finally return the acc which will be our flattened object.
Phew! Now if you've got this far, you can pat yourself on the back as this helper function was a bit involved. Again, we can go back to our flatten function and we have now covered all of the requirements that were set out for it:
function flatten(value) {
// check for null
if (value === null) {
return value
}
// test for primitive values
if (typeof value !== "object") {
return value
}
// check for empty array
if (Array.isArray(value) && value.length === 0) {
return value
}
// nested empty arrays are removed
if (Array.isArray(value)) {
return flattenArray(value)
}
return flattenObj(value)
}
function flattenArray(arr) {
return arr.reduce((acc, curr) => {
return acc.concat(Array.isArray(curr) ? flattenArray(curr) : curr)
}, [])
}
function flattenObj(obj) {
if (Object.keys(obj).length === 0) {
return obj
}
return Object.keys(obj).reduce((acc, cur) => {
const isArray = Array.isArray(obj[cur]);
const isObject = typeof obj[cur] === "object";
const isNull = obj[cur] === null;
// if value is an array - flatten it with flattenArray
if (isArray) {
acc[cur] = flattenArray(obj[cur])
}
// if is object
if (isObject && !isNull && !isArray) {
acc = { ...acc, ...flattenObj(obj[cur]) }
}
if (isNull) {
acc[cur] = obj[cur]
}
if (!isArray && !isObject) {
acc[cur] = obj[cur]
}
return acc
}, {})
}
I've added some test data that we can use to test our function meets all of the requirements that we set out earlier. We'll start with testing primitive values.
const result = flatten(1) // 1
const result2 = flatten(true) // true
const result3 = flatten("hello") // hello
const result4 = flatten(null) // null
// empty array
const result5 = flatten([]) // []
// nested empty arrays
const result6 = flatten([1, 2, 3, [], 4]) // [1, 2, 3, 4]
// nested arrays
const result7 = flatten([2, 4, 5, [7, [3, [1]]]]) // [2, 4, 5, 3, 1]
const result7 = flatten({
a: 123,
b: [1, 2, 3],
c: {
d: "123",
e: ["a", "b", ["c", "d"]],
},
}) _// { a: 123, b: [ 1, 2, 3 ], d: '123', e: [ 'a', 'b', 'c', 'd' ] }_
So there you have it, in my opinion a simple solution to a flatten function problem. As I mentioned already there are multiple different ways to solve this problem and this is just one solution of the many possibilities. Although there are multiple ways to solve this problem, one common thing that all solutions will share is the methods used to solve them. For example, to solve this and similar problems you will need to have understanding of:
forEach, reduce, filter etcAs with all interview coding challenges, you will need to make sure that you have a well rounded understanding and that you brush up the parts that you not clear on. I hope this post has shown you one of solving this common coding problem.