← WeRide Interview InsightsSoftware Engineer

WeRide·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Weride software engineer interview with a classic stack problem. Nothing fancy, but they wanted you to be precise about the O(n) complexity and not just hand-wave it.

Questions Asked (1)

Q1

Given a string containing only bracket characters, write a function to determine whether the brackets are all properly matched and closed in the correct order. Expected solution is O(n) time and O(n) space using a stack.

Algorithms & Data Structures
Author's notes

Pretty standard bracket matching problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem: the string contains only bracket characters, and we need to check if they are properly matched and closed in order. Then, describe a stack-based solution: iterate through the string, push opening brackets onto the stack, and for closing brackets, check if the stack is non-empty and the top matches the corresponding opening bracket. Finally, ensure the stack is empty at the end.

Pro tip: Mention edge cases like empty string, odd length, and strings with only closing brackets. Also, discuss the time and space complexity explicitly: O(n) time and O(n) space in the worst case.

1. Clarify the problem

Confirm that the string contains only bracket characters and that we need to check for proper matching and ordering. Ask if there are any constraints on the types of brackets (e.g., (), [], {}).

2. Outline the stack approach

Explain that a stack is ideal because brackets must be closed in the reverse order they are opened. Iterate through the string, pushing opening brackets and popping for closing brackets.

3. Detail the algorithm

For each character: if it's an opening bracket, push it onto the stack. If it's a closing bracket, check if the stack is empty or if the top doesn't match; if so, return false. Otherwise, pop the stack. After iteration, return true only if the stack is empty.

4. Analyze complexity

State that the algorithm runs in O(n) time because each character is processed once, and O(n) space in the worst case (e.g., all opening brackets) due to the stack.

5. Test with examples

Walk through examples like '()[]{}', '([)]', and '{[]}' to demonstrate correctness. Also, mention edge cases like empty string and single bracket.

Key Points to Mention

  • Use a stack to track opening brackets.
  • Map closing brackets to their corresponding opening brackets for easy matching.
  • Check for empty stack when encountering a closing bracket.
  • Ensure the stack is empty after processing all characters.
  • Time complexity: O(n) because each character is processed once.
  • Space complexity: O(n) in the worst case due to stack storage.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.