Solve three mini-game algorithm tasks
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Solve three mini-game algorithm tasks:
(a) Move-House Puzzle: Given initial and target arrangements of N labeled blocks ("houses") on a 2D grid with one empty cell, where a move slides one adjacent block into the empty cell, return the minimal number of moves to reach the target or -1 if impossible; describe your state encoding and search (BFS or A* with an admissible heuristic).
(b) Arrow-or-Odd Stream: Given a stream where each token is either an arrow (←, →, ↑, ↓) or a non-negative integer, output 1 if the token is an arrow with the same direction as the immediately previous arrow token, or if the token is an odd integer; otherwise output 0; achieve O(
1) time and O(
1) extra space per token.
(c) Find Identical Strings: Given up to 10^6 strings (possibly Unicode), return all strings that appear more than once with their frequencies; discuss hash-based vs external sort approaches, memory limits, and normalization of equivalent strings.
Quick Answer: Solve three mini-game algorithm tasks evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Move-House Puzzle: Minimum Sliding Moves
You are given two 2D grids, `start` and `target`, each an R x C arrangement of N labeled blocks ("houses") plus exactly one empty cell, represented by `0`. In one move you may slide any block that is orthogonally adjacent to the empty cell into the empty cell (equivalently, swap the empty cell with one of its up/down/left/right neighbors).
Return the minimum number of moves needed to transform `start` into `target`, or `-1` if it is impossible.
Approach: encode each grid as a flat tuple and run a breadth-first search from the start state; BFS gives the shortest path in an unweighted state graph. Each state expands into at most 4 neighbors by moving the empty cell. (A* with the sum of Manhattan distances of each tile to its goal is an admissible speed-up for larger boards.)
Assumptions: `start` and `target` are rectangular grids of identical dimensions; each contains the integer `0` exactly once and the remaining cells form the same multiset of labels (otherwise the answer is `-1`).
Constraints
- 1 <= R, C and R*C <= ~12 for an exact BFS to remain tractable.
- Exactly one cell in each grid equals 0 (the empty cell).
- start and target share the same dimensions and the same multiset of labels.
- Return -1 when the target permutation is unreachable (e.g. an odd permutation given the empty-cell parity).
Examples
Input: ([[1, 2], [3, 0]], [[1, 2], [3, 0]])
Expected Output: 0
Explanation: Start already equals target, so zero moves are needed.
Input: ([[1, 2], [0, 3]], [[1, 2], [3, 0]])
Expected Output: 1
Explanation: Slide the block 3 left into the empty cell (one move).
Hints
- Encode a grid as a flat tuple so it can be a dictionary/set key for the visited check.
- BFS layer-by-layer gives the shortest move count in an unweighted state graph; the first time you reach target is optimal.
- Generate neighbors by swapping the empty cell (0) with each in-bounds orthogonal neighbor.
- Parity matters: in a 2x2 board with a fixed blank position, a single transposition of two tiles is unreachable.
Arrow-or-Odd Stream
Process a stream of tokens where each token is either an arrow (one of the strings "←", "→", "↑", "↓") or a non-negative integer. For each token, output `1` if EITHER:
- the token is an arrow whose direction equals the immediately previous ARROW token seen in the stream, OR
- the token is an odd integer;
otherwise output `0`. Return the list of per-token outputs (same length and order as the input).
Key subtlety: "immediately previous arrow token" skips over any integers in between — an integer does NOT reset the remembered direction. The very first arrow has no predecessor, so it outputs `0`.
Each token is handled in O(1) time and O(1) extra state (just the last-seen arrow direction).
Constraints
- Each token is one of the four arrow glyphs or a non-negative integer.
- The first arrow in the stream always outputs 0 (no previous arrow).
- Integers between two arrows do not reset the remembered previous-arrow direction.
- 0 is even, so it outputs 0.
Examples
Input: (["→", "→", "↑", 3, 4, "↑"],)
Expected Output: [0, 1, 0, 1, 0, 1]
Explanation: First →:0 (no prior arrow); second →:1 (matches); ↑:0 (differs from →); 3:1 (odd); 4:0 (even); final ↑:1 (matches the previous arrow ↑, the 3 and 4 did not reset it).
Input: ([],)
Expected Output: []
Explanation: Empty stream yields an empty output.
Hints
- Maintain a single variable holding the last arrow direction you saw.
- Only arrow tokens update that variable; integers leave it unchanged.
- An odd integer scores 1 regardless of any arrows around it.
- Compare the current arrow to the stored previous arrow before updating the stored value.
Find Identical Strings (Duplicates with Frequencies)
Given a list of up to 10^6 strings (possibly containing Unicode characters), return a mapping from each string that appears more than once to the number of times it appears. Strings that occur exactly once are excluded.
Approach: a single hash-map pass counts every string in O(n) expected time; then keep only entries with count > 1. This is the in-memory hash-based method. If the data exceeds RAM, the classic alternative is an external merge sort (sort the strings on disk, then scan for adjacent runs) or sharding by hash into bucket files that each fit in memory.
Normalization note: equivalent-but-distinct byte sequences (e.g. NFC vs NFD Unicode forms, or case folding) should only be merged if the problem says so. Here strings are compared exactly as given, so "café" and "cafe" are different keys.
Constraints
- 0 <= number of strings <= 10^6.
- Strings may contain arbitrary Unicode characters, including the empty string.
- Only strings with frequency >= 2 appear in the result.
- Comparison is exact: no implicit case folding or Unicode normalization.
Examples
Input: (["apple", "banana", "apple", "cherry", "banana", "apple"],)
Expected Output: {"apple": 3, "banana": 2}
Explanation: apple appears 3 times and banana 2 times; cherry appears once and is excluded.
Input: ([],)
Expected Output: {}
Explanation: No strings, so no duplicates.
Hints
- A single pass with a hash map from string to count is enough.
- After counting, filter to entries whose count exceeds 1.
- The empty string is a valid key and can be a duplicate.
- If the input does not fit in memory, fall back to external sort or hash-bucket sharding.