Solve three mini-game algorithm tasks
Overview
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.
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(
- time and O(
- 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.