Validate a Balanced INDENT and DEDENT Token Stream
Company: Figma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Validate a Balanced INDENT and DEDENT Token Stream
### Problem
A tokenizer has already converted a document into a sequence of tokens. Two token values have structural meaning:
- `INDENT` opens one indentation level.
- `DEDENT` closes one indentation level.
All other token values are content and do not change indentation depth.
Implement `is_well_formed(tokens)` to return whether every `INDENT` has a corresponding later `DEDENT`, with no prefix of the stream containing more `DEDENT` tokens than `INDENT` tokens.
### Examples
```text
tokens = ["text", "INDENT", "text", "DEDENT"]
result = true
```
```text
tokens = ["DEDENT", "text"]
result = false
```
```text
tokens = ["INDENT", "INDENT", "DEDENT"]
result = false
```
### Requirements
- Treat an empty token sequence as well formed.
- Reject immediately if a `DEDENT` would make the current depth negative.
- After the final token, accept only if the depth is zero.
- Use one pass and constant auxiliary space.
```hint Test the shortest failures
Compare a stream that begins with `DEDENT` with one that ends after an unmatched `INDENT`; they fail for different reasons.
```
### Discussion Prompts
1. Why is counting total `INDENT` and `DEDENT` tokens insufficient?
2. Which malformed input can be rejected before the scan finishes?
3. What are the time and auxiliary-space complexities?
Quick Answer: Validate whether an INDENT and DEDENT token stream remains balanced at every prefix and closes all open levels at the end. This compact problem tests one-pass state tracking, early rejection, empty-input behavior, and the difference between global counts and structural ordering.
A tokenizer has already converted a document into a flat sequence of tokens. Exactly two token values carry structural meaning:
- `"INDENT"` opens one indentation level.
- `"DEDENT"` closes one indentation level.
Every other token value is **content** and does not change the indentation depth.
Given the token sequence `tokens`, implement `is_well_formed(tokens)` returning a boolean: `true` when the stream is well formed, `false` otherwise.
A stream is well formed when **both** hold:
1. No prefix of the stream contains more `DEDENT` tokens than `INDENT` tokens. Equivalently, scanning left to right, a `DEDENT` that would drive the current depth below zero makes the stream ill formed immediately.
2. After the final token the depth is exactly zero, so every `INDENT` was closed by a later `DEDENT`.
An empty token sequence is well formed.
### Matching rules
Structural matching is on the **exact, case-sensitive** strings `"INDENT"` and `"DEDENT"`. Anything else -- including `"indent"`, `"Indent"`, `"INDENTS"`, or `" INDENT"` with surrounding whitespace -- is ordinary content and leaves the depth unchanged.
### Output semantics
Return a genuine boolean (`True`/`False` in Python, `true`/`false` in JavaScript, `boolean` in Java, `bool` in C++). Do not return `0`/`1` or a string. There is exactly one correct answer per input, so no ordering or tie-breaking rule is needed.
### Examples
**Example 1**
```text
Input: tokens = ["text", "INDENT", "text", "DEDENT"]
Output: true
```
The depth goes 0 -> 0 -> 1 -> 1 -> 0. It never goes negative and ends at zero.
**Example 2**
```text
Input: tokens = ["DEDENT", "text"]
Output: false
```
The very first token would drive the depth to -1, closing a level that was never opened, so the stream is rejected before the scan finishes.
**Example 3**
```text
Input: tokens = ["INDENT", "INDENT", "DEDENT"]
Output: false
```
The depth never goes negative, but it ends at 1: the first `INDENT` is never closed.
**Example 4**
```text
Input: tokens = ["DEDENT", "INDENT"]
Output: false
```
The counts of `INDENT` and `DEDENT` are equal, yet the stream is still ill formed. Counting alone is not enough -- order matters.
### Constraints
- `0 <= len(tokens) <= 10^5`
- `1 <= len(tokens[i]) <= 32`
- Each `tokens[i]` is a string of printable ASCII characters
- Only the exact strings `"INDENT"` and `"DEDENT"` are structural; matching is case-sensitive
- The return value is a boolean; no numeric value crosses the function boundary
- Aim for one pass over the tokens and O(1) auxiliary space
Constraints
- 0 <= len(tokens) <= 10^5
- 1 <= len(tokens[i]) <= 32
- Each tokens[i] is a string of printable ASCII characters
- Only the exact strings "INDENT" and "DEDENT" are structural; matching is case-sensitive
- Every other token value is content and leaves the indentation depth unchanged
- The return value is a boolean; no numeric value crosses the function boundary
- Target complexity: one pass over the tokens and O(1) auxiliary space
Examples
Input: ([],)
Expected Output: True
Input: (['INDENT'],)
Expected Output: False
Hints
- The two failure modes are not the same failure. One can be detected in the middle of the scan; the other can only be detected once you have run out of tokens.
- Consider ["DEDENT", "INDENT"]: the totals match perfectly, yet the stream is ill formed. What does that tell you about a solution that only tallies counts?
- You only ever need to remember one number while scanning, and it should never be allowed to go negative.