50 Essential Python Coding Interview Questions — Ready

Guide
Prepared for: Candidates with ~2 years experience. Includes company tags (common), difficulty, explanation,
Python solution, example test cases, time & space complexity.

1. Two Sum — [Amazon/Google] (Easy)

Given an array nums and target, return indices of two numbers adding to target.

Idea: Use hashmap to store complements.

Example Input Expected Output
nums=[2,7,11,15], target=9 [0,1]
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
rem = target -
num
if rem in seen:
return [seen[rem], i]
seen[num] = i
# Time: O(n),
Space: O(n)

2. Reverse Linked List — [Microsoft] (Easy)

Reverse a singly linked list and return new head.

Idea: Iterative two-pointer reverse.

Example Input Expected Output
1->2->3->None 3->2->1->None
class ListNode:
def __init__(self, val=0,next=None):
self.val=val; self.next=next
def
reverse_list(head):
prev=None; curr=head
while curr:
nxt=curr.next
curr.next=prev
prev=curr
curr=nxt
return prev
# Time: O(n), Space: O(1)

3. Merge Intervals — [Google] (Medium)

Given intervals, merge overlapping ones.

Idea: Sort by start, merge greedily.

Example Input Expected Output
[[1,3],[2,6],[8,10]] [[1,6],[8,10]]
def merge_intervals(intervals):
if not intervals: return []
intervals.sort(key=lambda x:
x[0])
res=[intervals[0]]
for s,e in intervals[1:]:
if s<=res[-1][1]:
res[-1][1]=max(res[-1][1], e)
else:
res.append([s,e])
return res
# Time: O(n
log n), Space: O(n)

4. Valid Parentheses — [Amazon] (Easy)

Check if parentheses string is valid.

Idea: Use stack and map pairs.

Example Input Expected Output
s='()[]{}' True
def is_valid(s):
stack=[]
pairs={')':'(',']':'[','}':'{'}
for ch in s:
if ch in
pairs:
if not stack or stack.pop()!=pairs[ch]:
return False
else:
stack.append(ch)
return not stack
# Time: O(n), Space: O(n)

5. Kth Largest Element (Quickselect) — [Google] (Medium)

Return k-th largest element in list.

Idea: Quickselect (average O(n)).

Example Input Expected Output
nums=[3,2,1,5,6,4], k=2 5
import random
def kth_largest(nums, k):
k = len(nums)-k
def partition(l,r):
pivot =
nums[r]; i=l
for j in range(l,r):
if nums[j]<=pivot:
nums[i],nums[j]=nums[j],nums[i]; i+=1
nums[i],nums[r]=nums[r],nums[i]; return i
l,r=0,len(nums)-1
while True:
p=partition(l,r)
if p==k: return nums[p]
if p<k: l=p+1
else: r=p-1
# Avg Time: O(n), Space: O(1)

6. Longest Substring Without Repeating Characters — [Amazon] (Medium)

Return length of longest substring without repeating chars.

Idea: Sliding window with last-seen indices.

Example Input Expected Output
s='abcabcbb' 3
def length_of_longest_substring(s):
last={}; start=0; maxlen=0
for i,ch in enumerate(s):
if ch in last and last[ch]>=start:
start=last[ch]+1
last[ch]=i
maxlen=max(maxlen, i-start+1)
return maxlen
# Time: O(n), Space: O(min(n,charset))

7. Inorder Traversal (Iterative) — [Microsoft] (Easy)

Return inorder traversal of binary tree.

Idea: Use stack to simulate recursion.

Example Input Expected Output
root=[1,null,2,3] [1,3,2]
def inorder_traversal(root):
res=[]; stack=[]; curr=root
while curr or stack:
while
curr:
stack.append(curr); curr=curr.left
curr=stack.pop(); res.append(curr.val);
curr=curr.right
return res
# Time: O(n), Space: O(h)

8. Lowest Common Ancestor of Binary Tree — [Google] (Medium)

Find LCA of two nodes in binary tree.

