Find lexicographically smallest string and elimination order

Quick Overview

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.

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.

|Home/Coding & Algorithms/Capital One
Capital One logo
Capital One
Sep 25, 2025, 12:00 AM
hardData ScientistTechnical ScreenCoding & Algorithms
10
0

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).

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...