Coding Interview Patterns and Meta Strategies Questions

import numpy as np
from collections import deque

def largest_component_bbox(mask):
    """
    mask: 2D numpy array of dtype bool or {0,1}
    returns: (min_row, min_col, max_row, max_col) of largest 4-connected component, or None if none
    """
    if mask.dtype != bool:
        mask = mask.astype(bool)
    h, w = mask.shape
    visited = np.zeros_like(mask, dtype=bool)
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    best_area = 0
    best_bbox = None

    for r in range(h):
        for c in range(w):
            if mask[r, c] and not visited[r, c]:
                q = deque()
                q.append((r,c))
                visited[r, c] = True
                min_r = max_r = r
                min_c = max_c = c
                area = 0
                while q:
                    y,x = q.popleft()
                    area += 1
                    if y < min_r: min_r = y
                    if y > max_r: max_r = y
                    if x < min_c: min_c = x
                    if x > max_c: max_c = x
                    for dy,dx in dirs:
                        ny, nx = y+dy, x+dx
                        if 0 <= ny < h and 0 <= nx < w and mask[ny, nx] and not visited[ny, nx]:
                            visited[ny, nx] = True
                            q.append((ny,nx))
                if area > best_area:
                    best_area = area
                    best_bbox = (min_r, min_c, max_r, max_c)
    return best_bbox

from collections import Counter, defaultdict

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
    need = Counter(t)           # required counts
    have = defaultdict(int)     # current window counts
    required = len(need)        # number of distinct chars we must satisfy
    formed = 0                  # how many distinct chars currently satisfied
    l = 0
    best = (float('inf'), None, None)  # (length, left, right)
    
    for r, ch in enumerate(s):
        have[ch] += 1
        if ch in need and have[ch] == need[ch]:
            formed += 1
        
        while l <= r and formed == required:
            # update answer
            if (r - l + 1) < best[0]:
                best = (r - l + 1, l, r)
            # pop left
            have[s[l]] -= 1
            if s[l] in need and have[s[l]] < need[s[l]]:
                formed -= 1
            l += 1

    return "" if best[0] == float('inf') else s[best[1]:best[2]+1]

import heapq
from typing import List, Tuple

def k_smallest_pairs(A: List[int], B: List[int], k: int) -> List[Tuple[int,int]]:
    """
    Return k pairs (a,b) with smallest sums from sorted arrays A and B.
    Time: O(k log min(m,k)), Space: O(min(m,k))
    """
    if not A or not B or k <= 0:
        return []
    m, n = len(A), len(B)
    res = []
    heap = []
    # Only need first min(m, k) rows (each row corresponds to fixed i and varying j)
    for i in range(min(m, k)):
        heapq.heappush(heap, (A[i] + B[0], i, 0))  # (sum, i, j)

    while heap and len(res) < k:
        s, i, j = heapq.heappop(heap)
        res.append((A[i], B[j]))
        # push next in the same row (i, j+1) if available
        if j + 1 < n:
            heapq.heappush(heap, (A[i] + B[j+1], i, j+1))

    return res