Idea: Post-order recursion returns node when split found.

Example Input Expected Output
tree, p=5,q=1 3
def lca(root,p,q):
if not root or root==p or root==q: return root
left=lca(root.left,p,q);
right=lca(root.right,p,q)
if left and right: return root
return left or right
# Time: O(n),
Space: O(h)
9. Serialize and Deserialize Binary Tree — [Facebook/Meta] (Hard)

Encode/decode binary tree to string and back.

Idea: Preorder with null markers.

Example Input Expected Output
serialize/deserialize roundtrip works
def serialize(root):
vals=[]
def dfs(node):
if not node:
vals.append('#'); return
vals.append(str(node.val)); dfs(node.left); dfs(node.right)
dfs(root); return ' '.join(vals)
def deserialize(data):
vals=iter(data.split())
def dfs():
val=next(vals)
if val=='#': return None
node=TreeNode(int(val)); node.left=dfs();
node.right=dfs(); return node
return dfs()
# Time: O(n), Space: O(n)

10. Climbing Stairs — [Easy/Leetcode] (Easy)

Number of ways to climb n stairs taking 1 or 2 steps.

Idea: Fibonacci DP iterative.

Example Input Expected Output
n=3 3
def climb_stairs(n):
if n<=1: return 1
a,b=1,1
for _ in range(2,n+1):
a,b=b,a+b
return b
# Time: O(n), Space: O(1)

11. Coin Change (Min Coins) — [Amazon] (Medium)

Fewest coins to make amount or -1.

Idea: DP over amounts.

Example Input Expected Output
coins=[1,2,5], amount=11 3
def coin_change(coins, amount):
dp=[float('inf')]*(amount+1); dp[0]=0
for i in
range(1,amount+1):
for c in coins:
if c<=i: dp[i]=min(dp[i], dp[i-c]+1)
return dp[amount] if dp[amount]!=float('inf') else -1
# Time: O(amount*len(coins)), Space: O(amount)
12. Word Break — [Google] (Medium)

Check if s can be segmented into words from dict.

Idea: DP boolean array over prefixes.

Example Input Expected Output
s='leetcode', dict=['leet','code'] True
def word_break(s, wordDict):
wordSet=set(wordDict); n=len(s); dp=[False]*(n+1); dp[0]=True
for i in range(1,n+1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i]=True; break
return dp[-1]
# Time: O(n^2*L), Space: O(n)

13. Search in Rotated Sorted Array — [Google] (Medium)

Search target in rotated sorted array in O(log n).

Idea: Binary search with rotated-check.

Example Input Expected Output
nums=[4,5,6,7,0,1,2], target=0 4
def search_rotated(nums, target):
l,r=0,len(nums)-1
while l<=r:
m=(l+r)//2
if nums[m]==target: return m
if nums[l]<=nums[m]:
if nums[l]<=target<nums[m]:
r=m-1
else: l=m+1
else:
if nums[m]<target<=nums[r]: l=m+1
else: r=m-1
return -1
# Time: O(log n), Space: O(1)

14. Median of Two Sorted Arrays (outline) — [Google] (Hard)

Find median of two sorted arrays in O(log(min(m,n))).

Idea: Binary search partition on smaller array.

Example Input Expected Output
a=[1,3], b=[2] 2.0
def find_median_sorted_arrays(a,b):
if len(a)>len(b): a,b=b,a
m,n=len(a),len(b);
imin,imax,half=0,m,(m+n+1)//2
while imin<=imax:
i=(imin+imax)//2; j=half-i
if
i<m and b[j-1]>a[i]: imin=i+1
elif i>0 and a[i-1]>b[j]: imax=i-1
else:
if i==0: left=b[j-1]
elif j==0: left=a[i-1]
else: left=max(a[i-1],b[j-1])
if (m+n)%2==1: return left
if i==m: right=b[j]
elif j==n: right=a[i]
else: right=min(a[i],b[j])
return (left+right)/2
# Time: O(log(min(m,n)))

