META SPECIFIC

Question 1

What are common graph-related problems asked at Meta?

Answer 1

Topological Sorting Course Schedule (Leetcode 207)

BFS/DFS Word Ladder (Leetcode 127)

Dijkstra’s Algorithm Network Delay Time (Leetcode 743)

Union-Find Redundant Connection (Leetcode 684)

Question 2

How do you detect cycles in a directed graph?

Answer 2

DFS with a recursion stack (White-Gray-Black Method)

Kahn’s Algorithm (BFS with in-degree count)

Question 3

What are common DP problems at Meta?

Answer 3

Subarray/Substring Maximum Subarray (Kadane’s Algorithm)

Knapsack Variants 0/1 Knapsack, Coin Change

Grid Pathfinding Unique Paths, Minimum Path Sum

Sequence Problems Longest Increasing Subsequence, Edit Distance

Question 4

When should you use BFS vs. DFS in graph traversal?

Answer 4

BFS Shortest path (unweighted), level-order traversal

DFS Cycle detection, topological sorting, deep recursion problem

Question 5

How do you find the longest increasing subsequence (LIS)

Answer 5

O(n²) DP Approach: Use a dp array where dp[i] stores LIS ending at index i.

O(n log n) Approach: Use binary search + patience sorting.

function lengthOfLIS(nums) {
let sub = [];
for (let num of nums) {
let pos = binarySearch(sub, num);
if (pos === sub.length) sub.push(num);
else sub[pos] = num;
}
return sub.length;
}

function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}

Question 6

How do you solve the Edit Distance problem (Levenshtein Distance)?

Answer 6

function editDistance(word1, word2) {
let m = word1.length, n = word2.length;
let dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
        if (i === 0) dp[i][j] = j;
        else if (j === 0) dp[i][j] = i;
        else dp[i][j] = Math.min(
            dp[i - 1][j] + 1,  // Delete
            dp[i][j - 1] + 1,  // Insert
            dp[i - 1][j - 1] + (word1[i - 1] !== word2[j - 1] ? 1 : 0) // Replace
        );
    }
}
return dp[m][n]; }

Question 7

What are two ways to solve LRU cache?

Answer 7

doubly linked list
javascript map (preserves insertion order)