DSA Interview Lab

Signals: counting · duplicates · most common

from collections import Counter
freq = Counter(nums)
answer = max(freq, key=freq.get)

Signals: group records · anagrams · buckets

from collections import defaultdict
groups = defaultdict(list)
for item in items:
    groups[key(item)].append(item)

Signals: stdin · multiple tests

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(a))

Signals: single pass · all items

for x in nums:
    use(x)

Signals: sorted search · divide by 2

while n > 1:
    n //= 2

Signals: all pairs · matrix relation

for i in range(n):
    for j in range(i + 1, n):
        check(i, j)

Signals: many range sums · cumulative

pref = [0]
for x in nums: pref.append(pref[-1] + x)
ans = pref[r+1] - pref[l]

Signals: maximum contiguous sum

cur = best = nums[0]
for x in nums[1:]:
    cur = max(x, cur + x)
    best = max(best, cur)

Signals: all-except-self · no division

out = [1] * n
p = 1
for i in range(n):
    out[i] = p; p *= nums[i]
s = 1
for i in range(n-1, -1, -1):
    out[i] *= s; s *= nums[i]

Signals: spiral · layers

top,left,bottom,right = 0,0,m-1,n-1
while top <= bottom and left <= right:
    # traverse top/right/bottom/left, then shrink

Signals: pair sum · lookup missing value

seen = {}
for i, x in enumerate(nums):
    if target - x in seen:
        return [seen[target-x], i]
    seen[x] = i

Signals: counts · anagram · top-k

from collections import Counter
freq = Counter(items)

Signals: subarray sum = k · count ranges

freq = {0:1}; p=ans=0
for x in nums:
    p += x
    ans += freq.get(p-k, 0)
    freq[p] = freq.get(p,0)+1

Signals: sorted pair · palindrome · container

l, r = 0, len(a)-1
while l < r:
    if need_bigger: l += 1
    else: r -= 1

Signals: in place · remove/keep · compact

w = 0
for r in range(len(a)):
    if keep(a[r]):
        a[w] = a[r]; w += 1

Signals: 3Sum · triplets

nums.sort()
for i in range(n-2):
    l, r = i+1, n-1
    while l < r: ...

Signals: exact k · moving average/sum

cur = sum(a[:k]); best = cur
for r in range(k, len(a)):
    cur += a[r] - a[r-k]
    best = max(best, cur)

Signals: longest substring/subarray under rule

l = 0
for r, x in enumerate(a):
    add(x)
    while invalid():
        remove(a[l]); l += 1
    best = max(best, r-l+1)

Signals: window max/min

dq = deque()
for i, x in enumerate(a):
    while dq and a[dq[-1]] <= x: dq.pop()
    dq.append(i)
    if dq[0] <= i-k: dq.popleft()

Signals: nested delimiters · matching

pairs = {')':'(',']':'[','}':'{'}
st=[]
for ch in s:
    if ch in pairs.values(): st.append(ch)
    elif not st or st.pop()!=pairs[ch]: return False

Signals: next greater/smaller · span

st=[]
for i,x in enumerate(a):
    while st and a[st[-1]] < x:
        j=st.pop(); answer[j]=i
    st.append(i)

Signals: largest rectangle · nearest smaller

st=[]
for i,h in enumerate(heights+[0]):
    while st and heights[st[-1]] > h:
        j=st.pop(); left=st[-1] if st else -1
        best=max(best, heights[j]*(i-left-1))
    st.append(i)

Signals: BFS · tasks · stream

from collections import deque
q=deque([start])
while q:
    node=q.popleft()
    for nei in graph[node]: ...

Signals: fixed capacity · wraparound

tail = (head + size) % cap
buf[tail] = value
size += 1

Signals: implement queue using stacks

if not out:
    while inp: out.append(inp.pop())
return out.pop()

Signals: head may change · merge/delete

dummy = ListNode(0, head)
prev = dummy
# mutate through prev.next
return dummy.next

Signals: middle · cycle · palindrome

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

Signals: nth from end

