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: This three-part question evaluates state-space search and admissible heuristic design for a sliding-block puzzle, O(1)-time and O(1)-space online stream processing for token pattern detection, and large-scale duplicate string detection including hash-based vs external-sort approaches, memory-limit handling, and Unicode normalization.