Mock 06 — Big Tech Onsite

Interview type: FAANG onsite coding round (single round of the 4–5 onsite rounds) Target role: FAANG SWE-II / Senior Time limit: 60 minutes total Format: ~5 min intro + 50 min coding (TWO problems back-to-back) + 5 min Q&A Hints policy: One hint per problem acceptable; more is below-bar. Primary goal: Demonstrate sustained performance across two problems without losing tempo.

What This Mock Tests

FAANG onsites run 4–5 of these rounds per day. Each round expects you to solve 1–2 problems in 50 minutes of coding. This mock packs two problems into 60 minutes deliberately — the time pressure is real.

The signal: are you a consistent solver, not a one-hit-wonder? Can you context-switch from problem 1 to problem 2 without resetting?

Scoring weights: all dimensions matter; Time Management is implicit — running out of time on problem 2 is a hard fail signal.

Format

Pick one easy/medium problem (15–20 min) AND one medium/hard problem (30–40 min) from the list below. The interviewer presents one, then immediately the next once you finish. No break.

Problem Set 1 (warm-up: 15–20 min)

A1 — Valid Anagram (LC 242)

Given two strings, determine if one is an anagram of the other.

"anagram", "nagaram"  → True
"rat", "car"          → False

Constraints: 1 ≤ |s|, |t| ≤ 5×10^4. Lowercase English letters (or follow up: Unicode).

A2 — Climbing Stairs (LC 70)

You can climb 1 or 2 steps at a time. How many distinct ways to reach step n?

n = 2 → 2   (1+1, 2)
n = 3 → 3   (1+1+1, 1+2, 2+1)

Constraints: 1 ≤ n ≤ 45.

A3 — Move Zeroes (LC 283)

Given nums, move all 0s to the end while maintaining the relative order of non-zero elements. In-place.

[0,1,0,3,12]  → [1,3,12,0,0]

Problem Set 2 (main: 30–40 min)

B1 — LRU Cache (LC 146)

Design and implement a Least Recently Used cache with get(key) and put(key, value) both in O(1).

LRUCache cache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)       → 1
cache.put(3, 3)    // evicts key 2
cache.get(2)       → -1
cache.put(4, 4)    // evicts key 1
cache.get(1)       → -1
cache.get(3)       → 3
cache.get(4)       → 4

Constraints: 1 ≤ capacity ≤ 3000. At most 10^5 operations.

B2 — Word Break (LC 139)

Given a string s and a dictionary wordDict, return True if s can be segmented into a sequence of dictionary words.

"leetcode", ["leet", "code"]   → True
"applepenapple", ["apple","pen"] → True
"catsandog", ["cats","dog","sand","and","cat"] → False

Constraints: 1 ≤ |s| ≤ 300. 1 ≤ |wordDict| ≤ 1000.

B3 — Course Schedule II (LC 210)

Given numCourses and prerequisites (pairs [a, b] meaning b must be taken before a), return an order in which to take all courses, or [] if impossible.

2, [[1,0]]                    → [0, 1]
4, [[1,0],[2,0],[3,1],[3,2]]  → [0, 1, 2, 3] or [0, 2, 1, 3]
2, [[1,0],[0,1]]              → []

Constraints: 1 ≤ numCourses ≤ 2000. 0 ≤ |prerequisites| ≤ 5000.

Expected Communication Style

For each problem:

  1. Restate
  2. 2–3 clarifying questions (don’t over-ask on the warm-up; do for the main)
  3. Brute force + complexity
  4. Optimal approach + complexity
  5. Code with narration
  6. Test 2–3 cases
  7. Move on to the next problem without dragging

Critical: manage time aggressively. If you blow past 20 min on problem 1, stop and move on. Failing on time is worse than producing partial code on both.

Solution Sketches

A1 Anagram: count chars (Counter or array of 26), compare. O(N + M). A2 Climbing Stairs: Fibonacci. DP or closed form. O(N) or O(1). A3 Move Zeroes: two-pointer, write-pointer advances on non-zero; pad with zeros. O(N) time, O(1) space.

