Quick Overview

This question evaluates algorithmic and systems engineering skills related to batch image processing, parallelization, I/O versus CPU trade-offs, and deterministic output association within the Coding & Algorithms domain.

Generate outputs for images and pipelines

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given **m input images** and **n processing pipelines**. - Each pipeline is an ordered list of **k operations** (e.g., resize, rotate, crop, blur, color transform). - Applying a pipeline to an image produces a new output image. ### Task Write a function/program that produces **m × n output images** by applying **every pipeline** to **every input image**. ### Requirements - Each output should be associated with `(image_id, pipeline_id)`. - The pipeline operations must be applied **in order**. - Assume images are stored as file paths; pipelines are provided as callable operations. - Your implementation should be structured so it can be **parallelized easily** (e.g., avoid unnecessary repeated work such as reading the same image multiple times). ### Input/Output (one reasonable interface) - Input: - `image_paths: List[str]` (size m) - `pipelines: List[List[Callable[[Image], Image]]]` (size n, each of length k) - `output_dir: str` - Output: - Write `m*n` images to `output_dir` with deterministic names like `img{idx}_pipe{j}.png`, or return a list of output file paths. ### Constraints (assume) - `m, n` can be large enough that runtime and I/O efficiency matter. - Operations may be CPU-bound; image decoding/encoding is I/O-bound. ### Follow-up discussion (no need to implement) - How would you scale this for large `m` and `n`? - What parallelization strategy would you choose and why?

Overview: This question evaluates algorithmic and systems engineering skills related to batch image processing, parallelization, I/O versus CPU trade-offs, and deterministic output association within the Coding & Algorithms domain.

Apply a set of integer **pipelines** to a set of **images** and produce one named output for every (image, pipeline) pair. This is an interview-friendly version of an image-processing problem: instead of real image objects, each image path maps to a single **integer value** in `image_store`. Each pipeline is a list of operations applied **in order**, left to right. ## What to implement ```python def solution(image_paths, image_store, pipelines, output_dir): ... ``` For **every** image index `i` (over `image_paths`) and **every** pipeline index `j` (over `pipelines`), run pipeline `j` on image `i`'s value and emit one result. ## Input - **`image_paths`** — list of image-path strings. The value of image `i` is `image_store[image_paths[i]]`. - **`image_store`** — dict mapping each image path to its integer value. Every path in `image_paths` is present as a key. - **`pipelines`** — list of pipelines. Each pipeline is a list of operation tuples (a pipeline may be empty). - **`output_dir`** — string used as the directory prefix for output file names. ## Operations Each operation transforms the current integer value `v`: - **`('ADD', x)`** → `v + x` - **`('SUB', x)`** → `v - x` - **`('MUL', x)`** → `v * x` - **`('NEG',)`** → `-v` Operations within a pipeline are applied sequentially in the order they appear. An **empty pipeline** performs no operations and leaves the value unchanged (identity). ## Output Return a **list of `(output_path, result_value)` tuples**. For image index `i` and pipeline index `j`: - **`result_value`** is image `i`'s value after running pipeline `j`'s operations in order. - **`output_path`** is built from `output_dir` plus the file name `img{i}_pipe{j}.png`: - Strip **any** trailing `/` characters from `output_dir`, then join with `/`. Example: `output_dir = 'tmp/'` (or `'tmp'`) → `tmp/img0_pipe0.png`. - If `output_dir` is the empty string `''` (or becomes empty after stripping trailing slashes), there is **no** leading separator → `img0_pipe0.png`. **Ordering:** results are ordered **first by image index `i`, then by pipeline index `j`** (image `0` with every pipeline, then image `1` with every pipeline, and so on). The returned list therefore has exactly `len(image_paths) * len(pipelines)` entries. ## Notes & edge cases - If the same image path appears multiple times in `image_paths`, an output is still produced for **each position** (each index `i` is independent). - An empty `image_paths` or empty `pipelines` yields an empty result list. - Your approach should **avoid unnecessary repeated work** — e.g. don't reload the same image path more than once, and don't re-run a pipeline's operation list from scratch for every image. ## Constraints - `0 <= len(image_paths)`, `0 <= len(pipelines)` - A pipeline may be empty. - All paths in `image_paths` exist in `image_store`. - The total number of operations across all pipelines is at most `2 * 10^5`. - The returned list has exactly `len(image_paths) * len(pipelines)` entries, so any solution must spend at least `O(m * n)` time to build the output (where `m = len(image_paths)`, `n = len(pipelines)`). ## Example ``` image_paths = ['a.png', 'b.png'] image_store = {'a.png': 2, 'b.png': 5} pipelines = [[('ADD', 3), ('MUL', 2)], [('NEG',), ('SUB', 4)]] output_dir = 'out' # pipeline 0 on 2: (2+3)*2 = 10 ; pipeline 1 on 2: -(2)-4 = -6 # pipeline 0 on 5: (5+3)*2 = 16 ; pipeline 1 on 5: -(5)-4 = -9 => [('out/img0_pipe0.png', 10), ('out/img0_pipe1.png', -6), ('out/img1_pipe0.png', 16), ('out/img1_pipe1.png', -9)] ```

