DSA and Coding Interview Patterns Interview Questions and Answers

def longest_unique(s):
    seen, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1      # shrink past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

# House Robber — the canonical 1D DP
def rob(nums):
    prev2, prev1 = 0, 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1

from collections import deque
def shortest_path(grid, start, goal):
    q, seen = deque([(start, 0)]), {start}
    while q:
        (r, c), d = q.popleft()
        if (r, c) == goal: return d
        for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) \
               and grid[nr][nc] != "#" and (nr, nc) not in seen:
                seen.add((nr, nc)); q.append(((nr, nc), d + 1))
    return -1

def diameter(root):
    best = 0
    def depth(node):                 # postorder: children first
        nonlocal best
        if not node: return 0
        l, r = depth(node.left), depth(node.right)
        best = max(best, l + r)      # path through this node
        return 1 + max(l, r)         # what the parent needs
    depth(root)
    return best

def single_number(nums):
    out = 0
    for n in nums: out ^= n   # pairs cancel, the loner survives
    return out

import heapq
def k_largest(nums, k):
    h = []
    for n in nums:
        heapq.heappush(h, n)
        if len(h) > k: heapq.heappop(h)   # keep only the k biggest
    return h[0]

def subsets(nums):
    out, path = [], []
    def bt(i):
        if i == len(nums):
            out.append(path[:])      # COPY, or every row aliases path
            return
        bt(i + 1)                    # skip nums[i]
        path.append(nums[i]); bt(i + 1); path.pop()
    bt(0)
    return out