Study Notes by Niladri & AI

Company-01-Meta

Properties1
tagscompany-prep, meta, interview-prep, java

18 min read

Meta Interview Prep

Interview Profile

  • Format: 5-round loop — 2 coding, 1 system design, 1 behavioral, 1 leadership/values
  • Coding style: Strict LeetCode-style; optimal solution expected; hints are rare — the interviewer expects you to drive
  • Senior bar: Clean code, O(n) solutions, discuss space-time tradeoffs unprompted; naming and structure matter as much as correctness
  • What Meta cares about at senior level: “Move fast” — can you write production-quality code under time pressure? Can you reason about product impact alongside the algorithm? Leadership/values round tests whether you multiply your team, not just yourself.

Pattern Frequency Breakdown

PatternFrequency %Notes
Arrays / Two Pointers / Sliding Window30%Most common phone screen content; expect at least one
Trees & Graphs25%Social graph problems dominate; BFS level-order is a near-certain topic
Dynamic Programming20%Ranking, feed optimization, caching policy problems
HashMap / HashSet15%Design-style problems; O(1) operations heavily tested
Heap / Greedy10%Often appears as a follow-up or second coding problem

Problems From This Repo

ProblemWhy Meta Asks This
Container With Most Water (LC 11)Resource partitioning problems — maximizing utility between two bounds maps to ad-slot allocation and budget distribution
3Sum (LC 15)Extremely frequent Meta phone screen problem; tests whether you can extend two-pointer to a sorted-scan without extra space
Trapping Rain Water (LC 42)Hard variant that tests depth; Meta uses this to differentiate strong candidates from exceptional ones
Longest Repeating Character Replacement (LC 424)Content moderation string problems — detecting near-homogeneous toxic substrings in feeds and comments
Insert Delete GetRandom O(1) (LC 380)Design-style, very common; directly models randomized A/B experiment assignment in the ads system
Binary Tree Level Order Traversal (LC 102)Social graph BFS — friend-of-friend discovery, notification propagation radius
Lowest Common Ancestor (LC 236)Classic Meta question; models finding the shared-owner escalation path in an org chart or permission hierarchy
Binary Tree Maximum Path Sum (LC 124)Hard tree; frequently asked as the second coding problem to confirm a candidate can handle global-state DFS
Number of Islands (LC 200)Connected components — friend cluster detection, identifying isolated sub-graphs in the social network
Longest Increasing Subsequence (LC 300)Ranking systems — finding the longest consistent ordering in a partially-ordered recommendation list

New Problems (Meta-Specific)

Problem 1: Remove Invalid Parentheses (LC 301) — Hard

Link: LeetCode 301

Quick Summary: Given a string with parentheses and letters, remove the minimum number of invalid parentheses to make the string valid. Return all possible valid results.

Industry Context: Meta’s content integrity pipelines need to detect and repair structurally malformed user-generated markup (templated posts, comments with auto-generated formatting tags). The minimum-removal constraint maps directly to the concept of least-invasive content sanitization — you want valid output with the fewest editorial changes.

Approach 1: Brute Force — enumerate all subsets

// Time: O(2^n * n)  Space: O(2^n) — exponential subset enumeration
public List<String> removeInvalidParenthesesBrute(String s) {
    List<String> result = new ArrayList<>();
    int minRemovals = Integer.MAX_VALUE;
 
    // Try every possible subset of characters to remove
    for (int mask = 0; mask < (1 << s.length()); mask++) {
        StringBuilder sb = new StringBuilder();
        int removals = Integer.bitCount(mask);
        if (removals > minRemovals) continue;
 
        for (int i = 0; i < s.length(); i++) {
            if ((mask & (1 << i)) == 0) sb.append(s.charAt(i));
        }
 
        String candidate = sb.toString();
        if (isValid(candidate)) {
            if (removals < minRemovals) {
                minRemovals = removals;
                result.clear();
            }
            if (!result.contains(candidate)) result.add(candidate);
        }
    }
    return result;
}
 