15. Container With Most Water — [Amazon] (Medium)

Given heights, find max area between two lines.

Idea: Two pointers moving shorter side inward.

Example Input Expected Output
height=[1,8,6,2,5,4,8,3,7] 49
def max_area(height):
l,r=0,len(height)-1; ans=0
while l<r:
ans=max(ans,(r-l)*min(height[l],height[r]))
if height[l]<height[r]: l+=1
else: r-=1
return ans
# Time: O(n), Space: O(1)

16. Permutations — [Google] (Medium)

Return all permutations of nums.

Idea: Backtracking with used marker.

Example Input Expected Output
nums=[1,2,3] [[1,2,3],[1,3,2],...]
def permute(nums):
res=[]
def backtrack(path, used):
if len(path)==len(nums):
res.append(path[:]); return
for i,n in enumerate(nums):
if used[i]: continue
used[i]=True; path.append(n)
backtrack(path, used)
path.pop(); used[i]=False
backtrack([], [False]*len(nums)); return res
# Time: O(n*n!), Space: O(n)

17. Subsets (Power Set) — [Microsoft] (Easy)

Return all subsets of nums.

Idea: Iterative build or backtrack.

Example Input Expected Output
nums=[1,2] [[],[1],[2],[1,2]]
def subsets(nums):
res=[[]]
for n in nums:
res += [curr+[n] for curr in res]
return res
# Time: O(n*2^n), Space: O(2^n)

18. LRU Cache — [Amazon] (Medium)

Implement LRU cache with O(1) get/put.

Idea: OrderedDict or doubly-linked list + hashmap.

Example Input Expected Output
ops: put(1,1), put(2,2), get(1) 1
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache=OrderedDict(); self.cap=capacity
def get(self,key):
if key not in self.cache:
return -1
val=self.cache.pop(key); self.cache[key]=val; return val
def
put(self,key,value):
if key in self.cache: self.cache.pop(key)
elif
len(self.cache)==self.cap: self.cache.popitem(last=False)
self.cache[key]=value
# Time: O(1)
amortized, Space: O(capacity)

19. Top K Frequent Elements — [Google] (Medium)

Return k most frequent elements in array.

Idea: Counter most_common or heap.

Example Input Expected Output
nums=[1,1,1,2,2,3], k=2 [1,2]
from collections import Counter
def top_k_frequent(nums,k):
cnt=Counter(nums)
return [item
for item,_ in cnt.most_common(k)]
# Time: O(n log k) or O(n), Space: O(n)

20. Sort Colors (Dutch Flag) — [Microsoft] (Medium)

Sort array containing 0,1,2 in-place.

Idea: Three-way partition pointers.

Example Input Expected Output
nums=[2,0,2,1,1,0] [0,0,1,1,2,2]
def sort_colors(nums):
low,mid,high=0,0,len(nums)-1
while mid<=high:
if
nums[mid]==0:
nums[low],nums[mid]=nums[mid],nums[low]; low+=1; mid+=1
elif
nums[mid]==1: mid+=1
else:
nums[mid],nums[high]=nums[high],nums[mid]; high-=1
#
Time: O(n), Space: O(1)

21. Product of Array Except Self — [Amazon] (Medium)

Return product of array except self without division.

Idea: Prefix and suffix products.

Example Input Expected Output
nums=[1,2,3,4] [24,12,8,6]
def product_except_self(nums):
n=len(nums); res=[1]*n
pref=1
for i in range(n):
res[i]=pref; pref*=nums[i]
suff=1
for i in range(n-1,-1,-1):
res[i]*=suff;
suff*=nums[i]
return res
# Time: O(n), Space: O(1) extra

22. Minimum Window Substring — [Amazon] (Hard)

Find min window in s containing all chars of t.

Idea: Sliding window with need counter and missing count.

