acoustic-guitar-336479_640

Uber Interview Questions – Delimiter Matching

We are going to discuss the delimiter matching problem in this week’s 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 couldn’t come up with any idea at all. However, it’s 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.

That’s why we select delimiter matching question – it’s fundamental, but if you can’t provide a solution with clean code in 15min, you’ve 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 – let’s say there are only three (“{}”, “[]” and “()”). You may also clarify if other characters in the string make any difference.

Next, it’s recommended to think about most naive ways to solve the problem, which at least shows that you’re 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 doesn’t work well in this question because going back to check if any delimiter matches the current one is non-trivial.

 

Simplest case

Let’s consider the simplest case. If there’s 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 it’s a right parenthesis “)”, decrease the counter by 1. Finally, if the counter is 0, it means the all the parentheses are balanced.

Let’s 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 doesn’t 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.

Let’s 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 it’s a left parenthesis, push it to the stack
    • If it’s 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.

Here’s the code (in Python):

 

Takeaways

The problem is not hard, but it’s 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, it’s quite natural to use a stack.
  • Don’t forget to check boundaries. In the coding solution, it’s 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..

The post is written by Gainlo - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

Share on Facebook5Tweet about this on TwitterShare on LinkedIn1Share on Reddit0

7 thoughts on “Uber Interview Questions – Delimiter Matching

  1. As the stack could have a lot of repeat characters, it may be beneficial to store it as follows.

    Input: [[[[[[[[[[(((((((((())))))))))))))]]]]]]]]]]
    Longer stack: [[[[[[[[[[((((((((((
    Better stack :
    Object( “[” and 10 )
    Object( “(” and 10 )

    Make everything into objects so you only have to pop the stack once without doing wacky calculations. The object holds the character and the number of times it occurred.

    Pop the stack, check its character; if it’s a new opening bracket of the same kind, increment the counter. Decrement the counter for the closing bracket. If the closing bracket brings it to 0, then don’t push the object back to the stack. That way you can handle ([]{}). If the new character is different from the last one, create a new object with the count at 1, and the set the new character accordingly.

    My solution takes a bit more code, so be sure to ask your interviewer if there could be lots of duplicate brackets in a row. That’s the beauty of the trade-off.

  2. This can be easily done using stack. For every open delim insert into stack and when ever u see match close delim pop from stack. At the end of the string stack MUST be empty.

  3. On the email chain there is a type.

    “Finally, if the counter is 9” instead of “Finally, if the counter is 0” in Simple Case.

  4. “if you can’t provide a solution with clean code in 15min, you’ve already failed this interview”

    Why? Can you provide scientific evidence that this criteria is yielding the best engineers for your company?

  5. if the char is Opening brace, add it to the stack.
    else if char is closig brac and our stack is not empty, than the absolute diff between the closing brace and stack.peek() should not be more than 2. If its more than 2 than its not a matching brace.
    if char is something else other than open n closing brace, simply move the pointer to next position.
    CRUX: matching braces dont have the ascii_diff>2

Leave a Reply

Your email address will not be published. Required fields are marked *