Uber Interview Questions - Delimiter Matching

Uber Interview Questions - Delimiter Matching We are going to discuss the delimiter matching problem in this weeks post. The question has recently been asked by Uber, however, which is only part of the reason we select this question. One of the common misunderstandings is that coding interviews are extremely hard to companies like Uber, Google, Facebook etc. and most people failed because they couldnt come up with any idea at all. However, its not the case. More than 70% of questions are quite fundamental and are focused on testing candidates understanding of basic data structures/algorithms. Also, writing clean and bug-free code is required. The result is that many people keep saying that questions are much simpler than they thought after the interview, but at the same time fail to solve them. Thats why we select delimiter matching question its fundamental, but if you cant provide a solution with clean code in 15min, youve already failed this interview. Question Delimiter Matching Write an algorithm to determine if all of the delimiters in an expression are matched and closed. For example, “{ac[bb]}”, “[dklf(df(kl))d]{}” and “{[[[]]]}” are matched. But “{3234[fd” and {df][d} are not. The question has been asked by Uber recently and is expected to be solved quickly. Before reading next sections, think about the problem by yourself and track how much time you need to solve it. How to analyze? The focus of all our posts is on how to analyze coding questions and how to come up with the right ideas, which are much more valuable than the solution itself. Back to this question, the first thing should be clarifying the question. For example, I would expect candidates to ask what are all delimiters in this question lets say there are only three (“{}”, “[]” and “()”). You may also clarify if other characters in the string make any difference. Next, its recommended to think about most naive ways to solve the problem, which at least shows that youre able to provide a solution and you can also keep optimizing from this point. Brute force is one of the most common approaches, but as you can see, it doesnt work well in this question because going back to check if any delimiter matches the current one is non-trivial. Simplest case Lets consider the simplest case. If theres only one type of delimiter “()”, how can we solve the problem? The solution is very straightforward. Basically, we keep a counter whose initial value is 0. Go over the string, if we get a left parenthesis “(“, increase the counter by 1 and if its a right parenthesis “)”, decrease the counter by 1. Finally, if the counter is 0, it means the all the parentheses are balanced. Lets generalize the solution for all delimiters. Generalized solution When I was working on this problem for the first time, what I thought first is to keep separate counters for each delimiter and if all of them are 0 after processing the string, all of the delimiters are balanced. However, this doesnt work. Consider the case “([)]”, we have an equal number of left and right delimiters but they are incorrectly matched. Therefore, only keeping the number of unmatched delimiters is not enough, we also need to keep track of all the previous delimiters. Since each time when we see a new delimiter, we need to compare this one with the last unmatched delimiter, stack is the data structure we should consider. Lets finalize the solution as follows: Start with an empty stack to store any delimiter we are processing Go over the string, for each delimiter we find: If its a left parenthesis, push it to the stack If its a right parenthesis, pop the top element of the stack and compare with the right parenthesis. If they are matched, keep processing the string. Otherwise, delimiters are not balanced. Heres the code (in Python): Takeaways The problem is not hard, but its not easy to write clean code within 15min. Again, I would recommend people spend more time on basic questions and be more proficient in writing solid code. You may still have a chance when failing with “super hard” questions, but not being able to write clean code for basic questions like this is much more terrible. Similar to previous questions, let me summarize few takeaways here: If you get stuck, solve the simplest case and try to generalize the solution. For this question, we start with only one type of delimiter, which provides a lot of insights. Instead of guessing which data structure to use, the nature of the solution actually provides a lot of clues. Since we need to compare with the last unmatched delimiter, its quite natural to use a stack. Dont forget to check boundaries. In the coding solution, its important to check if the stack is empty. By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interview with engineers from Google, Facebook etc..