Example Input Expected Output
s='ADOBECODEBANC', t='ABC' 'BANC'
from collections import Counter
def min_window(s,t):
need=Counter(t); missing=len(t); left=0;
start=0; min_len=float('inf')
for right,ch in enumerate(s):
if need[ch]>0: missing-=1
need[ch]-=1
while missing==0:
if right-left+1<min_len: start=left;
min_len=right-left+1
need[s[left]]+=1
if need[s[left]]>0: missing+=1
left+=1
return '' if min_len==float('inf') else s[start:start+min_len]
# Time: O(n), Space:
O(charset)

23. Number of Islands — [Microsoft] (Medium)

Count islands of '1's in grid.

Idea: DFS/BFS to mark visited.
Example Input Expected Output
grid=[[1,1,0],[0,1,0]] 1
def num_islands(grid):
if not grid: return 0
rows,cols=len(grid),len(grid[0])
def
dfs(r,c):
if r<0 or c<0 or r>=rows or c>=cols or grid[r][c]=='0': return
grid[r][c]='0'
for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
dfs(r+dr,c+dc)
count=0
for r in range(rows):
for c in range(cols):
if grid[r][c]=='1':
count+=1; dfs(r,c)
return count
# Time: O(rows*cols), Space: O(rows*cols) recursion

24. Merge K Sorted Lists — [Google] (Hard)

Merge k sorted linked lists into one sorted list.

Idea: Use heap of current nodes.

Example Input Expected Output
lists=[[1,4,5],[1,3,4],[2,6]] [1,1,2,3,4,4,5,6]
import heapq
def merge_k_lists(lists):
heap=[]; counter=0
for node in lists:
if
node: heapq.heappush(heap, (node.val, counter, node)); counter+=1
head=tail=ListNode(0)
while heap:
val,_,node=heapq.heappop(heap)
tail.next=ListNode(val); tail=tail.next
node=node.next
if node: heapq.heappush(heap, (node.val, counter, node)); counter+=1
return head.next
# Time: O(N log k), Space: O(k)

25. Decode Ways — [Google] (Medium)

Count decodings of digit string where '1'->A... '26'->Z.

Idea: DP with two previous states.

Example Input Expected Output
s='12' 2
def num_decodings(s):
if not s or s[0]=='0': return 0
n=len(s); dp=[0]*(n+1); dp[0]=1;
dp[1]=1
for i in range(2,n+1):
if s[i-1]!='0': dp[i]+=dp[i-1]
two=int(s[i-2:i])
if 10<=two<=26: dp[i]+=dp[i-2]
return dp[n]
# Time: O(n), Space: O(n)

26. Find Peak Element — [Microsoft] (Medium)

Return index of a peak element where nums[i]>nums[i+1].

Idea: Binary search on slopes.

Example Input Expected Output
nums=[1,2,3,1] 2
def find_peak(nums):
l,r=0,len(nums)-1
while l<r:
m=(l+r)//2
if
nums[m]>nums[m+1]: r=m
else: l=m+1
return l
# Time: O(log n), Space: O(1)

27. K Closest Points to Origin — [Google] (Medium)

Return k points closest to origin.

Idea: Use heap or quickselect.

Example Input Expected Output
points=[[1,3],[-2,2]], k=1 [[-2,2]]
import heapq, random, math
def k_closest(points,k):
return sorted(points, key=lambda p:
p[0]*p[0]+p[1]*p[1])[:k]
# Time: O(n log n) or O(n) via quickselect

28. Search a 2D Matrix — [Amazon] (Medium)

Matrix rows sorted, first element of each row > last of previous. Search target.

Idea: Binary search treating as flattened array.

