Find lexicographically smallest string and elimination order
Company: Capital One
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Hard
Interview Round: Technical Screen
You remember two coding questions from an online assessment.
## Question 1: Return the lexicographically smallest string after a prefix/suffix reverse
You are given a string `s` (length `n`). You may perform **at most one** operation:
1. Choose an integer `k` where `1 <= k <= n`.
2. Either:
- Reverse the **first `k` characters** of `s` (reverse a prefix of length `k`), leaving the rest unchanged, **or**
- Reverse the **last `k` characters** of `s` (reverse a suffix of length `k`), leaving the rest unchanged.
Return the **lexicographically (alphabetically) smallest** string that can be obtained among:
- doing no operation, and
- doing one valid operation as above.
**Output:** the smallest resulting string.
---
## Question 2: Simulate race eliminations using drivers’ history across laps
You are given `laps`, an array of length `n` representing a multi-lap race.
- Each `laps[i]` is an array of pairs `[driverName, lapTime]`.
- `lapTime` is a positive integer.
- A driver may appear in earlier laps and then be eliminated; eliminated drivers no longer appear in subsequent laps.
Maintain each driver’s **history so far** using **cumulative total time across all completed laps**.
After each lap is processed:
1. Update each active driver’s cumulative time by adding their time from this lap.
2. Eliminate the **slowest** active driver, defined as the driver with the **largest cumulative total time so far**.
- If there is a tie, break ties by `driverName` in ascending lexicographic order.
Return the **elimination order** as an array of driver names, from first eliminated to last eliminated.
**Output:** `string[]` elimination order.
**Notes / assumptions to make the task well-defined:**
- Each lap input includes exactly one entry for each currently-active (not-yet-eliminated) driver.
- There is at least 2 drivers at the start.
- Exactly 1 driver is eliminated after each lap until 1 remains (so total eliminations = initialDrivers - 1).
Quick Answer: These problems evaluate string-manipulation and algorithmic-simulation competencies—specifically lexicographic ordering and prefix/suffix transformations for the first problem, and cumulative-time aggregation with elimination and lexicographic tie-breaking for the second.