private boolean isValid(String s) {
    int count = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') count++;
        else if (c == ')') {
            if (count == 0) return false;
            count--;
        }
    }
    return count == 0;
}
  • Time: O(2^n * n) — 2^n subsets, each validity check is O(n)
  • Space: O(2^n) — storing candidates
  • Tradeoff: Correct but completely impractical for n > 20. The key flaw is that we have no way to prune early — we must enumerate every subset before knowing which removal count is minimal.

Approach 2: BFS Level-by-Level Pruning (optimal for “minimum removals”)

// Time: O(2^n * n)  Space: O(2^n) — but with level-wise early termination
public List<String> removeInvalidParentheses(String s) {
    List<String> result = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Queue<String> queue = new LinkedList<>();
 
    queue.offer(s);
    visited.add(s);
    boolean found = false;  // once we find valid strings at this level, stop going deeper
 
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
 
        for (int i = 0; i < levelSize; i++) {
            String current = queue.poll();
 
            if (isValid(current)) {
                result.add(current);
                found = true;   // flag: do not enqueue next level
            }
 
            if (found) continue;  // don't generate children once a valid level is found
 
            // Generate all strings with one character removed
            for (int j = 0; j < current.length(); j++) {
                if (current.charAt(j) != '(' && current.charAt(j) != ')') continue;
                String next = current.substring(0, j) + current.substring(j + 1);
                if (!visited.contains(next)) {
                    visited.add(next);
                    queue.offer(next);
                }
            }
        }
 
        if (found) break;  // all valid strings at this removal depth collected
    }
 
    return result;
}
 
private boolean isValid(String s) {
    int count = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') count++;
        else if (c == ')') {
            if (count == 0) return false;
            count--;
        }
    }
    return count == 0;
}
  • Time: O(2^n * n) worst case, but practical due to level-stopping — once any valid string is found at removal depth k, we never explore depth k+1
  • Space: O(2^n) — visited set and queue
  • Key Insight: BFS naturally explores states in order of increasing edit distance from the original string. Each BFS level corresponds to exactly one additional character removal. The found flag is the critical optimization: the first BFS level that contains any valid string gives us all minimum-removal valid strings — we collect all of them before stopping. Without found, you’d explore unnecessary deeper levels. The visited set prevents duplicate work from different removal orderings producing the same string.

Problem 2: Subarray Sum Equals K (LC 560) — Medium

Link: LeetCode 560

Quick Summary: Given an integer array nums and an integer k, return the total number of subarrays whose sum equals k.

Industry Context: Ad impression counting — given a time-series of events (clicks, impressions, engagements) each with a weight, count how many contiguous time windows have exactly k total engagement units. Also maps to feed engagement scoring: given a sequence of post scores, how many consecutive feed segments sum to exactly the target engagement budget?

Approach 1: Brute Force — all subarrays

// Time: O(n²)  Space: O(1)
public int subarraySumBrute(int[] nums, int k) {
    int count = 0;
    for (int start = 0; start < nums.length; start++) {
        int sum = 0;
        for (int end = start; end < nums.length; end++) {
            sum += nums[end];
            if (sum == k) count++;
        }
    }
    return count;
}
  • Time: O(n²) — O(n) starting positions, O(n) extension per start
  • Space: O(1)
  • Tradeoff: Intuitive but quadratic. Works for n ≤ 10^4; fails for n = 10^5 (LeetCode’s actual constraint). The core waste: we recompute prefix sums from scratch for each starting index.

Approach 2: HashMap Prefix Sum (optimal)