dummy=ListNode(0,head); fast=slow=dummy
for _ in range(n+1): fast=fast.next
while fast: fast=fast.next; slow=slow.next
slow.next=slow.next.next

Signals: halve input · exponentiation

def power(x,n):
    if n==0: return 1
    h=power(x,n//2)
    return h*h if n%2==0 else x*h*h

Signals: overlapping subproblems

from functools import cache
@cache
def f(state):
    if base(state): return base_value
    return combine(f(next_state))

Signals: avoid recursion depth

stack=[start]
while stack:
    state=stack.pop()
    # push children in reverse desired order

Signals: include/exclude · all subsets

def dfs(i):
    if i==n: out.append(path[:]); return
    path.append(a[i]); dfs(i+1); path.pop()
    dfs(i+1)

Signals: arrangements · use each once

def dfs():
    if len(path)==n: out.append(path[:]); return
    for x in nums:
        if x in used: continue
        used.add(x); path.append(x)
        dfs()
        path.pop(); used.remove(x)

Signals: target sum · sorted choices

for i in range(start,n):
    if i>start and a[i]==a[i-1]: continue
    if a[i] > remain: break
    path.append(a[i]); dfs(i+1, remain-a[i]); path.pop()

Signals: stable · divide and merge

def sort(a):
    if len(a)<=1: return a
    m=len(a)//2
    return merge(sort(a[:m]), sort(a[m:]))

Signals: pivot · in-place partition

pivot=a[hi]; i=lo
for j in range(lo,hi):
    if a[j] <= pivot:
        a[i],a[j]=a[j],a[i]; i+=1
a[i],a[hi]=a[hi],a[i]

Signals: kth element · partial sort

while lo <= hi:
    p=partition(a,lo,hi)
    if p==k:return a[p]
    if p<k:lo=p+1
    else:hi=p-1

Signals: sorted · find target

lo,hi=0,n-1
while lo<=hi:
    mid=(lo+hi)//2
    if a[mid]==x:return mid
    if a[mid]<x:lo=mid+1
    else:hi=mid-1

Signals: first >= x · first true

lo,hi=0,n
while lo<hi:
    mid=(lo+hi)//2
    if a[mid] < x: lo=mid+1
    else: hi=mid
return lo

Signals: minimum feasible · maximum possible

lo,hi=min_answer,max_answer
while lo<hi:
    mid=(lo+hi)//2
    if feasible(mid): hi=mid
    else: lo=mid+1
return lo

Signals: height · balance · diameter

def dfs(node):
    if not node:return 0
    L=dfs(node.left); R=dfs(node.right)
    update_answer(L,R,node)
    return 1+max(L,R)

Signals: levels · shortest edges · right view

q=deque([root])
while q:
    for _ in range(len(q)):
        node=q.popleft()
        if node.left:q.append(node.left)
        if node.right:q.append(node.right)

Signals: BST sorted order · avoid recursion

st=[]; cur=root
while cur or st:
    while cur: st.append(cur); cur=cur.left
    cur=st.pop(); visit(cur); cur=cur.right

Signals: ordered comparisons

cur=root
while cur:
    if x==cur.val: return cur
    cur = cur.left if x<cur.val else cur.right

Signals: global BST property

def dfs(node,lo,hi):
    if not node:return True
    if not lo < node.val < hi:return False
    return dfs(node.left,lo,node.val) and dfs(node.right,node.val,hi)

Signals: kth smallest

st=[];cur=root
while True:
    while cur:st.append(cur);cur=cur.left
    cur=st.pop(); k-=1
    if k==0:return cur.val
    cur=cur.right

Signals: kth largest · k closest

h=[]
for x in items:
    heapq.heappush(h, score(x))
    if len(h)>k: heapq.heappop(h)

Signals: merge sorted sources

h=[]
for source in sources:
    push_first(source)
while h:
    value, sid, pos = heapq.heappop(h)
    output(value); push_next(sid,pos)

Signals: stream median

# low = negatives (max-heap), high = min-heap
# rebalance so len(low) >= len(high) and diff <= 1

Signals: shortest unweighted · layers · components

for start in graph:
    if start in seen: continue
    q=deque([start]); seen.add(start)
    while q:
        u=q.popleft()
        for v in graph[u]:
            if v not in seen: seen.add(v); q.append(v)

Signals: prerequisites · DAG order

q=deque(v for v in nodes if indeg[v]==0)
order=[]
while q:
    u=q.popleft(); order.append(u)
    for v in g[u]:
        indeg[v]-=1
        if indeg[v]==0:q.append(v)

Signals: dynamic connectivity · redundant edge

def find(x):
    if parent[x]!=x: parent[x]=find(parent[x])
    return parent[x]
def union(a,b):
    ra,rb=find(a),find(b)
    if ra==rb:return False
    # attach smaller rank/size under larger

Signals: non-negative weights · shortest path

pq=[(0,src)]; dist={src:0}
while pq:
    d,u=heappop(pq)
    if d!=dist[u]:continue
    for v,w in g[u]:
        if d+w < dist.get(v,INF):
            dist[v]=d+w; heappush(pq,(d+w,v))

Signals: negative edges · bounded stops

dist=[INF]*n;dist[src]=0
for _ in range(n-1):
    nxt=dist.copy()
    for u,v,w in edges:
        nxt[v]=min(nxt[v], dist[u]+w)
    dist=nxt

Signals: minimum total connection · undirected

for w,u,v in sorted(edges):
    if union(u,v):
        cost += w
        used += 1

Signals: interval scheduling · removals

intervals.sort(key=lambda x:x[1])
end=-INF
for s,e in intervals:
    if s>=end:
        keep(); end=e

Signals: jump game · coverage

far=0
for i,jump in enumerate(nums):
    if i>far:return False
    far=max(far,i+jump)
return True

Signals: circular route · net gain

if sum(gas)<sum(cost):return -1
start=tank=0
for i in range(n):
    tank += gas[i]-cost[i]
    if tank<0:start=i+1;tank=0
return start

Signals: recursive recurrence · sparse states

from functools import cache
@cache
def dp(state):
    if base(state): return base_value
    return best(dp(next_state) + cost for next_state in moves(state))

Signals: stairs · robber

prev2,prev1=base0,base1
for i in range(2,n+1):
    cur=transition(prev2,prev1)
    prev2,prev1=prev1,cur

Signals: choose each item once

dp=[0]*(cap+1)
for w,val in items:
    for c in range(cap,w-1,-1):
        dp[c]=max(dp[c],dp[c-w]+val)

Signals: LCS · edit distance

dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        dp[i][j]=transition(...)

Signals: dictionary words · prefixes

node=root
for ch in word:
    if ch not in node.children:return False
    node=node.children[ch]
return node.is_end

Signals: suggestions · prefix query

node=walk(prefix)
# DFS descendants, append when is_end, stop after k

Signals: pattern with dot wildcard

def dfs(i,node):
    if i==len(word): return node.is_end
    if word[i]=='.': return any(dfs(i+1,c) for c in node.children.values())
    return word[i] in node.children and dfs(i+1,node.children[word[i]])

Signals: single odd-occurring value

ans=0
for x in nums: ans ^= x
return ans

Signals: popcount · bit iteration

count=0
while x:
    x &= x-1
    count += 1

Signals: all primes up to n

prime=[True]*(n+1)
prime[:2]=[False,False]
for p in range(2,int(n**0.5)+1):
    if prime[p]:
        for m in range(p*p,n+1,p): prime[m]=False

Signals: live coding · think aloud

clarify()
brute_force()
state_complexity()
optimize_by_pattern()
code_cleanly()
dry_run()
test_edges()
state_final_complexity()

Signals: repeat mistakes deliberately

log = {
 "signal_missed": "contiguous + longest",
 "bug": "used if instead of while when shrinking",
 "fix": "state window invariant first"
}

Signals: maximize correct submissions

# 1 scan all
# 2 solve easiest complete tasks
# 3 optimize by constraints
# 4 reserve test/review time