More patterns for coding interviews

1- Traversing 2D space.

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

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

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
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]

--

--

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