CMD Guide
Home › DSA

Company Practice

Step 23 in the DSA path · 2 concepts · 235 problems

0 / 237 complete

📘 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:

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.

Lessons in this topic

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard
In the Company Practice topic's disciplined interview loop, what is the recommended order of steps from reading the problem to coding?
tap to reveal →
Read & restate the problem (confirm output type), pin the constraints, state the brute-force solution out loud first, spot the pattern by mapping a signal to a technique, optimize the bottleneck, then handle edge cases and test by hand.
💡 Restate, Pin, Brute, Spot, Optimize, Edge — 'Really Polished Brains Solve Or Exit'.
Flashcard
What signal-to-technique mappings does the topic overview give for spotting the right pattern?
tap to reveal →
Frequency -> hash map; sorted-by-rank / small bounded range -> bucket or counting sort; pick-max-repeatedly or 'k operations' -> heap; tree-compare -> DFS. But verify: a 'subtract' or 'max' keyword does not automatically mean a heap.
💡 Constraints are the hint: bounded range = counting, 'k' = heap.
Flashcard
How do you count the Number of Islands in a 0/1 matrix, and what are its time and space complexities?
tap to reveal →
Scan the matrix; on each unvisited '1' increment the island count and run DFS/BFS to sink all horizontally/vertically connected land (mark visited by setting cells to 0). Time is O(M*N) and space is O(M*N) for the DFS recursion stack (worst case all land).
💡 Find a 1, count +1, then flood-fill it to 0.
Flashcard
What technique solves Longest Substring Without Repeating Characters, and what is its complexity?
tap to reveal →
A sliding window with a HashSet: expand the end pointer adding chars; on a duplicate, remove the start char and advance start so the window stays unique, tracking the max length. Time O(n) (each pointer crosses once, O(2n)) with HashSet ops O(1) average.
💡 Two pointers + a set = unique window that breathes.
Flashcard
How does Largest Rectangle in Histogram use a monotonic stack to find the max area?
tap to reveal →
Keep a stack of bar indices in ascending height. When the current bar is shorter than the stack top, pop it and compute area = popped height * width, where width is i if the stack is now empty else i - stack.peek() - 1; track the max.
💡 Stack rises; a shorter bar triggers a pop-and-measure.
Flashcard
Why is Subarray Sum Equals K solved with a prefix-sum hashmap seeded with {0:1}?
tap to reveal →
Walk the array keeping a running cumulativeSum; for each element add the frequency of (cumulativeSum - k) to the count, then record cumulativeSum. If two prefix sums differ by k, the elements between them sum to k. Seeding {0:1} counts subarrays starting at index 0. Time O(n).
💡 Prefix sum seen before minus k = a subarray summing to k.
Q1. For Relative Sort Array (values bounded 0-1000, sort arr1 by arr2's order), the topic says the bounded range is the trigger for which optimal technique over a comparator?
Q2. In Trapping Rain Water, the two-pointer method moves the pointer at the smaller bar. Why is that the correct side to process?
Q3. What does Minimum Window Substring use to track whether the current window contains all of t's characters, including duplicates?
Q4. For Number of Islands, what is the purpose of setting each visited land cell to '0' during DFS/BFS?
Q5. K Closest Points to the Origin follows the Top-K pattern. Which heap is used and how is it maintained at size K?