Allocate Unique File Names in an In-Memory Vault
Company: Harvey
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
An in-memory file vault must assign a unique name whenever a file is created. If the requested name already exists, append a parenthesized positive integer to obtain an unused name.
Implement `allocate_names(requests: string[]) -> string[]` and return the assigned name for each request in order.
### Constraints & Assumptions
- All requests target the same namespace, which starts empty. No file is deleted or renamed during the sequence.
- If requested name `s` is unused, assign `s` unchanged.
- Otherwise choose the smallest positive integer `x` for which `s + "(" + decimal(x) + ")"` is unused, then reserve and return that name.
- Names are case-sensitive, nonempty ASCII strings of at most 100 characters. There are at most 10,000 requests.
- Parentheses already present in a requested name are literal text. For example, a collision on `a(1)` tries `a(1)(1)`; do not reinterpret it as a collision on `a`.
- The smallest available positive suffix and flat namespace are explicit practice choices for the reported duplicate-name behavior.
### Examples
```text
requests = ["report", "report", "report", "report(1)"]
result = ["report", "report(1)", "report(2)", "report(1)(1)"]
```
```text
requests = ["a(1)", "a", "a", "A"]
result = ["a(1)", "a", "a(2)", "A"]
```
```hint Remember where each repeated base can resume
Once a suffix candidate is known to be occupied and names are never removed, trying the same candidate again for that base cannot succeed.
```
Overview: Allocate unique vault file names with the smallest available numeric suffix, handling preexisting suffixes, repeated requests, and case sensitivity.
Read the full Harvey Software Engineer interview experience this question came from
An in-memory file vault must assign a unique name whenever a file is created. If the requested name already exists, append a parenthesized positive integer to obtain an unused name.
Implement `allocate_names(requests: string[]) -> string[]` and return the assigned name for each request in order.
### Constraints & Assumptions
- All requests target the same namespace, which starts empty. No file is deleted or renamed during the sequence.
- If requested name `s` is unused, assign `s` unchanged.
- Otherwise choose the smallest positive integer `x` for which `s + "(" + decimal(x) + ")"` is unused, then reserve and return that name.
- Names are case-sensitive, nonempty ASCII strings of at most 100 characters. There are at most 10,000 requests.
- Parentheses already present in a requested name are literal text. For example, a collision on `a(1)` tries `a(1)(1)`; do not reinterpret it as a collision on `a`.
- The smallest available positive suffix and flat namespace are explicit practice choices for the reported duplicate-name behavior.
### Examples
```text
requests = ["report", "report", "report", "report(1)"]
result = ["report", "report(1)", "report(2)", "report(1)(1)"]
```
```text
requests = ["a(1)", "a", "a", "A"]
result = ["a(1)", "a", "a(2)", "A"]
```
```hint Remember where each repeated base can resume
Once a suffix candidate is known to be occupied and names are never removed, trying the same candidate again for that base cannot succeed.
```
Constraints
- At most 10000 requests in a single initially empty namespace.
- Requests are nonempty case-sensitive ASCII strings of at most 100 characters.
- On collision append the smallest available positive decimal integer in parentheses to the entire requested name.
- No deletions or renames occur; existing parentheses remain literal text.
Examples
Input: (['report', 'report', 'report', 'report(1)'],)
Expected Output: ['report', 'report(1)', 'report(2)', 'report(1)(1)']
Explanation: Reserve each result immediately; a requested parenthesized name is a literal new base.
Input: (['a(1)', 'a', 'a', 'A'],)
Expected Output: ['a(1)', 'a', 'a(2)', 'A']
Explanation: A pre-reserved suffix is skipped, while uppercase A remains a separate name.