// Time: O(n)  Space: O(n)
public int subarraySum(int[] nums, int k) {
    // prefixCount[x] = number of times prefix sum x has been seen so far
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);  // empty prefix — critical for subarrays starting at index 0
 
    int count = 0;
    int prefixSum = 0;
 
    for (int num : nums) {
        prefixSum += num;
        // If (prefixSum - k) has been seen, those prefixes form valid subarrays ending here
        count += prefixCount.getOrDefault(prefixSum - k, 0);
        prefixCount.merge(prefixSum, 1, Integer::sum);
    }
 
    return count;
}
  • Time: O(n) — single pass
  • Space: O(n) — prefix sum map stores at most n+1 distinct values
  • Key Insight: A subarray nums[i..j] has sum k iff prefixSum[j] - prefixSum[i-1] = k, i.e., prefixSum[i-1] = prefixSum[j] - k. So at each index j, the question becomes: “how many times has the value (currentPrefixSum - k) appeared as a prefix sum earlier?” The HashMap answers this in O(1). The sentinel prefixCount.put(0, 1) handles the case where the subarray starts at index 0 (no prior prefix) — forgetting this seed is the most common bug on this problem.

Problem 3: Diameter of Binary Tree (LC 543) — Easy/Medium

Link: LeetCode 543

Quick Summary: The diameter of a binary tree is the length of the longest path between any two nodes, measured in edges. The path may or may not pass through the root.

Industry Context: Network diameter in a hierarchical topology — the maximum latency between any two leaf servers in a data center’s tree network. Also: social graph diameter estimation (how many hops between the most distant friends), and compiler AST analysis (maximum expression depth between two operands). Meta interviewers often use LC 543 as a warm-up before LC 124 (Max Path Sum) since both use the identical “arm + arm at bend point” postorder pattern.

Approach 1: Brute Force — recompute height per node

// Time: O(n²)  Space: O(h)
public int diameterOfBinaryTreeBrute(TreeNode root) {
    if (root == null) return 0;
    // Diameter through this node = left height + right height
    int throughRoot = height(root.left) + height(root.right);
    // Diameter might be entirely in left or right subtree
    int leftBest  = diameterOfBinaryTreeBrute(root.left);
    int rightBest = diameterOfBinaryTreeBrute(root.right);
    return Math.max(throughRoot, Math.max(leftBest, rightBest));
}
 
private int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}
  • Time: O(n²) — height() is called O(n) times, each taking O(n)
  • Space: O(h)
  • Tradeoff: Classic redundant-computation pattern. Every internal node’s height is recomputed from scratch whenever it appears in any ancestor’s height() call. Signals to the interviewer that you recognize the single-pass optimization.

Approach 2: Single-Pass Postorder DFS with global max (optimal)

// Time: O(n)  Space: O(h)
private int maxDiameter;
 
public int diameterOfBinaryTree(TreeNode root) {
    maxDiameter = 0;
    depthForDiameter(root);
    return maxDiameter;
}
 
// Returns the height of the subtree rooted at node (number of edges to deepest leaf)
private int depthForDiameter(TreeNode node) {
    if (node == null) return 0;
    int leftDepth  = depthForDiameter(node.left);
    int rightDepth = depthForDiameter(node.right);
    // At this node as the bend point, diameter = left arm + right arm
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
    // Return the longer arm upward (path cannot bend above this node)
    return 1 + Math.max(leftDepth, rightDepth);
}
  • Time: O(n) — every node visited exactly once
  • Space: O(h) — recursion stack
  • Key Insight: This is the LC 124 pattern in its simplest form. The return value serves the parent (single arm for continued path extension), while the global update serves the answer (both arms joined at the current bend point). The two concerns are deliberately separated: leftDepth + rightDepth is the diameter candidate at this node; 1 + max(leftDepth, rightDepth) is the contribution to the parent. Getting comfortable with this “dual-purpose postorder return” is a prerequisite for LC 124.

Problem 4: Minimum Remove to Make Valid Parentheses (LC 1249) — Medium

Link: LeetCode 1249

Quick Summary: Given a string with parentheses and lowercase letters, remove the minimum number of parentheses to make it valid. Return any valid result.

