Katkat
Back

Sum palindrome-change costs over all substrings

IntuitSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates understanding of string algorithms, combinatorial counting, and algorithmic optimization for aggregating pairwise mismatch costs across 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.

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

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.

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.

Hints

Hint 1

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 2

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 3

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

Hint 4

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.

Hint 5

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.

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