Sum palindrome-change costs over all substrings
Company: Intuit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
This is a three-part coding screen. Each part is independent — a string-algorithms problem, a SQL aggregation problem, and a shell-parsing problem — and is graded separately. Treat them as three short whiteboard problems in one session.
### Constraints & Assumptions
- **Part 1 (algorithms):** `dna` may be up to a few thousand characters; the running answer can exceed the signed 32-bit range, so a 64-bit accumulator is required. Alphabet is exactly `{A, C, G, T}`.
- **Part 2 (SQL):** Standard SQL on a single `transactions` table; assume an engine with window functions and a string-aggregation function (the prompt uses Oracle-style `LISTAGG`, but `STRING_AGG` / `GROUP_CONCAT` are acceptable analogues if you state the dialect).
- **Part 3 (Bash):** Input is a single multi-line string formatted like `ls -l` output. Filenames may contain spaces. You may use standard POSIX shell utilities (`awk`, `sort`, `cut`, etc.).
### Clarifying Questions to Ask
- **Part 1:** What is the maximum length of `dna`? Does this drive whether an $O(n^2)$ solution is acceptable or a linear-time solution is expected? Is the alphabet guaranteed to be exactly `ACGT`, or should the solution be alphabet-agnostic?
- **Part 2:** Which SQL dialect (Oracle / Postgres / MySQL / Snowflake)? How exactly should raw `reason` strings be normalized (case, trimming, mapping synonyms)? When two reasons tie on frequency, what is the tiebreak ordering? Should the `failure_reasons` list be capped (top-N) or include every reason?
- **Part 3:** Is the input guaranteed to be well-formed `ls -l` (a leading `total` line, fixed leading columns)? "Largest" by what metric — byte size from the size column, or longest filename? How should ties be broken? Can a filename contain a newline?
---
### Part 1 — Sum of palindrome-modification costs over all substrings (Coding)
You are given a DNA string `dna` consisting only of characters `A`, `C`, `G`, `T`.
For any substring `dna[l..r]`, define its **palindrome modification cost** as the minimum number of single-character substitutions required to make that substring a palindrome. Equivalently, it is the number of mismatched mirror pairs: the count of offsets `t` with `t < (r-l+1)/2` for which `dna[l+t] != dna[r-t]`.
Compute the **sum of palindrome modification costs over all substrings** of `dna`, and return the result as a 64-bit integer.
- **Input:** a single string `dna`.
- **Output:** a single integer — the sum of costs across all substrings.
```hint Reframe the sum
Don't iterate substrings and re-scan each one ($O(n^3)$). Swap the order of summation: ask how much a single mismatched character **pair** `(i, j)` contributes across *all* substrings in which `i` and `j` are mirror images.
```
```hint The mirror condition
Inside `dna[l..r]`, position `l+t` mirrors `r-t`, so `i` and `j` mirror exactly when `l + r = i + j` — i.e. they are equidistant from the two ends. Count how many in-bounds symmetric expansions `l = i-t`, `r = j+t` exist.
```
```hint Closing the form
A fixed mismatched pair `(i, j)` contributes a weight of $\min(i,\,n-1-j)+1$. Summing that weight over all pairs with `dna[i] != dna[j]` gives an $O(n^2)$ solution; with a 4-letter alphabet and per-character prefix sums you can push it to $O(n)$.
```
#### What This Part Should Cover
- Recognizing that the naive triple loop is too slow and reframing the count by character pairs rather than by substrings.
- Correctly deriving and justifying the per-pair weight (the mirror/equidistance condition and the in-bounds expansion count, including the `+1`).
- Choosing a 64-bit accumulator and explaining *why* (the answer grows like $n^3$ and overflows 32-bit for $n$ a few thousand).
- Optionally, an alphabet-aware linear-time refinement and a clean correctness/complexity statement.
---
### Part 2 — Per-status transaction summary with aggregated failure reasons (SQL)
You are given a `transactions` table with at least: a transaction identifier, an `amount`, a `status` (e.g. `SUCCESS` / `FAILED`), and a free-text `reason` describing why a transaction failed (raw, inconsistently formatted).
Write a query that returns exactly one row per `status` with the columns:
| `status` | `total_transactions` | `total_amount` | `failure_reasons` |
where `total_transactions` is the count of transactions in that status, `total_amount` is the sum of their `amount`, and `failure_reasons` is a single delimited string of the **distinct normalized reasons** for that status, ordered by how frequently each reason occurs (most frequent first).
```hint Pipeline shape
Build it in stages with CTEs: (1) normalize the raw `reason` (trim, fold case, collapse whitespace) so spelling variants collapse to one value; (2) group by `status` + normalized reason to get per-reason frequencies; (3) rank reasons within each status with a window function (`ROW_NUMBER`/`RANK` over `PARTITION BY status ORDER BY count DESC`); (4) collapse each status to one row with an ordered string aggregation (`LISTAGG` / `STRING_AGG`) and the count/sum aggregates.
```
#### What This Part Should Cover
- Reason normalization so semantically identical reasons are not double-counted.
- Correct two-level aggregation: per-status totals (count, sum) plus a frequency-ranked, distinct list of reasons collapsed into one cell.
- Using window functions to impose the frequency ordering, and an ordered string-aggregation (`LISTAGG ... WITHIN GROUP` / `STRING_AGG(... ORDER BY ...)`) so the final result is exactly one row per status.
- Handling the SUCCESS status (which has no failure reasons) cleanly — `NULL`/empty list rather than a wrong row count.
---
### Part 3 — Find the largest file from `ls -l` output (Bash)
You are given a single multi-line string that looks like the output of `ls -l` (a leading `total N` line followed by one line per entry, each with permissions, link count, owner, group, **size in bytes**, a date/time, and finally the **filename**). Filenames may contain spaces.
Write a shell command or short script that prints the **name of the largest file** (by the byte-size column). The core difficulty is parsing the fixed `ls -l` column layout correctly while keeping filenames that contain spaces intact.
```hint Don't split the name on spaces
The first columns are fixed-width-ish fields; the filename is "everything from column 9 onward." Field-splitting on whitespace will chop a spaced filename. Sort numerically on the size field (column 5) and then reconstruct the filename from the remaining fields, or use `cut`/`awk` with an explicit field offset so the trailing name is preserved verbatim.
```
#### What This Part Should Cover
- Skipping the leading `total` line and any non-entry lines.
- Selecting the max by the numeric **size** column (column 5), using a numeric (not lexicographic) comparison.
- Reconstructing a filename that may contain spaces without truncating it at the first space.
- A sensible tie-break and graceful behavior on empty/malformed input.
---
### What a Strong Answer Covers
Across all three parts, a strong candidate demonstrates the same instincts in three different domains:
- **Right complexity for the input size.** Part 1: replacing the $O(n^3)$ simulation with an $O(n^2)$ (or $O(n)$) reformulation and justifying it. Part 2: a query that scans the table a small constant number of times rather than correlated subqueries. Part 3: a single pass / sort rather than fragile manual parsing.
- **Correctness under messy data.** Overflow awareness (Part 1), reason normalization and the empty-failure-list case (Part 2), and spaces-in-filenames plus the `total` header line (Part 3) — each part has one "gotcha" that separates a working answer from a brittle one.
- **Clear statement of assumptions.** Stating the SQL dialect, the tiebreak rules, and the size metric, rather than silently picking one.
### Follow-up Questions
- **Part 1:** Walk through the $O(n)$ refinement: how do per-character prefix sums let you sum the piecewise weight $\min(i, n-1-j)+1$ over all left indices for a fixed `j`? What changes if the alphabet is large instead of 4 letters?
- **Part 2:** How would you cap `failure_reasons` to the top 3 per status, and how does your query change if `reason` can be `NULL`? How would you make the normalization robust to typos (e.g. fuzzy grouping)?
- **Part 3:** How does your command behave if a filename contains a literal newline or tab? How would you instead solve this without parsing `ls -l` at all (e.g. operating on the real filesystem)?
Quick Answer: This question evaluates understanding of string algorithms, combinatorial counting, and algorithmic optimization for aggregating pairwise mismatch costs across all substrings.
Solution
This screen has three independent parts. Each is solved separately below.
---
## Part 1 — Sum of palindrome-modification costs over all substrings
### Reframe: count by pairs, not by substrings
The naive reading iterates every substring and walks both ends. There are $O(n^2)$ substrings, each costing up to $O(n)$ to score, so direct simulation is $O(n^3)$ — too slow for $n$ in the thousands.
The key move is to **stop summing over substrings and sum over character pairs.** A single mismatched pair $(dna[i], dna[j])$ with $i<j$ contributes $1$ to the cost of *every* substring in which positions $i$ and $j$ are mirror images. So:
$$\text{answer} = \sum_{\substack{0 \le i < j \le n-1 \\ dna[i] \ne dna[j]}} \big(\text{number of substrings where } i \text{ and } j \text{ are a mirror pair}\big).$$
### When are $i$ and $j$ a mirror pair?
Inside `dna[l..r]`, offset `l+t` mirrors `r-t`. So $i$ and $j$ mirror exactly when they are equidistant from the two ends:
$$i - l = r - j \iff l + r = i + j.$$
Fix the pair $(i,j)$. Every substring in which they mirror is a **symmetric expansion** outward: `l = i - t`, `r = j + t` for $t \ge 0$, subject to staying in bounds:
- `l >= 0` requires `t <= i`,
- `r <= n-1` requires `t <= n-1-j`.
So $t$ ranges over $0 \dots \min(i,\,n-1-j)$, giving exactly
$$\text{weight}(i, j) = \min(i,\; n-1-j) + 1$$
substrings (distinct $t$ ↔ distinct substring, no overcounting). The $+1$ accounts for the tight substring `dna[i..j]` itself ($t=0$). This collapses the problem to a double loop over pairs:
$$\boxed{\;\text{answer} = \sum_{0 \le i < j \le n-1} [\,dna[i] \ne dna[j]\,]\cdot\big(\min(i,\,n-1-j)+1\big)\;}$$
### Reference solution — $O(n^2)$ time, $O(1)$ space
This is the version to write on the whiteboard: short, obviously correct, fast enough for $n$ up to a few thousand.
```python
def sum_palindrome_costs(dna: str) -> int:
n = len(dna)
total = 0
for i in range(n):
for j in range(i + 1, n):
if dna[i] != dna[j]:
total += min(i, n - 1 - j) + 1
return total
```
```java
public static long sumPalindromeCosts(String dna) {
int n = dna.length();
long total = 0; // 64-bit accumulator — required
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (dna.charAt(i) != dna.charAt(j)) {
total += Math.min(i, n - 1 - j) + 1;
}
}
}
return total;
}
```
- **Time:** $O(n^2)$ — one pass over all $\binom{n}{2}$ pairs, $O(1)$ each.
- **Space:** $O(1)$.
### Optional refinement — $O(n\cdot\sigma)$ time with $\sigma=4$
Because the alphabet is tiny (`A`,`C`,`G`,`T`), we can compute the same sum in $O(n\cdot\sigma)$ time. Fix the right index `j` and let `m = n-1-j`. For each `i < j` the weight splits at the threshold `m`:
$$\min(i, m) + 1 = \begin{cases} i + 1 & \text{if } i \le m, \\ m + 1 & \text{if } i > m. \end{cases}$$
For a fixed `j` we sum this over all `i < j` whose character **differs** from `dna[j]`, using "differs = all − equal." Maintain per-character prefix tables over `i`:
- `cnt[p][c]` — count of positions in `[0, p-1]` holding char `c`;
- `wsum[p][c]` — sum of `(pos+1)` over positions in `[0, p-1]` holding char `c`.
Split `i ∈ [0, j-1]` at `thr = min(m, j-1)`: the left part (`i ≤ thr`) contributes weight `i+1` (use `wsum`), the right part (`thr < i < j`) contributes the constant `m+1` (use `cnt`); in both subtract the equal-character term.
```python
def sum_palindrome_costs_linear(dna: str) -> int:
n = len(dna)
if n < 2:
return 0
idx = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
cnt = [[0] * 4 for _ in range(n + 1)] # cnt[p][c] = #char c in [0,p-1]
wsum = [[0] * 4 for _ in range(n + 1)] # wsum[p][c] = sum(pos+1) for char c
for p in range(n):
for c in range(4):
cnt[p + 1][c] = cnt[p][c]
wsum[p + 1][c] = wsum[p][c]
c = idx[dna[p]]
cnt[p + 1][c] += 1
wsum[p + 1][c] += (p + 1)
total = 0
for j in range(n):
m = n - 1 - j
cj = idx[dna[j]]
thr = min(m, j - 1) # last i that uses weight (i+1)
if thr >= 0: # left part: weight (i+1)
p = thr + 1
all_w = sum(wsum[p][c] for c in range(4))
total += all_w - wsum[p][cj]
a, b = thr + 1, j - 1 # right part: constant weight (m+1)
if a <= b:
all_c = sum(cnt[b + 1][c] - cnt[a][c] for c in range(4))
eq_c = cnt[b + 1][cj] - cnt[a][cj]
total += (m + 1) * (all_c - eq_c)
return total
```
- **Time:** $O(n\cdot\sigma)$; with $\sigma=4$ this is $O(n)$.
- **Space:** $O(n\cdot\sigma)$ for the prefix tables (also $O(n)$ for fixed $\sigma$; can be rolled to $O(\sigma)$).
Both implementations agree with the brute-force $O(n^3)$ simulation on thousands of random strings.
### Overflow — the headline trap
The total counts (substring, mirror-pair) incidences, so it grows on the order of $n^3$ (bounded by roughly $n^3/6$). For strings a few thousand characters long a worst-case pattern (e.g. repeating `ACGT`) crosses $2^{31}-1$ around $n \approx 3.6\text{k}$. **Use a 64-bit accumulator** (`long` in Java/C++; Python ints are arbitrary precision). `int` is not safe.
### Worked examples
| `dna` | answer | why |
|-------|--------|-----|
| `"A"` | `0` | single char, no pairs |
| `"AC"` | `1` | only `"AC"` has a pair: one mismatch |
| `"ACA"` | `2` | `"AC"`→1, `"CA"`→1, `"ACA"`→0 (already a palindrome) |
| `"AAAA"` | `0` | all equal, never a mismatch |
| `"ACGT"` | `7` | all six pairs mismatch |
| `"ACGTACGT"` | `44` | larger sanity check |
Hand-check of `"ACGT"` ($n=4$, all six pairs mismatch): $\min(0,2){+}1{+}\min(0,1){+}1{+}\min(0,0){+}1{+}\min(1,1){+}1{+}\min(1,0){+}1{+}\min(2,0){+}1 = 1{+}1{+}1{+}2{+}1{+}1 = 7$. ✓
### Edge cases & pitfalls
- **Length 0 or 1:** no pairs ⇒ answer `0`; the loops produce it naturally.
- **Off-by-one:** dropping the `+1` undercounts the tight substring `dna[i..j]` for every pair.
- **Mirror, not adjacency:** the pair must satisfy `l + r = i + j`; only comparing adjacent/fixed-distance characters is wrong. The `min(i, n-1-j)` weight encodes this.
- **Alphabet generality:** the $O(n^2)$ version works for any alphabet; only the linear refinement needs a small known alphabet.
---
## Part 2 — Per-status summary with frequency-ranked failure reasons (SQL)
**Goal:** one row per `status` with `total_transactions`, `total_amount`, and a single delimited string of distinct **normalized** failure reasons ordered most-frequent-first.
### Why the staged approach
Two aggregations are interleaved: per-*status* totals (count, sum over all rows) and a per-*reason* frequency that must then be flattened back to the status grain in a specific order. Doing it in one `GROUP BY` is impossible because the grains differ, so build it with CTEs.
```sql
WITH normalized AS ( -- 1. collapse spelling variants
SELECT
t.status,
t.amount,
CASE
WHEN t.reason IS NULL THEN NULL
ELSE UPPER(TRIM(REGEXP_REPLACE(t.reason, '\s+', ' ')))
END AS reason_norm
FROM transactions t
),
per_reason AS ( -- 2. frequency of each reason within a status
SELECT status, reason_norm, COUNT(*) AS reason_cnt
FROM normalized
WHERE reason_norm IS NOT NULL
GROUP BY status, reason_norm
),
status_totals AS ( -- 3. totals at the status grain (all rows)
SELECT status,
COUNT(*) AS total_transactions,
SUM(amount) AS total_amount
FROM normalized
GROUP BY status
),
reasons_agg AS ( -- 4. flatten reasons to one string, freq-ordered
SELECT status,
LISTAGG(reason_norm, ', ')
WITHIN GROUP (ORDER BY reason_cnt DESC, reason_norm) AS failure_reasons
FROM per_reason
GROUP BY status
)
SELECT s.status,
s.total_transactions,
s.total_amount,
r.failure_reasons -- NULL for statuses with no failures
FROM status_totals s
LEFT JOIN reasons_agg r ON r.status = s.status
ORDER BY s.status;
```
### Notes on the query
- **Normalization (CTE 1):** `TRIM` + collapse internal whitespace + `UPPER` so `"Insufficient Funds"`, `"insufficient funds "` etc. fold to one value. State this rule explicitly to the interviewer; if synonyms must merge (e.g. `"NSF"` ↔ `"INSUFFICIENT FUNDS"`) add a mapping table.
- **Two grains kept separate:** `status_totals` is computed over *all* rows (so `total_transactions`/`total_amount` include successes and rows with no reason), while `per_reason` filters to non-null reasons. The final `LEFT JOIN` keeps every status even when it has no failure reasons (SUCCESS → `failure_reasons` is `NULL`).
- **Ordering inside the aggregate:** `LISTAGG(... ) WITHIN GROUP (ORDER BY reason_cnt DESC, reason_norm)` imposes most-frequent-first with a deterministic tiebreak by name.
- **Dialect portability:** Oracle/Snowflake use `LISTAGG ... WITHIN GROUP`. Postgres: `STRING_AGG(reason_norm, ', ' ORDER BY reason_cnt DESC, reason_norm)`. MySQL: `GROUP_CONCAT(reason_norm ORDER BY reason_cnt DESC SEPARATOR ', ')` (and `REGEXP_REPLACE` requires MySQL 8+). The CTE structure is identical; only the aggregate function name changes.
- **If you must avoid a window function:** none is strictly required above — the ordering is pushed into the `LISTAGG`/`STRING_AGG`. If instead you want an explicit per-status rank (e.g. to cap top-N), add `ROW_NUMBER() OVER (PARTITION BY status ORDER BY reason_cnt DESC)` in a CTE between steps 2 and 4 and filter `rn <= 3` before aggregating.
### Sample shape
| status | total_transactions | total_amount | failure_reasons |
|--------|-------------------:|-------------:|-----------------|
| FAILED | 120 | 5400.00 | `INSUFFICIENT FUNDS, CARD DECLINED, TIMEOUT` |
| SUCCESS | 880 | 91250.00 | `NULL` |
---
## Part 3 — Largest file from `ls -l` output (Bash)
**Goal:** given a multi-line string formatted like `ls -l`, print the **filename of the largest entry by byte size** — and keep filenames that contain spaces intact.
### The two traps
1. A leading `total N` line (and any blank/non-entry lines) must be skipped.
2. The filename is "column 9 onward." Naive whitespace splitting truncates a filename like `my big file.dat` at the first space, and lexicographic sorting picks the wrong "largest." Sort **numerically** on the **size** column (column 5) and reconstruct the name from field 9 to end.
### One-liner
```bash
grep -v '^total' input.txt \
| awk '{ name=$9; for (i=10; i<=NF; i++) name = name " " $i;
print $5 "\t" name }' \
| sort -t$'\t' -k1,1nr \
| head -1 \
| cut -f2-
```
For `input` read from a shell variable instead of a file, pipe it in: `printf '%s\n' "$ls_output" | grep -v '^total' | awk ...`.
### How it works
- `grep -v '^total'` drops the `ls -l` header line. (Add `awk 'NF>=9'` if blank or malformed lines are possible.)
- In `awk`, `$5` is the byte size; the filename is rebuilt by concatenating fields `$9..$NF` with single spaces, so spaced names survive. We emit `size <TAB> name`.
- `sort -t$'\t' -k1,1nr` sorts **numerically descending** on the size field only (the tab delimiter prevents the name from leaking into the sort key).
- `head -1` takes the largest; `cut -f2-` strips the size column and prints just the name.
### Pure-`awk` alternative (single pass, no sort)
```bash
grep -v '^total' input.txt \
| awk 'NF>=9 {
name=$9; for (i=10;i<=NF;i++) name=name" "$i;
if ($5+0 > max) { max=$5+0; best=name }
}
END { if (best!="") print best }'
```
### Caveats to raise
- **Spaces vs. arbitrary names:** this handles spaces, but `ls -l` output is genuinely ambiguous if a filename contains a literal newline or tab (or if `ls` quotes/escapes names). The robust answer is *not to parse `ls` at all* — operate on the real filesystem instead:
```bash
# largest regular file in the current dir, NUL-safe
find . -maxdepth 1 -type f -printf '%s\t%P\0' \
| sort -z -t$'\t' -k1,1nr \
| head -z -n1 \
| cut -z -f2- | tr '\0' '\n'
```
- **Ties:** the `sort | head -1` form breaks ties by input order; state the chosen rule.
- **Directories/symlinks:** the size column for a directory is its directory-entry size, not recursive content size — filter with the leading `-`/`d` type char if "file" must exclude directories (`awk '/^-/'`).
---
## Cross-cutting takeaways
Each part hides exactly one correctness gotcha that separates a brittle answer from a solid one: **integer overflow** (Part 1, use 64-bit), **reason normalization + the empty failure list** (Part 2, normalize before counting and `LEFT JOIN` so SUCCESS survives), and **spaces in filenames + the `total` header** (Part 3, numeric sort on the size field, reconstruct the name). In all three, stating assumptions up front (max `n`, SQL dialect/tiebreak, the size metric) is what an interviewer is grading as much as the code itself.