Industry Context: Meta’s content integrity pipelines for structured posts and comments — user-generated content often contains auto-generated or copy-pasted formatting with unmatched brackets. Unlike LC 301 (which finds all minimum removals), this problem models a streaming sanitization pass: process left-to-right, track unmatched indices, then surgically remove only the offending characters.

Approach 1: Brute Force — count then reconstruct

// Time: O(n)  Space: O(n)  — actually O(n) but with two passes and less clarity
public String minRemoveToMakeValidBrute(String s) {
    // Count unmatched closing brackets first
    int openCount = 0, closeToRemove = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') openCount++;
        else if (c == ')') {
            if (openCount > 0) openCount--;
            else closeToRemove++;
        }
    }
    // openCount now holds unmatched opening brackets to remove (from right side)
    int openToRemove = openCount;
 
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (c == '(') {
            if (openToRemove > 0) { openToRemove--; continue; }  // skip leftmost unmatched opens
        } else if (c == ')') {
            if (closeToRemove > 0) { closeToRemove--; continue; }
        }
        sb.append(c);
    }
    return sb.toString();
}
  • Time: O(n) — two passes
  • Space: O(n) — output buffer
  • Tradeoff: Correct and O(n), but removes leftmost unmatched opens rather than rightmost, which can produce a different valid answer than the stack approach. Both are acceptable per the problem statement, but explaining which unmatched brackets are removed matters to Meta interviewers asking follow-ups.

Approach 2: Stack Index Tracking (optimal — precise removal set)

// Time: O(n)  Space: O(n)
public String minRemoveToMakeValid(String s) {
    Deque<Integer> openIndices = new ArrayDeque<>();  // stack of unmatched '(' indices
    Set<Integer> toRemove = new HashSet<>();
 
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            openIndices.push(i);        // tentatively mark — might be matched later
        } else if (c == ')') {
            if (!openIndices.isEmpty()) {
                openIndices.pop();      // matched — remove tentative mark
            } else {
                toRemove.add(i);        // unmatched ')' — mark for removal immediately
            }
        }
    }
 
    // Any indices left in stack are unmatched '(' characters
    while (!openIndices.isEmpty()) toRemove.add(openIndices.pop());
 
    // Reconstruct without the marked indices
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (!toRemove.contains(i)) sb.append(s.charAt(i));
    }
    return sb.toString();
}
  • Time: O(n) — single left-to-right pass + one reconstruction pass
  • Space: O(n) — stack and removal set
  • Key Insight: Track indices, not just counts. A count-based approach tells you how many to remove but not which ones; the stack-of-indices approach gives you exact positions. Push open-bracket indices onto the stack; when a close bracket arrives and the stack is non-empty, pop (matched). Unmatched close brackets get added to toRemove immediately; unmatched open brackets remain in the stack after the pass and are drained into toRemove. This produces the rightmost removal of unmatched opens — the most natural human-readable result. For Meta follow-ups: this extends directly to multi-character tags and nested XML-style markup.

Problem 5: Add Strings (LC 415) — Easy (with Hard Follow-Ups)

Link: LeetCode 415

Quick Summary: Given two non-negative integers represented as strings, return their sum as a string. Do not use built-in BigInteger or convert directly to integers.

Industry Context: Meta’s financial systems (payments infrastructure, advertiser billing) handle arbitrary-precision currency amounts that exceed long range. BigDecimal addition in Java is essentially this algorithm under the hood. Meta follows up with: (1) negative numbers — handle sign prefix; (2) different bases — generalize the digit extraction; (3) multiplication of large strings; (4) why does this matter when Java has BigDecimal? — answer: custom precision control, serialization format compatibility, and performance in hot-path billing calculations.

Approach 1: Brute Force — use Long/BigInteger parsing

