Implement staircase printing and distributed mode/median
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
### Problem A: Print a “staircase” pattern
Implement a function that prints a staircase with `n` rows.
**Input**
- An integer `n (n >= 1)`
**Output**
- Print `n` lines.
- Line `i` (1-indexed) contains `i` items separated by a single space.
- **Formatting requirement:** there must be **no trailing space** at the end of any line (i.e., the last item in a line should be printed without an extra delimiter).
- You must also write a small set of test cases to verify correctness (including edge cases like `n = 1`).
**Follow-up:** modify the staircase so that it prints **consecutive integers across the entire output** (e.g., `1`, then `2`, then `3`, continuing across rows), still respecting the “no trailing delimiter” formatting requirement.
---
### Problem B: Compute mode/median in a constrained distributed setting
You have **10 worker nodes**. Each node stores a partition of a dataset of integers locally.
You are given only these primitives:
- `read_local()` to read bytes from local storage at **10 bytes/second**.
- `send(node_id, bytes)` which transmits data at **1 byte/second**.
- `recv(node_id, bytes)` which receives data at **1 byte/second**.
- `barrier()` for synchronization.
**Task**
- Design and implement a workable approach to compute the **global mode** (most frequent value) and/or the **global median**.
- The interviewer will iterate with you: after you present a correct baseline, you should propose improvements to reduce end-to-end time and communication.
**What to discuss while implementing**
- What you choose to transmit (raw data vs summaries).
- Coordination strategy (central aggregator vs hierarchical reduction).
- How your design changes if the value range is small/known vs large/unknown.
- How you would validate correctness and measure end-to-end time under the given byte/second cost model.
Quick Answer: This set of problems evaluates implementation correctness and attention to formatting for a staircase-printing routine alongside distributed-algorithms reasoning for computing a global mode/median, testing algorithmic thinking, I/O handling, synchronization, and communication-cost trade-offs in the Coding & Algorithms domain.
Part 1: Staircase Pattern with No Trailing Spaces
Given an integer n, build a staircase of n rows using the character '*'. Row i must contain exactly i stars separated by a single space. To make the problem easy to test, return the staircase as a list of strings instead of printing it. No row may end with a trailing space.
Constraints
- 1 <= n <= 1000
- Each output row must use exactly one space between adjacent stars
- No trailing spaces are allowed
Examples
Input: 1
Expected Output: ['*']
Explanation: With one row, the staircase contains only a single star.
Input: 4
Expected Output: ['*', '* *', '* * *', '* * * *']
Explanation: Each row adds one more star, and stars are separated by exactly one space.
Hints
- Build each row independently, then join the row items with ' ' so you never create a trailing space.
- The i-th row should contain exactly i copies of the same symbol.
Part 2: Consecutive-Integer Staircase with No Trailing Spaces
Given an integer n, build a staircase of n rows where the numbers continue consecutively across the entire output. Row 1 contains '1'. Row 2 contains '2 3'. Row 3 contains '4 5 6', and so on. Return the staircase as a list of strings. No row may end with a trailing space.
Constraints
- 1 <= n <= 1000
- Numbers start at 1 and increase by 1 each time
- No trailing spaces are allowed
Examples
Input: 1
Expected Output: ['1']
Explanation: There is only one row, so it contains just the first number.
Input: 4
Expected Output: ['1', '2 3', '4 5 6', '7 8 9 10']
Explanation: The numbers continue consecutively across rows: 1, then 2 3, then 4 5 6, then 7 8 9 10.
Hints
- Keep a running number that starts at 1 and increases every time you place a value in the staircase.
- Build each row as a list of strings, then use ' '.join(...) to format it cleanly.
Part 3: Distributed Mode and Median with Communication-Aware Strategy Selection
You are given integer data split across worker nodes. Implement an exact coordinator that computes the global mode and median, but also chooses the cheapest valid communication strategy under a simplified byte-cost model. Your function must consider three strategies: (1) raw: every worker sends every integer; (2) sparse_counts: every worker sends one (value, count) pair for each distinct local value; (3) dense_histogram: if a value_range = (lo, hi) is provided and all data lies inside it, each worker sends one count bucket for every value in that inclusive range. Use these assumptions: every stored integer costs 4 bytes to read; every raw integer sent costs 4 bytes; every sparse (value, count) pair costs 8 bytes; every dense histogram bucket costs 4 bytes. All workers read in parallel, so read_seconds = max bytes read by any single worker / 10. The coordinator is the network bottleneck, so network_seconds = total sent bytes / 1. Return the exact mode and median, the chosen strategy, and the estimated costs. If multiple values are tied for mode, return the smallest such value. If the total element count is even, the median is the average of the two middle values; if that average is an integer, return it as an int. If the dataset is empty, return None for both mode and median. If two strategies send the same number of bytes, prefer dense_histogram over sparse_counts over raw.
Constraints
- 1 <= len(partitions) <= 10
- 0 <= total number of integers <= 200000
- Each integer fits in 32-bit signed range
- If value_range is provided, it should be a tuple (lo, hi) with lo <= hi
Examples
Input: ([[1, 1, 1, 1, 2, 2], [2, 2, 2, 3, 3, 3], [1, 1, 3, 3, 3, 3]], (1, 3))
Expected Output: {'mode': 3, 'median': 2, 'strategy': 'dense_histogram', 'sent_bytes': 36, 'read_seconds': 2.4, 'network_seconds': 36, 'total_seconds': 38.4}
Explanation: Small known range makes a dense histogram cheaper than sending raw values or sparse maps.
Input: ([[1000, 1000, 1000, 1000, 1000, 1000, 1001], [1001, 1001, 1001, 1001, 1001, 1001, 1002], [1002, 1002, 1002, 1002, 1002, 1002]], None)
Expected Output: {'mode': 1001, 'median': 1001, 'strategy': 'sparse_counts', 'sent_bytes': 40, 'read_seconds': 2.8, 'network_seconds': 40, 'total_seconds': 42.8}
Explanation: The values are large and repeated, so sparse local counts are much cheaper than shipping all raw integers.
Hints
- A global frequency map is enough to compute both the exact mode and the exact median, because the median only needs counts in sorted value order.
- Compare total bytes for all valid strategies before choosing one; the cheapest communication plan is not always the same.