How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Optiver.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Optiver during technical interviews.

Solve three mini-game algorithm tasks | Optiver Coding Question

Quick Overview

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.

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

Input: ([[1, 2], [3, 0]], [[1, 0], [3, 2]])

Expected Output: 1

Explanation: Slide the block 2 down into the empty cell (one move).

Input: ([[1, 2, 3], [4, 0, 5], [7, 8, 6]], [[1, 2, 3], [4, 5, 6], [7, 8, 0]])

Expected Output: 2

Explanation: Move 5 left then 6 up: two moves to reach the solved board.

Input: ([[1, 2], [3, 0]], [[2, 1], [3, 0]])

Expected Output: -1

Explanation: Swapping only tiles 1 and 2 while the blank stays put is an odd permutation and is unreachable in a 2x2 puzzle.

Input: ([[0, 1], [2, 3]], [[3, 2], [1, 0]])

Expected Output: 6

Explanation: This is the farthest reachable 2x2 configuration from the start, requiring the full diameter of 6 moves.

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.

Input: ([5],)

Expected Output: [1]

Explanation: 5 is odd.

Input: (["←"],)

Expected Output: [0]

Explanation: A lone arrow has no previous arrow, so 0.

Input: ([0, 1, 2, 7, 8],)

Expected Output: [0, 1, 0, 1, 0]

Explanation: Odd integers 1 and 7 output 1; 0, 2, 8 are even.

Input: (["←", "→", "→", "→", "↑"],)

Expected Output: [0, 0, 1, 1, 0]

Explanation: ←:0; →:0 (differs); →:1; →:1; ↑:0 (differs).

Input: (["↑", 3, "↑"],)

Expected Output: [0, 1, 1]

Explanation: First ↑:0; 3:1 (odd); second ↑:1 because the previous arrow was ↑ (the integer in between is skipped).

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.

Input: (["unique"],)

Expected Output: {}

Explanation: A single occurrence is not a duplicate.

Input: (["a", "b", "c"],)

Expected Output: {}

Explanation: All distinct, nothing repeats.

Input: (["x", "x", "x", "x"],)

Expected Output: {"x": 4}

Explanation: x appears four times.

Input: (["café", "cafe", "café"],)

Expected Output: {"café": 2}

Explanation: Exact comparison keeps 'café' (with the accent) separate from 'cafe'; only 'café' repeats.

Input: (["", "", "a"],)

Expected Output: {"": 2}

Explanation: The empty string repeats twice; 'a' occurs once.

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.

Quick Overview

Solve three mini-game algorithm tasks

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Move-House Puzzle: Minimum Sliding Moves

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

Input: ([[1, 2], [3, 0]], [[1, 0], [3, 2]])

Expected Output: 1

Explanation: Slide the block 2 down into the empty cell (one move).

Input: ([[1, 2, 3], [4, 0, 5], [7, 8, 6]], [[1, 2, 3], [4, 5, 6], [7, 8, 0]])

Expected Output: 2

Explanation: Move 5 left then 6 up: two moves to reach the solved board.

Input: ([[1, 2], [3, 0]], [[2, 1], [3, 0]])

Expected Output: -1

Explanation: Swapping only tiles 1 and 2 while the blank stays put is an odd permutation and is unreachable in a 2x2 puzzle.

Input: ([[0, 1], [2, 3]], [[3, 2], [1, 0]])

Expected Output: 6

Explanation: This is the farthest reachable 2x2 configuration from the start, requiring the full diameter of 6 moves.

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

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.

Input: ([5],)

Expected Output: [1]

Explanation: 5 is odd.

Input: (["←"],)

Expected Output: [0]

Explanation: A lone arrow has no previous arrow, so 0.

Input: ([0, 1, 2, 7, 8],)

Expected Output: [0, 1, 0, 1, 0]

Explanation: Odd integers 1 and 7 output 1; 0, 2, 8 are even.

Input: (["←", "→", "→", "→", "↑"],)

Expected Output: [0, 0, 1, 1, 0]

Explanation: ←:0; →:0 (differs); →:1; →:1; ↑:0 (differs).

Input: (["↑", 3, "↑"],)

Expected Output: [0, 1, 1]

Explanation: First ↑:0; 3:1 (odd); second ↑:1 because the previous arrow was ↑ (the integer in between is skipped).

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)

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.

Input: (["unique"],)

Expected Output: {}

Explanation: A single occurrence is not a duplicate.

Input: (["a", "b", "c"],)

Expected Output: {}

Explanation: All distinct, nothing repeats.

Input: (["x", "x", "x", "x"],)

Expected Output: {"x": 4}

Explanation: x appears four times.

Input: (["café", "cafe", "café"],)

Expected Output: {"café": 2}

Explanation: Exact comparison keeps 'café' (with the accent) separate from 'cafe'; only 'café' repeats.

Input: (["", "", "a"],)

Expected Output: {"": 2}

Explanation: The empty string repeats twice; 'a' occurs once.

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.