Constraints

  • 0 <= len(image_paths), len(pipelines)
  • A pipeline may be empty
  • All paths in `image_paths` exist in `image_store`
  • The total number of operations across all pipelines is at most 2 * 10^5
  • The returned list has exactly `len(image_paths) * len(pipelines)` entries, so any solution must spend at least O(m*n) time to build the output

Examples

Input: (['a.png', 'b.png'], {'a.png': 2, 'b.png': 5}, [[('ADD', 3), ('MUL', 2)], [('NEG',), ('SUB', 4)]], 'out')

Expected Output: [('out/img0_pipe0.png', 10), ('out/img0_pipe1.png', -6), ('out/img1_pipe0.png', 16), ('out/img1_pipe1.png', -9)]

Input: (['x', 'x', 'y'], {'x': -3, 'y': 0}, [[], [('MUL', -1), ('ADD', 2)], [('SUB', 5), ('NEG',)]], 'res')

Expected Output: [('res/img0_pipe0.png', -3), ('res/img0_pipe1.png', 5), ('res/img0_pipe2.png', 8), ('res/img1_pipe0.png', -3), ('res/img1_pipe1.png', 5), ('res/img1_pipe2.png', 8), ('res/img2_pipe0.png', 0), ('res/img2_pipe1.png', 2), ('res/img2_pipe2.png', 5)]

Hints

  1. Each supported operation keeps the form `a*x + b`. Try compressing each whole pipeline into one pair `(a, b)` before processing the images.
  2. If the same path appears more than once in `image_paths`, cache its loaded value so you do not conceptually decode it multiple times.

Loading coding console...

Show the approach

Approach

Key idea: every pipeline is an affine function. Each operation only ever scales or shifts the value, so the whole pipeline collapses into a single linear map v -> a*v + b. We can compute (a, b) once per pipeline and then apply it in O(1) for every image, instead of replaying the operation list for each image.

Building the transforms. For each pipeline we start at the identity (a, b) = (1, 0) and fold in operations:

  • ADD x / SUB x: shift only, so b += x / b -= x.
  • MUL x: scales the current expression a*v + b, so both coefficients scale: a *= x; b *= x.
  • NEG: negates the whole expression: a = -a; b = -b.

An empty pipeline stays (1, 0), correctly acting as identity. Unknown ops raise ValueError.

Producing outputs. loaded caches each path's value the first time it's seen, so a repeated path isn't "reloaded" (it's still emitted once per position, satisfying the multiplicity rule). base = output_dir.rstrip('/') normalizes a trailing slash; when base is empty the path has no leading /. The nested loop walks images (outer i) then pipelines (inner j), so results come out ordered by image index then pipeline index, and each value is just a*value + b.

Why correct: affine maps are closed under composition, and the fold above is exactly that composition applied left-to-right in pipeline order, so a*value + b equals running the raw operations sequentially. The cartesian-product loop yields exactly len(image_paths) * len(pipelines) tuples with the required img{i}_pipe{j}.png names and ordering.

Time complexity:
O(P + m*n), where P is the total number of operations across all pipelines (≤ 2*10^5), m = len(image_paths), and n = len(pipelines). Building transforms is O(P); the output double loop is O(m*n), which is required since the result has exactly m*n entries.
Space complexity:
O(u + n) auxiliary space (excluding the returned list): O(n) for the precomputed `transforms` and O(u) for the `loaded` cache, where u is the number of distinct image paths.