Meta Senior Software Engineer (E5) Interview Preparation Guide

#include <climits>

bool isPowerOfTwo(int n) {
    // Reject non-positive values (zero and negatives)
    if (n <= 0) return false;
    // True iff exactly one bit is set
    return (n & (n - 1)) == 0;
}

from collections import deque

def shortest_path_bfs(adj, src, dst):
    """
    adj: dict[node] -> list(neighbor nodes)  (adjacency list)
    src, dst: nodes (hashable)
    Returns: list of nodes from src to dst (inclusive) or [] if no path
    """
    if src == dst:
        return [src]

    q = deque([src])
    visited = {src}
    pred = {}  # predecessor map: node -> previous node on shortest path

    while q:
        u = q.popleft()
        for v in adj.get(u, []):
            if v not in visited:
                visited.add(v)
                pred[v] = u
                if v == dst:
                    # reconstruct path
                    path = [dst]
                    while path[-1] != src:
                        path.append(pred[path[-1]])
                    return path[::-1]
                q.append(v)
    return []  # no path

def levenshtein(a: str, b: str) -> int:
    # Ensure b is the shorter string to use O(min(m,n)) space
    if len(a) < len(b):
        a, b = b, a
    m, n = len(a), len(b)
    # prev and curr are length (n+1)
    prev = list(range(n + 1))
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        curr[0] = i
        ai = a[i - 1]
        for j in range(1, n + 1):
            cost = 0 if ai == b[j - 1] else 1
            # insert (curr[j-1]+1), delete (prev[j]+1), replace (prev[j-1]+cost)
            curr[j] = min(curr[j - 1] + 1, prev[j] + 1, prev[j - 1] + cost)
        prev, curr = curr, prev  # reuse arrays
    return prev[n]

def two_sum_sorted(nums, target):
    """
    nums: sorted list of ints
    returns: tuple (i, j) of 0-based indices where nums[i] + nums[j] == target,
             or (-1, -1) if no such pair exists.
    """
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (left, right)
        elif s < target:
            left += 1
        else:
            right -= 1
    return (-1, -1)

#include <bits/stdc++.h>
using namespace std;

struct XorBasis {
    static const int W = 64;
    int maxn; // max number of elements to track for reconstruction
    uint64_t basis[W];                 // basis vectors (values)
    vector<uint64_t> repr[W];          // bitmap repr: vector of 64-bit blocks, length = (maxn+63)/64

    XorBasis(int maxn_=0): maxn(maxn_) {
        for(int i=0;i<W;i++) basis[i]=0;
        if(maxn>0){
            int L = (maxn+63)/64;
            for(int i=0;i<W;i++) repr[i].assign(L,0);
        }
    }

    // insert value v, with index idx in [0..maxn-1] for reconstruction tracking
    void insert(uint64_t v, int idx=-1){
        vector<uint64_t> cur;
        if(maxn>0){
            cur.assign((maxn+63)/64,0);
            if(idx>=0) cur[idx/64] |= (1ULL<<(idx%64));
        }

        for(int b=W-1;b>=0;--b){
            if(!(v & (1ULL<<b))) continue;
            if(!basis[b]){
                basis[b]=v;
                if(maxn>0) repr[b]=cur;
                return;
            }
            // eliminate bit b
            v ^= basis[b];
            if(maxn>0){
                for(size_t i=0;i<repr[b].size();++i) cur[i] ^= repr[b][i];
            }
        }
        // if v==0: dependent; cur holds coefficients of original basis (can be stored if desired)
    }

    // get maximum XOR value achievable
    uint64_t getMaxXor(){
        uint64_t res=0;
        for(int b=W-1;b>=0;--b){
            if((res ^ basis[b]) > res) res ^= basis[b];
        }
        return res;
    }

    // get indices (0-based) of subset achieving maximum xor; returns vector<int>
    vector<int> getMaxXorSubset(){
        if(maxn==0) throw runtime_error("reconstruction not enabled (maxn==0)");
        vector<uint64_t> acc((maxn+63)/64,0);
        uint64_t res=0;
        for(int b=W-1;b>=0;--b){
            if((res ^ basis[b]) > res){
                res ^= basis[b];
                for(size_t i=0;i<acc.size();++i) acc[i] ^= repr[b][i];
            }
        }
        vector<int> out;
        for(int i=0;i<maxn;++i){
            if(acc[i/64] & (1ULL<<(i%64))) out.push_back(i);
        }
        return out;
    }
};

import heapq

class MedianStream:
    def __init__(self):
        self.lo = []  # max-heap via negatives
        self.hi = []  # min-heap

    def insert(self, x):
        # push into lo (max-heap) if appropriate
        if not self.lo or x <= -self.lo[0]:
            heapq.heappush(self.lo, -x)
        else:
            heapq.heappush(self.hi, x)

        # rebalance to maintain size invariant
        if len(self.lo) > len(self.hi) + 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        elif len(self.hi) > len(self.lo) + 1:
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def getMedian(self):
        if not self.lo and not self.hi:
            raise IndexError("no elements")
        if len(self.lo) == len(self.hi):
            return (-self.lo[0] + self.hi[0]) / 2.0
        elif len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        else:
            return float(self.hi[0])

def compute_lps(p):
    """Compute LPS array for pattern p."""
    m = len(p)
    lps = [0] * m
    length = 0  # length of previous longest prefix suffix
    i = 1
    while i < m:
        if p[i] == p[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]  # fallback
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    """Return list of start indices where pattern occurs in text."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    lps = compute_lps(pattern)
    res = []
    i = j = 0  # i -> text, j -> pattern
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                res.append(i - j)
                j = lps[j - 1]  # continue searching
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return res

import random

def rabin_karp(text, pattern, double_hash=True):
    if not pattern:
        return list(range(len(text)+1))
    n, m = len(text), len(pattern)
    if m > n:
        return []

    # choose base and moduli
    base = 257
    mod1 = 2**61 - 1  # large Mersenne-like prime using fast reduction
    mod2 = 10**9+7 if double_hash else None

    def modmul(a,b,mod):
        return (a*b) % mod

    # precompute base^(m-1)
    pow1 = pow(base, m-1, mod1)
    pow2 = pow(base, m-1, mod2) if double_hash else None

    # initial hashes
    h1 = 0
    h2 = 0
    for ch in pattern:
        h1 = (h1*base + ord(ch)) % mod1
        if double_hash:
            h2 = (h2*base + ord(ch)) % mod2

    t1 = 0
    t2 = 0
    for i in range(m):
        t1 = (t1*base + ord(text[i])) % mod1
        if double_hash:
            t2 = (t2*base + ord(text[i])) % mod2

    res = []
    def verify(i):
        return text[i:i+m] == pattern

    if (t1==h1 and (not double_hash or t2==h2)) and verify(0):
        res.append(0)

    for i in range(1, n-m+1):
        left = ord(text[i-1])
        right = ord(text[i+m-1])
        # roll t1
        t1 = (t1 - left*pow1) % mod1
        t1 = (t1*base + right) % mod1
        if double_hash:
            t2 = (t2 - left*pow2) % mod2
            t2 = (t2*base + right) % mod2

        if t1==h1 and (not double_hash or t2==h2):
            if verify(i):
                res.append(i)
    return res