Familiarize yourself with typical problem patterns: string manipulation (finding substrings, counting characters), array operations (finding duplicates, sorting, searching), two-pointer techniques, basic recursion, and simple dynamic programming. Focus on problems that are LeetCode Easy to Easy-Medium difficulty.
HardTechnical
55 practiced
Coin Change (Minimum Coins): Given an integer amount and a list of coin denominations, compute the fewest number of coins needed to make up that amount, or return -1 if not possible. Implement coinChange(coins, amount) in Python using dynamic programming (bottom-up) with O(amount * len(coins)) time. Discuss when BFS can be used as an alternative and trade-offs between methods.
Sample Answer
To solve this, use bottom-up dynamic programming: dp[x] = fewest coins to make amount x. Initialize dp[0]=0 and dp[1..amount]=inf. For each amount a from 1..amount, try every coin c and update dp[a] = min(dp[a], dp[a-c]+1) if a>=c and dp[a-c] is reachable. Return dp[amount] or -1.
python
def coinChange(coins, amount):
"""
Bottom-up DP. Time: O(amount * len(coins)). Space: O(amount).
"""
INF = amount + 1 # sentinel > any possible answer
dp = [INF] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != INF else -1
Key points:- Deterministic, simple, and optimal for unbounded coin usage.- Time O(amount * n), space O(amount).Edge cases:- amount = 0 -> 0; empty coins -> -1 (unless amount=0); large amounts may need memory/time considerations.BFS alternative:- Treat amounts as nodes; edges add coin values. BFS from 0 finds shortest path (fewest coins) and can stop when you reach amount. BFS is often faster when the reachable state space until target is small and coins are positive integers. Trade-offs: BFS may explore fewer states for small targets but still can be O(amount * n) worst-case; DP is simpler, uses predictable memory and often faster due to cache-friendly loops.
MediumTechnical
62 practiced
Valid Parentheses: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. Implement isValid(s) in Python using a stack with O(n) time and O(n) space. Example: s='()[]{}' -> true, s='(]' -> false. Explain why a stack is the appropriate data structure.
Sample Answer
To validate brackets, use a stack: push opening brackets, pop and check when encountering a closing bracket. A stack enforces last-in-first-out, matching the most recent unmatched opening bracket (nesting), so it's the natural DS for this parsing.
python
def isValid(s: str) -> bool:
"""
Return True if s has valid matched parentheses.
O(n) time, O(n) space.
"""
# map closing -> opening for quick checks
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in pairs.values(): # opening bracket
stack.append(ch)
elif ch in pairs: # closing bracket
if not stack or stack.pop() != pairs[ch]:
return False
else:
# unexpected character (optional: treat as invalid)
return False
return not stack # valid if no unmatched openings remain
Key points:- Stack operations push/pop are O(1); loop does O(n) work → O(n) time.- In worst case (all openings) stack holds O(n) items → O(n) space.- Edge cases: odd length string, starting with a closing bracket, unmatched openings at end, or invalid characters.- Alternative: scanning with index pairs or counting only works for simple non-nested cases; stack handles arbitrary nesting reliably.
MediumTechnical
75 practiced
Simplify Unix-style paths: Given a string path representing an absolute path (starting with '/'), simplify it to the canonical path. Implement simplifyPath(path) in Python considering '.' and '..' and removing extra slashes. Example: '/a/./b/../../c/' -> '/c'. Explain use of stack to solve the problem and describe edge cases.
Sample Answer
To simplify a Unix-style absolute path, use a stack to process path components: push valid directory names, ignore '.' and empty components, and pop for '..' (if stack not empty). At the end, join stack with '/' and prepend root '/'.
python
def simplifyPath(path):
"""
Simplify an absolute Unix-style path to its canonical form.
"""
parts = path.split('/') # split by slash -> may include '' and '.' and '..'
stack = []
for p in parts:
if p == '' or p == '.':
continue # ignore empty components and current dir
if p == '..':
if stack:
stack.pop() # go up one directory if possible
else:
stack.append(p) # valid directory name
return '/' + '/'.join(stack) # root + joined components (empty -> '/')
Key points:- Stack models directory depth: push for directories, pop for '..'.- split('/') makes parsing simple; skip empty pieces to handle repeated slashes.Time complexity: O(n) where n = len(path) (one pass). Space: O(k) for stack where k = number of valid components.Edge cases:- Input "/" or "/../" -> return "/".- Multiple consecutive slashes like "/a//b" handled by empty parts.- Trailing slash like "/a/b/" preserved correctly (canonical form has no trailing slash except root).Alternative: iterate with two-pointer without split if minimizing allocations; behavior remains same.
EasyTechnical
66 practiced
Merge two sorted arrays nums1 and nums2 into one sorted array in-place. You are given nums1 with size m+n where the first m elements are valid and the last n elements are zeros reserved for merging, and nums2 with n elements. Implement merge(nums1, m, nums2, n) in Java or C++ in O(m+n) time and O(1) extra space. Example: nums1=[1,2,3,0,0,0], m=3; nums2=[2,5,6], n=3 -> nums1 becomes [1,2,2,3,5,6].
Sample Answer
Approach: Use three pointers and fill nums1 from the end to avoid overwriting. Pointer p1 = m-1, p2 = n-1, write pointer p = m+n-1. Compare nums1[p1] and nums2[p2], place the larger at nums1[p], decrement pointers. When p2 < 0 we're done; if p1 < 0 copy remaining nums2 elements.
java
// Java implementation - O(m+n) time, O(1) extra space
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
int p = m + n - 1;
while (p2 >= 0) {
if (p1 >= 0 && nums1[p1] > nums2[p2]) {
nums1[p--] = nums1[p1--];
} else {
nums1[p--] = nums2[p2--];
}
}
}
Key points:- Fill from the back to avoid shifting elements.- Handles duplicates correctly.- Works when m==0 (just copies nums2) or n==0 (nums1 unchanged).Time complexity: O(m + n). Space complexity: O(1) extra space.Alternative: merge forward using extra buffer (O(m+n) space) — simpler but doesn't meet the O(1) space constraint.
HardTechnical
114 practiced
Longest Consecutive Sequence: Given an unsorted array of integers, find the length of the longest consecutive elements sequence in O(n) time. Implement in Python using a hash set and explain why you only start counting at numbers that are sequence starts (num-1 not present). Example: [100,4,200,1,3,2] -> 4 (sequence 1,2,3,4).
Sample Answer
To solve this in O(n) we use a hash set for O(1) membership checks and only begin counting from numbers that are sequence starts (i.e., num-1 not in set). That avoids re-counting sequences multiple times and ensures each element is visited at most twice (once when checked, once when advanced), yielding linear time.
python
def longest_consecutive(nums):
"""
Return length of longest consecutive sequence in O(n) time.
"""
if not nums:
return 0
s = set(nums)
longest = 0
for num in s:
# only start counting if num is the beginning of a sequence
if num - 1 not in s:
length = 1
cur = num + 1
while cur in s:
length += 1
cur += 1
longest = max(longest, length)
return longest
# Example
print(longest_consecutive([100, 4, 200, 1, 3, 2])) # -> 4
Key reasoning:- By skipping numbers with num-1 in set we ensure each sequence is counted exactly once, avoiding repeated O(k) scans for every member.- Time Complexity: O(n) average — each number is checked a constant number of times.- Space Complexity: O(n) for the set.Edge cases:- Empty list -> 0- Duplicates handled by set- Negative numbers work the sameAlternative: sort-based solution is simpler but O(n log n) instead of O(n).
Unlock Full Question Bank
Get access to hundreds of Common Interview Problem Patterns interview questions and detailed answers.
