Ask LSBot
Back to Open Book Shelf

Stacks and Queues in Interviews

In many technical interviews, Stacks and Queues are rarely asked about directly. Instead, they are often used as intermediary tools to manage data in a way that aligns with the problem's requirements. The main challenge is recognizing when using one of these data structures can help you solve the problem. In most situations, you'll likely be able to use an array as a stack or queue rather than implementing these data structures from scratch. Here are some guidelines to help you determine whether to use a stack or a queue.

When to use a Stack

  • Reversal Properties: If the problem involves reversing elements, such as in string reversal or undo operations in text editors.
  • Balancing Symbols: Problems that require checking the balance of certain characters, like matching parenthesis, often benefit from a stack.
  • Depth-First Search (DFS): We'll explore DFS in upcoming lessons when discussing Binary Trees. For now, be aware that stacks can be used to perform a depth-first search through tree or graph data structures.

Note that if a problem requires a stack, another approach could be using recursion, which uses a call stack to keep track of function calls. We'll learn about recursion in the next lesson.

When to use a Queue

  • Order Maintenance: When the problem requires maintaining elements in their original order, such as in task scheduling or managing print jobs, a queue is usually suitable.
  • Breadth-First Search (BFS): As with DFS, we'll explore BFS in the upcoming lesson on Binary Trees. You'll learn what BFS is and how queues can help us implement it.
  • Buffering or Pipeline If the scenario requires a buffer of elements to be processed in the order they arrive, like in streaming data or load balancing, a queue offers the necessary structure.

By understanding these guidelines, you'll be better equipped to recognize when stacks or queues can be valuable tools in solving interview problems.

Practice: Matching Brackets

In this exercise, you will apply what we've learned so far in this lesson to solve the "Matching Brackets" problem. First, identify which data structure could help you solve this problem. Feel free to use an array either as a stack or a queue, depending on what you find most suitable.

Make sure to apply the PEDAC process. In this challenge, it's important to understand the problem well and break down the logical rules of matching brackets to be able to apply these rules to a solution.

Problem Description

// Write a function `areMatched` that takes a string as an argument
// and returns true if all types of brackets (parentheses (),
// square brackets [], and curly braces {}) in the string are
// properly matched. For the brackets to be considered
// matched, every opening bracket must have a corresponding
// closing bracket of the same type, and the brackets must be
// correctly nested.

console.log(areMatched("()"));              // Output: true
console.log(areMatched("([()]{})"));        // Output: true
console.log(areMatched("([((}]({}))"));     // Output: false
console.log(areMatched("{{[[(())]]}}"));    // Output: true
console.log(areMatched(""));                // Output: true
console.log(areMatched("([)]"));            // Output: false

Exercises

  1. Determine whether to use a stack or a queue, and write an algorithm for the "Matching Brackets" problem.

    You can use a Stack data structure to solve this problem.

    View Our Solution

    For this problem, we'll maintain a stack as we iterate through the characters of the input string.

    There are two distinct cases to consider based on the character type:

    1. Open Bracket: When the character is an open bracket ((, [, {), we push it onto the stack.
    2. Closed Bracket: When the character is a closed bracket (), ], }):
      • We attempt to pop the last character from the stack.
        • If the stack is empty, indicating there is no matching open bracket, we return false immediately.
        • If the current character and the popped character aren't a match return false.
        • If we've not returned false, we can continue iterating.

    At the end of the process, if the stack is empty, all brackets are properly matched, and we can return true. Otherwise, if any brackets remain unmatched in the stack, we return false.

    Walkthrough

    Let's do a detailed walkthrough using a string "([()]{})".

    Step 1: The first character is an open bracket, so we push it to the stack.

    Step 2: Once again, the character is an open bracket, so we push it to the stack.

    Step 3: In the third step we encounter an open bracket yet again.

    Step 4: In the fourth step, the character is a closed bracket so we pop the last character from the stack and check if it matches the current character. Since the characters match, we continue.

    Step 5: Once again, the character is a closed bracket so we pop the last character from the stack and check if it matches the current character. Since the characters match, we continue.

    Step 6: The character is an open bracket, so we push it to the stack.

    Step 7: The character is a closed bracket so we pop the last character from the stack and check if it matches the current character. Since the characters match, we continue.

    Step 8: Finally, the last character is a closed bracket so we pop the last character from the stack and check if it matches the current character. The characters match, so we continue.

    Step 9: We've reached the end of the string. We now check to see if the stack is empty. Since it is, we return true.

    In the walkthrough, we've seen an example where all brackets matched correctly and the stack was empty at the end. Now, let's visually explore cases where this might not be true, and we'd have to return false instead.

    Case 1: We have reached the end of the string, but the stack is not empty.

    In this example, we would push the open bracket to the stack and successfully completed our iterations. At the end, however, our stack is not empty and we return false.

    Case 2: We've encountered a closing bracket while the stack is empty.

    Here, we encounter a closing bracket. That means we want to pop from the stack to compare with our closing bracket. In this case, the stack is empty, meaning we have a closing bracket with no matching opening bracket and we return false.

    In the above example, we try to pop from an empty stack on the first iteration, but this isn't necessarily always the case. Consider what happens with the string '{()}]'.

    Case 3: We've encountered a closing bracket that doesn't match the last character in the stack.

    In our first step, we would push our first opening bracket onto the stack.

    In the second step, we encounter a closing bracket. We successfully pop from the stack to get a character to compare against our bracket. When we make the comparison, however, they are not compatible brackets and we return false.

  2. Use your algorithm to implement a solution for the "Matching Brackets" problem.

    View Our Solution

    In our implementation we'll use an array as a stack.

    function areMatched(string) {
  const stack = [];
  const matches = {
    '(': ')',
    '[': ']',
    '{': '}',
  };

  for (let char of string) {
    if (['(', '[', '{'].includes(char)) {
      stack.push(char);
    } else if ([')', ']', '}'].includes(char)) {
      if (stack.length === 0 || matches[stack.pop()] !== char) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

console.log(areMatched("()"));              // Output: true
console.log(areMatched("([()]{})"));        // Output: true
console.log(areMatched("([((}]({}))"));     // Output: false
console.log(areMatched("{{[[(())]]}}"));    // Output: true
console.log(areMatched(""));                // Output: true
console.log(areMatched("([)]"));            // Output: false

Ask LSBot about: Stacks and Queues in Interviews

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you understand this chapter content with fast, focused answers.

Ask me about concepts, examples, or anything you'd like clarified from this chapter. I can explain complex topics, provide examples, or help connect ideas.

Want to know more? Refer to the LSBot User Guide.

Stacks and Queues in Interviews - Exercise

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you think through this exercise by providing hints and guidance, without giving away the solution.

You can ask me about your approach, request clarification on the problem, or seek help when you feel stuck.

Want to know more? Refer to the LSBot User Guide.