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:

1041. Robot Bounded In Circle

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)

54. Spiral Matrix

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:

15. 3Sum

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)

40. Combination Sum II

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 -1
left, 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-1
return -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 :)

UPDATE: Part 2 and Part 3 are published

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

A bright future for Frame

Python OOP Tutorial | Part I: Classes and Objects

Organizing your UI for Performance in Unity

Transformers in Swift

Most Frequently Used Git Commands

Using platform variants when testing flutter widgets

Our Story with Stakeborg

Build and deploy a Maven project with circleci to heroku

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Muhammed Abogazia

Muhammed Abogazia

human

More from Medium

Bee Travel Puzzle

14 Days Study Plan to Crack Algo I

Steps to design a Dynamic programming algorithm

Leetcode Q260. Single Number III (Q237)