Implementation lab in Hash Tables and Collision Reasoning

Mission

Count tokens while preserving first-seen key order.

Learning outcome: Implement a frequency table

Correctness contract

Invariant: Equal keys produce equal hashes, and collision handling preserves every distinct key.

Required technique: Use a LinkedHashMap so counts and first-seen key order are both preserved.

Complexity target: time O(n) average; space O(k).

Input and output

Input: n followed by exactly n whitespace-delimited tokens. Whitespace may be spaces or line breaks.

Output: Print key:count pairs in first-seen key order, separated by single spaces. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• The declared count is non-negative and is followed by exactly that many whitespace-delimited tokens.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Use a LinkedHashMap so counts and first-seen key order are both preserved.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

5 red blue red red blue

Sample output

red:3 blue:2

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Each token increments one map count, while first insertion order determines the report order. Input `5 red blue red red blue` therefore produces `red:3 blue:2`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.