Two of the Most Famous Coding Interview Questions Explained

The two most favorite coding interview questions of big tech companies simplified in plain English.

Jaival Patel
Towards Data Science
9 min readJul 21, 2021

--

If you are into the IT industry and love to code, you probably know what coding interviews are and how much work it takes to pass an interview successfully, let alone preparing for the interview itself. For the people who don't, there are essentially like giving a test. The interviewer(s) give you a particular problem that you would have to code a solution to. Sometimes, coding interviews are easy, but most of the time, they fall under the range of medium to extremely difficult. Of course, as you go for an interview at more prominent companies like Amazon and Google, the coding interviews are challenging. People spend months before their interviews practicing and learning different methods to tackle different interview questions to have an idea of a solution during the interview. You can almost say it’s like giving an entrance exam or an SAT exam to a university. The more prestigious university you apply to, the more complex the exam, and the more challenging acceptance. Therefore, more preparation needed in advance.

However, what makes an interview coding question so intricate and intriguing at the point where people practice months before their interviews? Aside from practicing to gain confidence about their coding ability, most programmers practice their coding interview questions because during an interview, the interview(s) look for an efficient yet effective solution. When I say efficient, I mean in terms of performance, or in other words, time and space complexity. Time complexity is an expression that summarizes the performance of the program and how long it takes the computer to finish or run the tasks written. Similarly, space complexity sort of works the same; however, it’s an expression that summarizes how much memory it takes to run the task.

If you want to know more about time and space complexities, click on this Data Structures Lecture on Complexity Analysis from the University Of Texas.

Essentially, when you get a problem that requires many “sub-tasks” to create a successful “solution to the main task,” keeping both time and space complexity can be challenging as there are multiple processes to take into consideration. Moreover, companies love when the solutions are clear and concise in terms of the solution's effectiveness. What I mean by that is that the solutions are not over-engineered. Let’s say, for example; we were solving a math problem. Writing unnecessary annotations and paragraphs about why we did each step (such as addition) will make the solution messy and crammed with information, making it hard to understand and read (assuming that our solution was long). The same thing applies to coding as well. Interviewers look for out-of-the-box solutions that can keep the same performance for any given input (of course, there are more factors that interviewers look into, but these are just the basics). Though, just like efficiency, when there are big problems to find a solution to, which include various “sub-tasks” to program, it can be tough to keep the code clean and concise, since naturally, there will be a lot of explaining to do to the interviewers about the solution and the multiple-processes for the solution (which is another factor that interviewees look into, how well can the recipient explain their code). But, that is why programmers constantly practice for months to prepare themselves for interviews. After all, thousands of developers are at big tech companies and start-ups, which means that it isn’t impossible to be successful at coding interviews at any company.

Just like subjects in school and units in math, we can sort problems into different subjects. One of the prevalent subject in coding problems are literally called “popular coding interview questions.” They are called popular coding interview questions because many developers have seen them in big companies. In this article, I will be discussing one of my personal favorite coding interview questions and one of the most popular coding questions regarding trees, and it’s max-width and depth. At first, it sounds intuitively easy to solve, but the reason why this question intrigues many developers (which is why it’s popular) and me is because of its abstract solutions. There are multiple ways to create efficient and effective algorithms, which really test the developer’s ability to think and problem-solve. For example, companies like Google, Amazon, etc., have had these interview questions present before, making it an important problem to know a solution to. When you think about it, it makes sense why this problem is under every developers’ radar; it allows them to shine a light and emphasize their problem-solving ability.

Max-Depth and Width Diagram of a Binary Search Tree | Image by Author

The interview question itself is pretty simple to understand. Given a tree, find the max-width and depth. Although it was straightforward to understand what the problem was asking for conceptually, it took a little bit of time (a couple of minutes compared to seconds) to brainstorm how to code a proper solution. My solution is a little bit wacky, but I got both algorithms to work linear time at the end of the day. What I mean by wacky is that by definition, a breadth-first search algorithm works best when counting nodes laterally, and a depth-first search algorithm works best when trying to count the height of a tree. Thus, you probably have an idea of what algorithm should go with which problem. Typically, the breadth-first search algorithm would work best to find the max-width of the tree, and the depth-first search algorithm would work best to find the max-depth. Both algorithms run linear time in terms of performance, which means that we don’t have to consider other complex algorithms for binary tree traversal. However, for my solution, I did the opposite. To find the max-width of the tree, I used the depth-first search algorithm and for the max-depth, breadth-first traversal. Although my solution may seem opposite from an “accepted general solution,” I did keep both my algorithms at linear time.

BFS and DFS algorithm Visualization | Image by Author

Since I mentioned max-width first, I will be starting off by talking more in-depth about my solution to that very problem and how I used max-depth to my advantage.