// Time: O(n)  Space: O(n) — but disallowed by the problem
public String addStringsBrute(String num1, String num2) {
    // This is what the problem explicitly forbids — shown for contrast only
    java.math.BigInteger a = new java.math.BigInteger(num1);
    java.math.BigInteger b = new java.math.BigInteger(num2);
    return a.add(b).toString();
}
  • Time: O(n)
  • Space: O(n)
  • Tradeoff: Correct but disallowed. Including this approach explicitly in an interview signals you understand the constraint and why it exists — do not just skip it silently.

Approach 2: Two-Pointer Right-to-Left Addition (optimal)

// Time: O(max(n, m))  Space: O(max(n, m) + 1)
public String addStrings(String num1, String num2) {
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int carry = 0;
    StringBuilder sb = new StringBuilder();
 
    while (i >= 0 || j >= 0 || carry != 0) {
        int digit1 = (i >= 0) ? (num1.charAt(i--) - '0') : 0;
        int digit2 = (j >= 0) ? (num2.charAt(j--) - '0') : 0;
        int sum = digit1 + digit2 + carry;
        carry = sum / 10;
        sb.append(sum % 10);
    }
 
    return sb.reverse().toString();
}
 
// Follow-up: handle negative numbers (sign prefix)
public String addStringsWithSign(String num1, String num2) {
    boolean neg1 = num1.startsWith("-");
    boolean neg2 = num2.startsWith("-");
    String abs1 = neg1 ? num1.substring(1) : num1;
    String abs2 = neg2 ? num2.substring(1) : num2;
 
    if (neg1 == neg2) {
        // Same sign: add magnitudes, keep the sign
        String sum = addStrings(abs1, abs2);
        return neg1 ? "-" + sum : sum;
    } else {
        // Different signs: subtract smaller from larger, keep larger's sign
        int cmp = compareAbs(abs1, abs2);
        if (cmp == 0) return "0";
        String larger  = cmp > 0 ? abs1 : abs2;
        String smaller = cmp > 0 ? abs2 : abs1;
        boolean resultNeg = cmp > 0 ? neg1 : neg2;
        String diff = subtractStrings(larger, smaller);
        return resultNeg ? "-" + diff : diff;
    }
}
 
// Helper: compare two non-negative number strings by magnitude
private int compareAbs(String a, String b) {
    if (a.length() != b.length()) return Integer.compare(a.length(), b.length());
    return a.compareTo(b);
}
 
// Helper: subtract smaller from larger (both non-negative, larger >= smaller)
private String subtractStrings(String larger, String smaller) {
    int i = larger.length() - 1;
    int j = smaller.length() - 1;
    int borrow = 0;
    StringBuilder sb = new StringBuilder();
 
    while (i >= 0) {
        int d1 = larger.charAt(i--) - '0';
        int d2 = (j >= 0) ? (smaller.charAt(j--) - '0') : 0;
        int diff = d1 - d2 - borrow;
        if (diff < 0) { diff += 10; borrow = 1; }
        else borrow = 0;
        sb.append(diff);
    }
 
    // Remove leading zeros
    while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0') {
        sb.deleteCharAt(sb.length() - 1);
    }
    return sb.reverse().toString();
}
  • Time: O(max(n, m)) — single right-to-left pass over both strings
  • Space: O(max(n, m) + 1) — output buffer; the +1 is for a possible carry overflow digit
  • Key Insight: Process digits from least-significant (rightmost) to most-significant, exactly how you learned to add on paper. The carry variable carries over the tens place. The loop condition i >= 0 || j >= 0 || carry != 0 elegantly handles unequal-length strings and a final carry in one clause. StringBuilder.reverse() avoids manual index management. For the follow-up with signs: decompose into same-sign (addition) and different-sign (subtraction) cases — never mix sign logic into the core arithmetic. This separation is how BigDecimal is actually implemented.

System Design Connections

