Simulate a Deterministic Finite Automaton
Company: Point72
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
Implement a deterministic finite automaton simulator for the alphabet `{a, b}`.
The automaton has states numbered from `0` through `stateCount - 1`. The transition table has one row per state:
```text
transitions[state][0] = next state after reading 'a'
transitions[state][1] = next state after reading 'b'
```
Given the start state, the set of accepting states, and an input string containing only `a` and `b`, process the string from left to right. Return `true` exactly when the state reached after the entire string is accepting. The empty string leaves the automaton in its start state.
## Constraints
- `1 <= stateCount <= 200,000`
- `0 <= startState < stateCount`
- Every transition target is a valid state.
- Accepting-state indices are unique.
- `0 <= input.length <= 200,000`
- `input` contains only lowercase `a` and `b`.
- Expected time is `O(input.length)` with `O(1)` auxiliary simulation space beyond the supplied automaton.
## Example
```text
stateCount = 3
startState = 0
acceptingStates = [2]
transitions = [
[1, 0],
[1, 2],
[2, 2]
]
input = "aab"
```
The visited states are `0 -> 1 -> 1 -> 2`, so the function returns `true`.
Quick Answer: Implement a deterministic finite automaton simulator for strings over a and b, including empty input and explicit accepting states. Demonstrate careful transition-table traversal, start-state handling, acceptance after complete input, and linear-time complexity.
Implement a deterministic finite automaton (DFA) simulator for the alphabet `{a, b}`.
The automaton has `stateCount` states numbered `0` through `stateCount - 1`. The transition table `transitions` has exactly one row per state, and each row has exactly two entries:
```text
transitions[state][0] = next state after reading 'a'
transitions[state][1] = next state after reading 'b'
```
Given `startState`, the list `acceptingStates` of accepting state indices, and `inputString` containing only the characters `a` and `b`, process `inputString` from left to right, following one transition per character. Return `true` exactly when the state reached **after the entire string has been consumed** is an accepting state, and `false` otherwise.
Only the final state matters. Passing through an accepting state partway does not make the string accepted, and passing through a non-accepting state does not make it rejected. The empty string consumes no transitions and leaves the automaton in `startState`.
`acceptingStates` may be given in any order and may be empty; an empty accepting set rejects every string.
## Output
Return a single boolean: `true` if the final state is accepting, otherwise `false`.
## Example 1
```text
stateCount = 3
startState = 0
acceptingStates = [2]
transitions = [
[1, 0],
[1, 2],
[2, 2]
]
inputString = "aab"
```
The visited states are `0 -> 1 -> 1 -> 2`. The final state `2` is accepting, so the answer is `true`.
## Example 2
```text
stateCount = 4
startState = 0
acceptingStates = [1, 2]
transitions = [
[1, 3],
[2, 3],
[1, 3],
[3, 3]
]
inputString = "aabb"
```
The visited states are `0 -> 1 -> 2 -> 3 -> 3`. The walk passes through the accepting states `1` and `2`, but state `3` absorbs every remaining symbol, so the final state is `3` and the answer is `false`.
Constraints
- 1 <= stateCount <= 200,000
- 0 <= startState < stateCount
- len(transitions) == stateCount, and every row has exactly 2 entries
- Every transition target is a valid state, i.e. 0 <= transitions[state][k] < stateCount
- Accepting-state indices are unique, and 0 <= acceptingStates[i] < stateCount
- 0 <= len(acceptingStates) <= stateCount
- 0 <= len(inputString) <= 200,000
- inputString contains only the lowercase characters 'a' and 'b'
- Expected time is O(len(inputString)) with O(1) auxiliary simulation space beyond the supplied automaton
Examples
Input: (3, 0, [2], [[1, 0], [1, 2], [2, 2]], 'aab')
Expected Output: True
Input: (3, 2, [2], [[1, 0], [1, 2], [2, 2]], '')
Expected Output: True
Hints
- Only one value changes as you scan the string. Ask yourself what the smallest piece of information is that you must carry from one character to the next.
- The two columns of a transition row are not interchangeable: column 0 is the target for 'a' and column 1 is the target for 'b'. Map each character to its column before indexing.
- The acceptance test happens exactly once, after the loop. Deciding membership in acceptingStates by scanning the list on every character would turn an O(n) walk into O(n * k); pre-build a lookup instead.