Quick Interview Notes

# Sliding window — max sum subarray of size k
def max_sum(arr, k):
    win = sum(arr[:k])
    best = win
    for i in range(k, len(arr)):
        win += arr[i] - arr[i-k]
        best = max(best, win)
    return best

# Valid anagram — O(n)
from collections import Counter
def is_anagram(s, t):
    return Counter(s) == Counter(t)

# Expand around center — longest palindrome
def longest_palindrome(s):
    res = ""
    for i in range(len(s)):
        for l, r in [(i, i), (i, i+1)]:
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l + 1 > len(res):
                    res = s[l:r+1]
                l -= 1; r += 1
    return res

# Level-order traversal
from collections import deque
def level_order(root):
    if not root: return []
    result, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)
    return result

# BFS shortest path
from collections import deque
def bfs(graph, src, dst):
    q = deque([(src, [src])])
    visited = {src}
    while q:
        node, path = q.popleft()
        if node == dst: return path
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append((nb, path + [nb]))
    return []

# Coin change — bottom up O(n*amount)
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if a >= c:
                dp[a] = min(dp[a], dp[a-c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

import heapq

# Top K frequent elements
from collections import Counter
def top_k(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count, key=count.get)

# Median of stream
class MedianFinder:
    def __init__(self):
        self.lo, self.hi = [], []  # max-heap, min-heap
    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
    def findMedian(self):
        if len(self.lo) > len(self.hi): return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

# Classic binary search
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target: return mid
        elif nums[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

# Binary search on answer — min days to make bouquets
def min_days(bloomDay, m, k):
    def can_make(d):
        bouquets = flowers = 0
        for b in bloomDay:
            if b <= d: flowers += 1
            else: flowers = 0
            if flowers == k: bouquets += 1; flowers = 0
        return bouquets >= m
    lo, hi = min(bloomDay), max(bloomDay)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_make(mid): hi = mid
        else: lo = mid + 1
    return lo

# Subsets — O(2^n)
def subsets(nums):
    result = []
    def bt(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1, path)
            path.pop()
    bt(0, [])
    return result

# Permutations
def permute(nums):
    result = []
    def bt(path, remaining):
        if not remaining:
            result.append(path)
            return
        for i, n in enumerate(remaining):
            bt(path + [n], remaining[:i] + remaining[i+1:])
    bt([], nums)
    return result

# Reverse linked list — iterative
def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

# Find middle — slow/fast
def find_mid(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow