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

  1. 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.
  2. 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.
  • 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.
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:

  1. 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.
  2. The mid = left + (right - left)//2 is used to avoid overflow, as mid = (left + right)//2 can cause overflow for large arrays.
  3. 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.