Max-Width Solution

To start off, with the depth-first algorithm, I got all the different permutations of each path of each node possible by just traversing the tree by its depth recursively. Then, I added each permutation to a separate array because we will assume that each index of the array represents a certain level. For example, let [a,b,c] be an array of a certain permutation returned by our depth-first search algorithm. We can view each index as a certain level of the tree:

Index to Level visual | Image by Author

We essentially do this because our depth-first search algorithm returns the depth of the traversed path. Hence, if the algorithm traverses each depth all the way to the leaf node, each path must be symmetrical in terms of each index representing each level.

Notice how the indices of both returned arrays are the same | Image by Author

We can also prove this with our second function .width_counter() . With all the permutations formatted into one 2D array, we then split each element in each list based on similar indices. For example, all the elements at index 0 will be placed in the list at index 0, then all the elements at index 1 will be placed in the list at index 1, and so on. This is called partitioning, which is an advanced computer science concept where we split an array or a sequence of values based on a certain condition. After the partitioning process, we will see a returned array with sub-arrays with sorted elements based on indices. We can double-check if our returned array is correct by simply comparing the tree diagram with the elements in our list. If each layer of the tree has the same nodes as each list in that very index (assuming again that indices are levels), we know we have done it correctly as our array is simply just a tree formatted differently.

Notice how each sub-array is similar to each level | Image by Author

The last step in our algorithm to find the max-depth is to compare the lengths of each array in the 2D array, and the largest array (the array with the biggest length) will be the widest level. In this case, since we are comparing each index in the 2D array, we just return the index simply. This still gives the right answer because of the definition we stated earlier about the levels being the same as the indices of each permutated array. In terms of performance overall, we managed to keep the depth-first search algorithm the same at O(n) time, and .width_counter() at O(n^2) due to the nested iterations to create a 2D array.

Moving to our max-depth solution, our method of finding the max-depth is very similar to the first solution of max-width. However, as stated before, instead of using dfs, we used bfs to keep track of our depth. The reason why we used bread-first search in the first place was to count the number of times it went down a layer due to the algorithm’s behavior of moving laterally.

Image by Author

The cool part about this solution is that unlike the first solution for finding the max-width where we compare each level, we don’t compare any array or any path. Instead, we take a traversal approach.

When you look at my solution, there really isn’t anything special about it — it’s just a modified version of the original depth-first search algorithm. Instead of traversing the tree until it meets a specific goal value, it will traverse the tree until its queue is empty. Moreover, to keep an accurate count of the depth, we only add 1 to the counter (which is our variable that keeps the count for our depth) when we approach a parent index. To know if we reach a parent index, we use the basic definition of a binary tree, which states that: each parent must have two child nodes at max. Therefore, during our iteration, we add 1to counter only if we are on the root node during our first iteration(to include the root node in our count) or if the length of the queue after popping its recent value is equivalent to 2. Another more stable way of finding the parent index is to append each node to an array. Using the heap equation to find the parent index, index // 2 , we can keep track of exactly which nodes are parent nodes. Hence, we can iterate the tree once again and add 1to counter every time we meet one of the parent nodes that we found using the equation. This is a great solution; however, compared to our simple solution of just modifying the dfs algorithm, which runs at linear time, the alternate solution would run at quadratic time.

View both of my solutions of Github and their test cases: https://github.com/GEEGABYTE1/Width-Depth-Tree-Problems

Interview questions are one of my favorite tests to take. Although I am only a high school developer and enthusiast who learns and develops solutions for various problems as a passion, interview questions really do improve my overall problem-solving ability. Additionally, the satisfaction you get when finding the right solution is unmatchable. Personally, every time I solve an interview question or a competitive coding problem, I get thrilled! However, some problems like max-depth and max-width are slightly complex, which might take some thinking and problem-solving skills. At first, there won’t be a solution that comes to your mind, but that’s why there are so fun and popular amongst all developers. The reason why it’s so challenging isn’t the fact that it takes great coding skills (which is a big misconception to be successful at solving interview questions); instead, these types of problems are challenging because they are abstract. In other words, there can be multiple solutions, which encourage developers to think even more out of the box! I still am trying to develop a great problem-solving ability along with new computer science concepts. Still, I will continue to write articles about my progress with my goals and new and intriguing interview questions I come across!

--

--

Towards Data Science
Towards Data Science

Published in Towards Data Science

Your home for data science and AI. The world’s leading publication for data science, data analytics, data engineering, machine learning, and artificial intelligence professionals.

Jaival Patel
Jaival Patel

Written by Jaival Patel

16y/o Computer Scientist x Mathematics Enthusiast. I love to share my research and interest in these two topics so you will see a lot of my blogs about my work!

Responses (2)