Algorithm PatternMeta Product Mapping
Two Pointers / Sliding WindowAd targeting — scan impression windows for engagement rate thresholds
HashMap / Prefix Sum (LC 560)Ad impression counting — subarray sum of engagement events per time window
BFS Level-OrderSocial graph — friend-of-friend discovery, notification propagation radius
Tree DFS / LCAOrg chart escalation — finding shared ownership path for incident routing
Tree Max Path SumFeed ranking — maximum-value content path in a recommendation tree
Connected Components (BFS/DFS)Friend cluster detection — identifying isolated sub-communities
Dynamic ProgrammingFeed ranking models — optimal sequencing of content given engagement predictions
Parentheses / StackContent integrity — structured markup validation in posts and comments
Arbitrary Precision ArithmeticPayments infrastructure — advertiser billing with sub-cent precision

2-Week Sprint Plan

Week 1: Arrays / Strings / HashMap

DayFocusProblems
MonTwo Pointers reviewLC 11, LC 15 (re-solve cold)
TueTwo Pointers hardLC 42 (re-solve cold)
WedSliding WindowLC 424 (re-solve); LC 560 (new)
ThuHashMap designLC 380 (re-solve); LC 1249 (new)
FriStrings / ArithmeticLC 301 (new); LC 415 (new + follow-ups)
SatMock sessionOne problem from each category, timed 35 min
SunReview + write up tradeoffsArticulate why each Meta-specific context matters

Week 2: Trees / Graphs / DP

DayFocusProblems
MonTree BFS patternsLC 102 (re-solve cold); walk through social graph analogy
TueTree DFS hardLC 236, LC 543 (re-solve cold)
WedTree DFS hardestLC 124 (re-solve cold); compare with LC 543
ThuGraphsLC 200 (re-solve cold); discuss cluster detection at scale
FriDPLC 300 (re-solve cold); connect to ranking system design
SatFull mock loop2 problems back-to-back, 35 min each, behavioral debrief
SunSystem design integrationWalk through one end-to-end Meta system using patterns from this sheet

Senior-Level Talking Points

How to Discuss Time/Space Tradeoffs at Meta

Meta expects you to lead the tradeoff discussion without being prompted. Use this structure:

  1. State the naive solution first — even if you know the optimal, naming the O(n²) approach shows you understand why the optimization matters.
  2. Identify the bottleneck explicitly — “The redundant recomputation is in height() being called O(n) times” — not just “it’s slow.”
  3. Name the pattern being applied — “We can amortize this by memoizing into a HashMap / converting to a single-pass postorder DFS.”
  4. Quantify the improvement — “This brings us from O(n²) to O(n) time, trading O(n) extra space for the prefix sum map.”
  5. Offer to optimize space if time permits — for prefix sum problems, mention that you could reduce space by streaming with a sliding approach where applicable.

Follow-Up Questions Meta Commonly Asks

  • “What if the input is a stream?” — Affects sliding window bounds; prefix sum requires rethinking.
  • “What if the tree has 10 million nodes?” — Discuss iterative DFS to avoid stack overflow, and consider disk-based tree traversal (B-tree paging).
  • “What if we need to handle this for multiple queries?” — Precomputation: build prefix sum arrays, parent maps, or sparse tables once; amortize over Q queries.
  • “How would you test this in production?” — Property-based tests, edge cases (empty input, single node, all-negative values), and a comparison oracle against the brute-force solution.
  • “Walk me through a real product that uses this.” — Always have a Meta-specific answer ready (see System Design Connections table above).

Behavioral Signals Meta Looks For Alongside Code Quality

  • Clarity under pressure: narrate your thought process continuously; silence reads as confusion.
  • Ownership of bugs: when you hit a bug mid-solution, say “I see the issue — I forgot the carry overflow case, fixing now” rather than silently editing.
  • Move fast, iterate: write a working solution first, then optimize; Meta values shipped code over perfect-but-unfinished code.
  • Product reasoning: connect your algorithm to a product outcome at least once during the coding portion — it signals you think like an engineer, not a puzzle solver.
  • Scale awareness: mention O(n) vs O(n²) unprompted; reference real dataset sizes (billions of posts, hundreds of millions of users).

Graph View