Example Input Expected Output
matrix=[[1,3,5]], target=3 True
def search_matrix(matrix,target):
if not matrix or not matrix[0]: return False
m,n=len(matrix),len(matrix[0])
l,r=0,m*n-1
while l<=r:
mid=(l+r)//2
val=matrix[mid//n][mid%n]
if val==target: return True
if val<target: l=mid+1
else: r=mid-1
return False
# Time: O(log(mn)), Space: O(1)
29. Course Schedule (Topological Sort) — [Amazon] (Medium)

Given numCourses and prerequisites, can finish all courses?

Idea: Use Kahn's algorithm (BFS) or DFS cycle detection.

Example Input Expected Output
numCourses=2, prerequisites=[[1,0]] True
from collections import deque
def can_finish(numCourses, prerequisites):
g=[[] for _ in
range(numCourses)]; indeg=[0]*numCourses
for u,v in prerequisites: g[v].append(u); indeg[u]+=1
q=deque([i for i in range(numCourses) if indeg[i]==0])
seen=0
while q:
node=q.popleft(); seen+=1
for nei in g[node]:
indeg[nei]-=1
if
indeg[nei]==0: q.append(nei)
return seen==numCourses
# Time: O(V+E), Space: O(V+E)

30. Word Ladder (BFS) — [Google] (Hard)

Shortest transformation from beginWord to endWord changing one letter at a time with dictionary.

Idea: BFS on word graph using wildcard neighbors.

Example Input Expected Output
begin='hit', end='cog', wordList=['hot','dot','dog','lot','log','cog']
5
from collections import deque, defaultdict
def ladder_length(begin, end, wordList):
wordSet=set(wordList)
if end not in wordSet: return 0
N=len(begin)
all_combo=defaultdict(list)
for word in wordSet:
for i in range(N):
all_combo[word[:i]+'*'+word[i+1:]].append(word)
q=deque([(begin,1)]); visited={begin}
while
q:
word,level=q.popleft()
for i in range(N):
pattern=word[:i]+'*'+word[i+1:]
for nei in all_combo.get(pattern,[]):
if
nei==end: return level+1
if nei not in visited:
visited.add(nei); q.append((nei,level+1))
all_combo[pattern]=[]
return 0
# Time:
approx O(M*N*26), Space: O(M*N)

31. Valid Sudoku — [Microsoft] (Medium)

Check if 9x9 board is valid according to Sudoku rules.

Idea: Use sets for rows, cols, boxes.
Example Input Expected Output
valid board True
def is_valid_sudoku(board):
rows=[set() for _ in range(9)]; cols=[set() for _ in range(9)];
boxes=[set() for _ in range(9)]
for r in range(9):
for c in range(9):
val=board[r][c]
if val=='.': continue
if val in rows[r] or val in cols[c] or
val in boxes[(r//3)*3+c//3]: return False
rows[r].add(val); cols[c].add(val);
boxes[(r//3)*3+c//3].add(val)
return True
# Time: O(81), Space: O(81)

32. Binary Tree Level Order Traversal — [Amazon] (Easy)

Return level order values of binary tree.

Idea: BFS with queue.

Example Input Expected Output
tree [[3],[9,20],[15,7]]
from collections import deque
def level_order(root):
if not root: return []
res=[];
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)
res.append(level)
return res
# Time: O(n), Space: O(n)

33. Find First and Last Position of Element in Sorted Array — [Google]
(Medium)

Find starting and ending position of target in sorted array.

Idea: Two binary searches for left and right bounds.

Example Input Expected Output
nums=[5,7,7,8,8,10], target=8 [3,4]
def search_range(nums,target):
def find_bound(left):
l,r=0,len(nums)-1; ans=-1
while l<=r:
m=(l+r)//2
if nums[m]==target: ans=m; (r if left else l)=(m-1 if
left else m+1) # placeholder
if nums[m]<target: l=m+1
else: r=m-1
return ans
# Simpler: use bisect
import bisect
l=bisect.bisect_left(nums,target)
if
l==len(nums) or nums[l]!=target: return [-1,-1]
r=bisect.bisect_right(nums,target)-1
return
[l,r]
# Time: O(log n), Space: O(1)

34. Evaluate Reverse Polish Notation — [Amazon] (Medium)

Evaluate RPN expression tokens.

Idea: Stack evaluate operators.

Example Input Expected Output
tokens=['2','1','+','3','*'] 9
def eval_rpn(tokens):
stack=[]
ops={'+':lambda a,b:a+b,'-':lambda a,b:a-b,'*':lambda
a,b:a*b,'/':lambda a,b:int(a/b)}
for t in tokens:
if t in ops:
b=stack.pop(); a=stack.pop(); stack.append(ops[t](a,b))
else: stack.append(int(t))
return stack[-1]
# Time: O(n), Space: O(n)

35. Spiral Matrix — [Google] (Medium)

Return all elements of matrix in spiral order.

Idea: Maintain boundaries and traverse in four directions.

Example Input Expected Output
matrix=[[1,2,3],[4,5,6],[7,8,9]] [1,2,3,6,9,8,7,4,5]
def spiral_order(matrix):
if not matrix: return []
res=[]; top,bot, left, right = 0,
len(matrix)-1, 0, len(matrix[0])-1
while left<=right and top<=bot:
for c in
range(left,right+1): res.append(matrix[top][c])
top+=1
for r in range(top,bot+1):
res.append(matrix[r][right])
right-=1
if top<=bot:
for c in
range(right,left-1,-1): res.append(matrix[bot][c])
bot-=1
if left<=right:
for r in range(bot,top-1,-1): res.append(matrix[r][left])
left+=1
return res
# Time:
O(mn), Space: O(1)
36. Rotate Image — [Microsoft] (Medium)

Rotate NxN matrix by 90 degrees clockwise in-place.

Idea: Transpose + reverse each row.

Example Input Expected Output
matrix=[[1,2,3],[4,5,6],[7,8,9]] [[7,4,1],[8,5,2],[9,6,3]]
def rotate(matrix):
n=len(matrix)
for i in range(n):
for j in range(i,n):
matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
for row in matrix: row.reverse()
# Time:
O(n^2), Space: O(1)

37. Flatten Nested List Iterator (design) — [Google] (Medium)

Design iterator to flatten nested lists of integers.

Idea: Use stack of iterators to lazily flatten.

Example Input Expected Output
nestedList = [[1,1],2,[1,1]] iterator yields 1,1,2,1,1
class NestedIterator:
def __init__(self, nestedList):
self.stack = [iter(nestedList)]
def next(self):
return self._next_val
def hasNext(self):
while self.stack:
try:
x = next(self.stack[-1])
except StopIteration:
self.stack.pop(); continue
if isinstance(x, int):
self._next_val = x;
return True
else:
self.stack.append(iter(x))
return False
#
Time: amortized O(1) per op

38. Serialize-Deserialize N-ary Tree — [Facebook/Meta] (Hard)

Serialize and deserialize N-ary tree.

Idea: Use markers for children counts or parentheses-style encoding.

Example Input Expected Output
roundtrip works
def serialize(root):
vals=[]
def dfs(node):
if not node: return
vals.append(str(node.val)); vals.append(str(len(node.children)))
for c in node.children:
dfs(c)
dfs(root); return ' '.join(vals)
def deserialize(data):
vals=iter(data.split())
def dfs():
try: val=next(vals)
except StopIteration: return None
node=Node(int(val)); k=int(next(vals))
node.children=[dfs() for _ in range(k)]; return node
return dfs()
# Time: O(n), Space: O(n)

39. Design Twitter (mini) — Post/Follow/NewsFeed — [Twitter-like]

(Medium)

Design post, follow, getNewsFeed returning 10 most recent posts from user and followees.

Idea: Use timestamp and heap merging of recent lists.

Example Input Expected Output
basic ops works
import heapq, itertools
class Twitter:
def __init__(self):
self.time=0; self.tweets={};
self.followees={}
def post(self,userId,tweetId):
self.time+=1;
self.tweets.setdefault(userId,[]).append((self.time,tweetId))
def
follow(self,follower,followee):
self.followees.setdefault(follower,set()).add(followee)
def unfollow(self,follower,followee):
self.followees.get(follower,set()).discard(followee)
def getNewsFeed(self,userId):
h=[]; users={userId} | self.followees.get(userId, set())
for u in users:
for t in self.tweets.get(u,[])[-10:]:
heapq.heappush(h,
t)
if len(h)>10: heapq.heappop(h)
return [tid for _,tid in sorted(h,
reverse=True)]
# Time: depends on number of users and tweets considered

40. Find Median from Data Stream — [Google] (Hard)

Support addNum and findMedian efficiently.

Idea: Two heaps (max-heap left, min-heap right).

Example Input Expected Output
stream 1,2,3 median 2
import heapq
class MedianFinder:
def __init__(self):
self.small=[]; self.large=[]
def addNum(self,num):
heapq.heappush(self.small, -num)
if self.small and self.large
and -self.small[0]>self.large[0]:
val=-heapq.heappop(self.small);
heapq.heappush(self.large,val)
if len(self.small)>len(self.large)+1:
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large)>len(self.small)+1:
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self):
if
len(self.small)==len(self.large): return (-self.small[0]+self.large[0])/2
return
-self.small[0] if len(self.small)>len(self.large) else self.large[0]
# Time: O(log n) per add, O(1)
median

41. Evaluate Division (graph) — [Google] (Medium)

Given equations like a/b=2, evaluate queries using graph ratios.

Idea: Build graph and BFS/DFS evaluate product along path.

Example Input Expected Output
a/b=2, b/c=3, query a/c 6.0
from collections import defaultdict, deque
def calc_equation(equations, values, queries):
g=defaultdict(list)
for (a,b),v in zip(equations,values):
g[a].append((b,v));
g[b].append((a,1/v))
def bfs(src,tgt):
if src not in g or tgt not in g: return -1.0
q=deque([(src,1.0)]); seen={src}
while q:
node,prod=q.popleft()
if
node==tgt: return prod
for nei, val in g[node]:
if nei not in seen:
seen.add(nei); q.append((nei, prod*val))
return -1.0
return [bfs(a,b) for a,b in
queries]
# Time: O(Q*(V+E)), Space: O(V+E)

42. Binary Search Tree Iterator — [Google] (Medium)

Implement iterator over BST returning next smallest element.

Idea: Stack of nodes go left as far as possible.

Example Input Expected Output
iterate tree inorder sequence
class BSTIterator:
def __init__(self, root):
self.stack=[]
self._push_left(root)
def _push_left(self,node):
while node:
self.stack.append(node); node=node.left
def next(self):
node=self.stack.pop(); val=node.val
self._push_left(node.right);
return val
def hasNext(self):
return bool(self.stack)
# Time: O(1) amortized per op

43. Longest Increasing Subsequence — [Google] (Hard)

Length of LIS in array.

Idea: Patience sorting with binary search O(n log n).

Example Input Expected Output
nums=[10,9,2,5,3,7,101,18] 4
import bisect
def length_of_lis(nums):
sub=[]
for x in nums:
i=bisect.bisect_left(sub, x)
if i==len(sub): sub.append(x)
else: sub[i]=x
return
len(sub)
# Time: O(n log n), Space: O(n)

44. Palindrome Partitioning — [Google] (Medium)

Return all palindrome partitioning of string.

Idea: Backtracking with palindrome check / DP pruning.

Example Input Expected Output
s='aab' [['a','a','b'],['aa','b']]
def partition(s):
res=[]; n=len(s)
def ispal(l,r):
while l<r:
if
s[l]!=s[r]: return False
l+=1; r-=1
return True
def backtrack(start,path):
if start==n: res.append(path[:]); return
for end in range(start,n):
if
ispal(start,end):
path.append(s[start:end+1]); backtrack(end+1,path); path.pop()
backtrack(0,[]); return res
# Time: exponential, Space: exponential

45. Minimum Number of Arrows to Burst Balloons — [Amazon] (Medium)

Given intervals, min arrows to cover all (points can shoot through interval).

Idea: Sort by end and greedy cover.

Example Input Expected Output
points=[[10,16],[2,8],[1,6],[7,12]] 2
def find_min_arrows(points):
if not points: return 0
points.sort(key=lambda x:x[1])
arrows=1; end=points[0][1]
for s,e in points[1:]:
if s> end:
arrows+=1;
end=e
return arrows
# Time: O(n log n), Space: O(1)

46. Sliding Window Maximum — [Google] (Hard)

Return max in each sliding window of size k.

Idea: Use deque to maintain candidates.

Example Input Expected Output
nums=[1,3,-1,-3,5,3,6,7], k=3 [3,3,5,5,6,7]
from collections import deque
def max_sliding_window(nums,k):
if not nums: return []
dq=deque(); res=[]
for i,n in enumerate(nums):
while dq and nums[dq[-1]]<n: dq.pop()
dq.append(i)
if dq[0]==i-k: dq.popleft()
if i>=k-1: res.append(nums[dq[0]])
return res
# Time: O(n), Space: O(k)

47. Random Pick with Weight — [Google] (Medium)

Pick index randomly proportional to weights.

Idea: Prefix sums + binary search.

Example Input Expected Output
weights=[1,3] index 1 more likely
import random, bisect
class Solution:
def __init__(self, w):
self.prefix=[0]
for
x in w: self.prefix.append(self.prefix[-1]+x)
def pickIndex(self):
target=random.randint(1,self.prefix[-1])
return bisect.bisect_left(self.prefix, target)-1
#
Time: O(log n) per pick, Space: O(n)

48. Number of Connected Components in Undirected Graph —

[Leetcode/Graph] (Medium)

Count connected components using union-find or DFS.

Idea: Union-find quick implementation.

Example Input Expected Output
n=5, edges=[[0,1],[1,2],[3,4]] 2
def count_components(n, edges):
parent=list(range(n))
def find(x):
while
parent[x]!=x:
parent[x]=parent[parent[x]]; x=parent[x]
return x
def
union(a,b):
ra,rb=find(a),find(b)
if ra!=rb: parent[ra]=rb
for a,b in edges:
union(a,b)
return len({find(i) for i in range(n)})
# Time: approx O((V+E)α(V)), Space: O(V)

49. URL Shortener (design coding) — [System Design mini] (Medium)

Design a tiny URL shortener: encode(longUrl)->short and decode(short)->long.

Idea: Base62 id encoding + DB mapping or hashing with collision handling.

Example Input Expected Output
encode/decode roundtrip works
import string, random
class TinyURL:
def __init__(self):
self.db={}; self.counter=1;
self.chars=string.ascii_letters+string.digits
def _encode(self, n):
s=''
while
n>0:
s+=self.chars[n%62]; n//=62
return s[::-1] or '0'
def
encode(self,longUrl):
short=self._encode(self.counter); self.db[short]=longUrl;
self.counter+=1; return short
def decode(self, short):
return self.db.get(short, '')
#
Simple; production requires persistence, collisions, custom domain.

50. Sliding Window: Longest Repeating Character Replacement —

[Leetcode/Amazon] (Medium)

Given string s and k replacements, longest substring with same char after <=k replacements.

Idea: Sliding window tracking max count of a single char in window.

Example Input Expected Output
s='AABABBA', k=1 4
def character_replacement(s,k):
count=[0]*26; l=0; maxf=0; res=0
for r,ch in enumerate(s):
count[ord(ch)-65]+=1
maxf=max(maxf, count[ord(ch)-65])
while r-l+1 - maxf > k:
count[ord(s[l])-65]-=1; l+=1
res=max(res, r-l+1)
return res
# Time: O(n), Space: O(26)
Notes & Tips

• Practice implementing these problems by hand and on a whiteboard. • Explain your approach before coding in
interviews. • Discuss time/space complexity and edge cases. • For system-design style problems, mention
persistence, scaling, and failure cases.

If you want the source code files (one .py per problem), unit tests, or a version tagged per company with frequency
notes, tell me — I can generate downloadable ZIP too.