Core Data Structures, Sorting, And Complexity

What's being tested

Apple coding screens probe data-structure selection, sorting tradeoffs, and precise time/space complexity reasoning under small implementation constraints. Expect to justify why an array, hash map, heap, stack, queue, or set is the right fit, then code cleanly with edge cases handled.

Patterns & templates

• Hash map aggregation — use dict / defaultdict(list) for per-key grouping in O(n) average time; discuss collision and memory tradeoffs.

• Top-k per key — maintain a min-heap of size k with heapq; O(n log k) beats full sorting at O(n log n).

• Two pointers on sorted arrays — shrink/search from both ends in O(n) time; confirm whether sorting cost O(n log n) is allowed.

• Sliding window for contiguous substrings/subarrays — expand right, contract left, update counts in dict; watch duplicate handling and empty inputs.

• Stack validation — bracket matching, monotonic stack, and undo-style parsing; O(n) time, O(n) worst-case space.

• Python list/dict mechanics — list.append amortized O(1), dict lookup average O(1), insertion order preserved in Python 3.7+.

• Complexity narration — state variables clearly: n items, m unique keys, k retained scores; separate algorithmic cost from input parsing.

Common pitfalls

Pitfall: Sorting everything when only top three are needed; use a bounded heap or fixed-size sorted list per student instead.

Pitfall: Claiming dict operations are always O(1) without saying average-case; adversarial hashing and resizing are real caveats.

Pitfall: Coding the happy path first and missing empty arrays, duplicate values, single-element inputs, invalid brackets, or tied scores.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.