Company Practice

📘 Learn Company Practice from zero

These are all "easy" tier, but FAANG graders judge how cleanly you reason, not whether you eventually pass. Use one disciplined loop on every problem:

1. Read & restate. Say the problem back in your own words and confirm the output type (boolean? array? rebuilt tree?). Surfaces misreads before you waste code.
2. Pin the constraints. Are values bounded (lowercase letters → int[26]; values 0–1000 → counting sort)? Is n small or up to 10⁵? Constraints are the hint — a bounded range points to counting; "k operations" points to a heap.
3. Brute force out loud first. State the obvious O(n²) or simulate-everything solution. It proves you understand the problem and gives a correctness baseline. Never go silent hunting for the clever trick.
4. Spot the pattern. Map a signal to a technique using the framework above — frequency→hash map, sorted-by-rank→bucket, pick-max-repeatedly→heap, tree-compare→DFS. Double-check the mapping: a "subtract" or "max" keyword does not automatically mean heap.
5. Optimize. Replace the bottleneck: a nested membership check becomes a HashSet; a sort-then-scan becomes counting sort when the range is small.
6. Edge cases. Empty input, single element, all-equal, negatives, duplicates, one-node tree, value not present.
7. Test by hand. Trace the given example, then one nasty case. State final time/space complexity unprompted.

Talk through every step. A calm, structured walk on an easy problem signals exactly the engineer they want to hire.

✨ Added by the guide to build intuition — not from the source course.

🎯 Guided practice

Walk-through: Relative Sort Array — sort arr1 so elements appear in the order they occur in arr2; anything not in arr2 goes at the end in ascending order.

1. Restate: output is a permutation of arr1, partially ordered by an external reference list, with leftovers sorted normally.
2. Brute force: a custom comparator — "rank by index in arr2 (via a value→rank map), else sort those leftovers by value, placing them after the ranked ones." Correct and O(n log n). Worth stating as a fallback.
3. Spot the signal: the prompt bounds values to 0–1000. "Sorted output + small bounded range" is the textbook trigger for counting sort, which beats the comparator's O(n log n) with O(n + K).
4. Why counting sort wins here: no comparisons needed. Count every value in arr1 into count[0..1000]. Then walk arr2 in order, emitting each value count[v] times and zeroing it. Finally sweep count 0→1000 to append the untouched leftovers, already ascending for free.

Optimal outline:

• Build count array over arr1 (one pass).
• For each v in arr2: append v exactly count[v] times, then set count[v]=0.
• For v from 0 to 1000: append v exactly count[v] times — these are the not-in-arr2 leftovers, emitted in sorted order automatically.

Complexity: O(n + m + K) time, O(K) extra space (n = arr1 length, m = arr2 length, K = value range, here 1001). Edge cases: values in arr1 not in arr2, duplicates in both, arr2 a strict subset of arr1's distinct values. The lesson: let the constraint (bounded values) pick the technique — that recognition is the whole game.

✨ Added by the guide — work these before the full problem set.