B1 LRU Cache: doubly linked list + hashmap. List front = most recent, tail = LRU. get → move node to front; put → if exists move to front and update; if not, insert at front; if over capacity, remove tail and delete from hashmap. O(1) per op.

B2 Word Break: DP. dp[i] = True if s[:i] can be broken. dp[i] = any(dp[j] and s[j:i] in wordSet) for j < i. O(N² · max_word_len) or O(N²) with set lookup. Watch the off-by-one in dp = [False] * (n + 1); dp[0] = True — a frequent bug.

B3 Course Schedule II: topological sort via Kahn’s algorithm (BFS on indegree). If output length < numCourses, there’s a cycle → return []. O(V + E).

Common Failure Modes

  1. Spent 30 min on the easy. Total fail; you’ll run out for the main problem.
  2. LRU implemented with built-in OrderedDict (Python) without explaining the underlying data structure. Some interviewers accept this; many do not. Always offer to implement from scratch.
  3. Word Break: O(2^N) recursion without memoization. TLE on N=100.
  4. Course Schedule: DFS-based cycle detection but forgot to track three states (unvisited / in-progress / done). Marks node done while in progress → false negatives.
  5. Trying to start problem 2 fresh without acknowledging the time check. Senior signal: “We have 35 min left and this is the main problem; let me dive in.”

Passing Bar

  • Total score: 49/70 (average 3.5)
  • BOTH problems implemented correctly
  • Optimal complexity on the main problem
  • Time managed: problem 1 ≤ 20 min, problem 2 ≤ 40 min
  • Hint usage ≤ 1 total
  • Tests run on both

Follow-up Questions (asked between or after problems)

For B1 (LRU):

  • Make it thread-safe. → Coarse-grained lock; or read-write lock with care; or lock-free with hazard pointers (advanced).
  • LFU instead of LRU. → Two-level structure: hashmap to nodes, hashmap to frequency-buckets, each bucket a doubly-linked list.
  • Distributed LRU across multiple servers. → Consistent hashing + per-shard LRU.
  • Persist to disk. → Write-behind cache; reconstruct on startup.

For B2 (Word Break):

  • Word Break II — return all valid sentences. → Backtracking with memoization on the suffix.
  • Words can be arbitrarily long, dict has 10^6 words. → Trie for prefix lookup during DP, O(N²) using trie traversal.
  • Streaming version: input arrives one char at a time. → Online DP — update dp[i] as i grows; suffix automaton helps for the dict.

For B3 (Course Schedule):

  • Find any cycle and return it. → DFS with parent tracking; on back-edge, walk parents.
  • Schedule to minimize number of semesters (parallel courses). → Longest path in DAG = answer; O(V + E).
  • Add weighted edges (course duration). → Critical path method.

Required Tests

  • All given examples (both problems)
  • Empty / single-element input for problem 1
  • Capacity 1 for LRU
  • Single-word dict and s that exactly equals one word for Word Break
  • Course graph with cycle for B3
  • Self-loop course (numCourses=1, prereq=[[0,0]]) — should return []

Required Complexity Explanation

For both problems, state time and space + identify which one is the bottleneck under the actual constraints (N=300 for Word Break ⇒ O(N²) is fine; N=10^5 ops on LRU ⇒ O(1) per op is mandatory).

Self-Evaluation Template

Mock 06 — Big Tech Onsite
Date: _______
Problem 1: _______ — Time: ___ min, Score: ___/70
Problem 2: _______ — Time: ___ min, Score: ___/70
Total time: ___ / 60 min
Hints used: ___ (across both)

Combined avg score:
Both problems complete? Y/N
Tests run on both? Y/N

What went well:
What went poorly:
Time-management notes:
Action item:

What to Do If You Fail

  • Failed problem 2 due to time: Practice problem 1 against a stricter timer (15 min).
  • Failed problem 2 due to difficulty: Mock 04 (hard LC) needs more reps.
  • Hint-heavy on both: Foundational pattern recognition gap; return to Phase 2.
  • LRU implementation issues: Drill data structure design — Phase 1 lab 04 + 05 (linked lists, stacks/queues).
  • Pass twice consecutively before Mock 07.