Trace lab in Arrays and Dynamic Lists

Mission

Answer a sequence of zero-based index queries in the order supplied.

Learning outcome: Trace indexed access in contiguous storage

Correctness contract

Invariant: Elements occupy indexes 0 through size - 1, and size never exceeds capacity.

Required technique: Answer each query with direct array indexing; do not scan from index zero for every query.

Complexity target: time O(q); space O(n + q) including input and output.

Input and output

Input: n, then n integers, then query count q followed by q zero-based indexes. Whitespace may be spaces or line breaks.

Output: Print the queried values on one line, separated by single spaces. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n and q are positive.
• Every query index is in the range 0 through n - 1.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Answer each query with direct array indexing; do not scan from index zero for every query.
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 9 8 7 6 5 4 0 2 4 1

Sample output

9 7 5 8

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Each query is answered directly from the requested array slot while preserving query order. Input `5 9 8 7 6 5 4 0 2 4 1` therefore produces `9 7 5 8`.

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.