More patterns for coding interviews
Unpopular patterns that show up often in coding interviews
I assume you are already comfortable with common algorithms and data structure.
if you have not taken this course, you should start with it.
Examples are from Leetcode and solutions are in python
1- Traversing 2D space.
This pattern solves problems where you are given a 2D space or matrix and are required to traverse it in a given sequence of steps
This pattern is solved by defining position variables and a direction variable that indicates the next amount of shift in both x,y directions. then control the direction variable according to the problem statement
Turning left is reversing direction variable and multiplying x by -1
Turning right is reversing direction variable and multiplying y by -1
Moving forward is adding direction to the position
examples:
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
x,y,direction = 0,0,(0,1)for instruction in instructions:
if instruction == 'G': x,y = x+direction[0],y+direction[1]
elif instruction == 'L': direction = (-direction[1],direction[0])
else: direction = (direction[1],-direction[0])return (x==0 and y==0) or direction != (0,1)
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
x, y, di, visited, ans = 0,0,(0,1),set(),[]for _ in range(len(matrix)*len(matrix[0])):
ans.append(matrix[x][y])
visited.add((x,y))
if x+di[0] in (-1,len(matrix)) or y+di[1] in (-1, len(matrix[0])) or (x+di[0],y+di[1]) in visited:
di = (di[1], - di[0])
x,y = x+di[0], y+di[1]
return ans
2- Unique combinations
This pattern solves problems where you need to generate subsets of a given sequence that meet a certain condition. but they need to be non-repeating nor a permutation of each other
for example [[1,1,2],[1,1,2],[1,2,1]] is not valid because 1st and 2nd are duplicates and all of them are permutations of each other
To avoid duplicate subsets, sort and skip neighboring elements with the same value
To avoid permutations in the sorted array, consider elements only larger than the current element. so in the previous example [1,2,1] won’t be possible to generate because 1 is less than 2 so it can’t come after it
examples:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3: return []
nums.sort()
res, seen_i = set(), {}
for i in range(len(nums)-2):
if i>0 and nums[i]==nums[i-1]: continue
seen_k = {}
for j in range(i+1,len(nums)):
k = -nums[i]-nums[j]
if nums[j] in seen_k: res.add((nums[i], k, nums[j]))
else: seen_k[k]=1
return map(list, res)
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
candidates.sort()
def dfs(candidates,route,target):
if target==0: return ans.append(route)
for i, candidate in enumerate(candidates):
if candidate>target: break
if i>0 and candidate==candidates[i-1]: continue
dfs(candidates[i+1:], route+[candidate], target-candidate)
dfs(candidates,[],target)
return ans
3- Monotonic subarray
This pattern solved sorted and shifted array problems.
given a sorted, shifted array. one half of it is monotonic and the other one is not. you can use this property to eliminate one half at each step
Assuming the array is in increasing order, you can find the monotonic half by comparing the middle element with the last one, if the latter is larger then the right half is monotonic. else, the left one is.
examples:
33. Search in Rotated Sorted Array
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return -1left, right = 0, len(nums) - 1while left <= right:
mid = (left + right) // 2
if target == nums[mid]: return mid
if nums[mid]>=nums[left]:
if nums[left]<=target<=nums[mid]: right= mid-1
else: left = mid+1
else:
if nums[mid]<=target<=nums[right]: left = mid+1
else: right= mid-1return -1
154. Find Minimum in Rotated Sorted Array II
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0,len(nums)-1
while lo<hi:
mid = (lo+hi)//2
if nums[hi]>=nums[mid]: hi=mid if nums[hi] != nums[mid] else hi - 1
else:lo=mid+1
return nums[lo]
It’s getting too long. so I’m going to end it here
Give a clap if you are interested in more patterns :)