Preparation for Interviews
Commuication, code stype, runnable code, good test cases in a given time are more important than coming up with a very optimised solution.
- Code style: Use meaningful variable names, use comments to explain the code, use functions to break down the problem.
- Runnable code: Make sure the code can be run, use a simple test case to demonstrate the code works. You should have knowledge of the edge cases, and possible exceptions.
- Communication: Explain the code, explain the logic behind the code, explain the time and space complexity of the code. It is always good to well understand the code and explain your idea before the implementation.
- Test cases: Use simple test cases to demonstrate the code works, and explain the edge cases. It is always good to have a few test cases in mind before the interview.
String
Find the first occurrence of a substring in a string.
def strStr(haystack: str, needle: str) -> int:
""" Return the index of first occurrence of needle in haystack, or -1 if not found
This is the implementation of find() function in Python.
time O(n*m) memory O(1)
"""
n_needle = len(needle)
# The last start index of needle is len(haystack) - n_needle
for i in range(len(haystack) - n_needle + 1):
match = True
for j, v in enumerate(needle):
if haystack[i+j] != v:
match = False
break
if match:
return i
return -1
Recursive
When I say recusive, is the idea of recursion, not the function which call itself. To find all subsets of a set, we start we a list contain only on empty set. Each time we go through all elements in the list and add the current element to each subset in the list, then we add the new subsets to the list. This is a recursive idea, but it is implemented with a for loop. So the lenght list of subsets is doubled each time we add a new element to the set.
def subsets(nums: list[int]) -> list[list[int]]:
""" https://leetcode.com/problems/subsets
Given an integer array nums of unique elements,
return all possible subsets (the power set).
there is only for loop, but it using recursive idea,
each time we update the subsets and reuse it.
"""
subsets = [[]]
for e in nums:
new_subsets = []
for s in subsets:
new_s = s.copy()
new_s.append(e)
new_subsets.append(new_s)
subsets += new_subsets
return subsets
For the subsets of a set with duplicated elements, we can use a counter to count the number of each element in the set. Then we can generate all subsets by adding the current element to each subset in the list. The combination of several same elements is treated as a new element, and we can add it to the list of subsets the same time with the base element to not generate duplicate subset.
def subset2(nums: list[int]) -> list[list[int]]:
""" https://leetcode.com/problems/subsets-ii
This time, there are duplicated elements.
"""
subsets = [[]]
counts = Counter(nums)
for e, count in counts.items():
new_subsets = []
for s in subsets:
for c in range(count):
new_s = s.copy()
new_s += [e] * (c + 1)
new_subsets.append(new_s)
subsets += new_subsets
return subsets
Binary Search
Binary search is a very common algorithm to find an element in a sorted array. The idea is to divide the array into two halves, and check if the element is in the left half or the right half. If it is in the left half, we continue to search in the left half, otherwise we search in the right half. This process continues until we find the element or the array is empty.
Usally in the following cases we use binary search:
- Find a log(n) algorithm or optimise a O(n) algorithm.
- Solve a problem in a sorted array or rotated sorted array.
There are two common ways to implement binary search:
- Iterative: We use a while loop to search for the element, and update the left and right pointers based on the comparison of the middle element and the target element.
- Recursive: We use a recursive function to search for the element, and return the index of the element if found, otherwise return -1. But this not a good idea for production code, as it can cause stack overflow for large arrays.
There are some common problems that can be solved with binary search:
- Find any occurrence of an element in a sorted array.
- Find the first occurrence of an element in a sorted array.
- This is the behavior of the
bisect_left
function in Python. Get the position to insert a new element in a sorted array, such that the order of the array is preserved. If the element is already present, the insertion point will be before (to the left of) any existing entries. Bisect show the position where the new element should stay after the insertion.
- This is the behavior of the
- Find the last occurrence of an element in a sorted array.
- This is the behavior of the
bisect_right
function in Python. Get the position to insert a new element in a sorted array, such that the order of the array is preserved. If the element is already present, the insertion point will be after (to the right of) any existing entries.
- This is the behavior of the
def binary_search_first(nums:list[int], target:int):
""" get the first occurence position of target (bisect.bisect_left)
"""
if nums is None or len(nums) == 0:
return -1
left, right = 0, len(nums) -1
while left + 1 < right:
mid = left + (right - left)//2
if nums[mid] == target:
right = mid # for ,any position case, you can just return
elif nums[mid] < target:
left = mid # (+1, -1 may not work for case when first that is bigger than target... )
else:
right = mid
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
def binary_search_last(nums:list[int], target:int):
""" get the last occurence position of target (bisect.bisect_right)"""
n = len(nums)
if nums is None or n == 0:
return -1
left, right = 0, n -1
while left + 1 < right:
mid = left + (right - left)//2
if nums[mid] == target:
left = mid
elif nums[mid] < target:
left = mid
else:
right = mid
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
There are three thing to mention here:
- The (left + 1 < right ) condition is used to avoid infinite loop, as we need to narrow down the search space. We break the loop when there are only two elements left in the search space.
- The
mid = left + (right - left)//2
is used to avoid overflow, asmid = (left + right)//2
can cause overflow for large arrays. - The
if nums[mid] == target:
condition is used to check if the middle element is the target element, and we update the left or right pointer based on the comparison of the middle element and the target element. If we want to find the first occurrence of the target element, we update the right pointer to mid, otherwise we update the left pointer to mid. If we want any occurrence of the target element, we can just return the mid index.
Get the square root of a number
Find the integer sqrt root of a number using binary search. This is the problem of finding the last occurrence x
such that x*x <= n
. The idea is to use binary search to find the integer square root of a number. We can use the same approach as above, but we need to check if mid*mid <= n
instead of nums[mid] == target
.
def sqrt(x:int) -> int:
""" compute and return the square root of x
idea: **Last** number i that i**2 <= x
"""
left, right = 1, x
while left + 1 < right:
mid = left + (right - left)//2
sq_mid = mid ** 2
if sq_mid == x:
left = mid
elif sq_mid < x:
left = mid
else:
right = mid
if right ** 2 <= x:
return right
return left
search-a-2d-matrix
This is a binary search if we transform the 2D matrix into a 1D array. row, col = divmod(mid, n) is used to find the original row and column. log(M) + log(N) = log(MN) = log(MN) is the time complexity of this algorithm, where M is the number of rows and N is the number of columns in the matrix. The space complexity is O(1) as we only use a few variables to store the left, right, mid, row, and col indices.
def search_matrix(matrix:list[list[int]], target:int) -> bool:
""" https://leetcode.com/problems/search-a-2d-matrix
Each row is sorted in non-decreasing order.
The first integer of each row is greater
than the last integer of the previous row.
"""
if len(matrix) == 0 and len(matrix[0]) == 0:
return False
if len(matrix) == 1 and len(matrix[0]) == 1:
return matrix[0][0] == target
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left + 1 < right:
mid = left + (right - left)//2
row, col = divmod(mid, n)
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
left = mid
else:
right = mid
row1, col1 = divmod(left, n)
row2, col2 = divmod(right, n)
if matrix[row1][col1] == target or matrix[row2][col2] == target:
return True
return False
Or we can do two binary searches, one for the row and one for the column. But this is not a good idea as it is not efficient.
def search_matrix_method2(matrix: list[list[int]], target: int) -> bool:
"""
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
"""
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
starts = [row[0] for row in matrix]
start_pos = bisect.bisect_right(starts, target) - 1
if start_pos < 0:
return False
# Binary search in the identified row
row = matrix[start_pos]
col_pos = bisect.bisect_left(row, target)
return col_pos < n and row[col_pos] == target
search in rotated sorted array
It is a binary search, but we need to handle the case when the array is rotated. The idea is to find the pivot index where the array is rotated, and then use binary search to find the target element in the left or right half of the array based on the pivot index. The pivot index is the index where the array is rotated, and it can be found by checking if the middle element is greater than the rightmost element or not.
def search_in_rotated_sorted_array(nums: list[int], target: int):
""" https://leetcode.com/problems/search-in-rotated-sorted-array/
[4,5,6,7,0,1,2] the sorted array is rotated at pivot index k = 3
[k, k+1,...,n-1]
All values of nums are unique.
nums is an ascending array that is possibly rotated.
For a mid, there can be four cases for target.
In the first halp of not and bigger or smaller than mid
So we need to discuss these four cases in the implementation
"""
if not nums:
return -1
left, right = 0, len(nums) - 1
while left + 1 < right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid
else:
left = mid
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid
else:
right = mid
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
Array and Numbers
Merge Sorted Array Two merge two ordered array with one array has empty place. We should think of filling the array from the back to the front, so that we can avoid overwriting the elements in the first array and move all elements after the first element. This is a common problem in interview preparation, and it is a good practice to implement it in-place.
def merge_sorted_array(nums1:list[int], nums2:list[int]):
""" Merge two sorted array nums1 and nums2 into a new sorted interger array
Merge Sorted Array
https://leetcode.com/problems/merge-sorted-array
Do not return anything, modify nums1 in-place instead. Fill from back to front.
"""
m, n = len(nums1), len(nums2)
i, j, cur = m-1, n-1, m+n-1
while(i>=0 or j>=0):
if len(nums1)==0 or i<0:
nums1[cur] = nums2[j]
j-=1
elif len(nums2)==0 or j<0:
nums1[cur] = nums1[i]
i-=1
elif nums1[i] > nums2[j]:
nums1[cur] = nums1[i]
i-=1
else:
nums1[cur] = nums2[j]
j-=1
cur-=1
Dynamic Programming
Dynamic is more a way of thinking than a specific algorithm. It is used to solve problems that can be broken down into smaller subproblems, and the solution to the problem can be built from the solutions to the subproblems. The key idea is to store the solutions to the subproblems in a table, so that we can reuse them later.