Sum palindrome-change costs over all substrings

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