Technical Phone Screen prep

Question 1

How to reverse a linked list?

Answer 1

!/usr/bin/ruby

def reverse
curr = self
prev = nil

while curr
  tmp = curr.next
  curr.next = prev
  prev = curr
  curr = tmp
end

return prev   end

Question 2

Longest substring without repeating chars

Answer 2

class SolutionGreat:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        # mp stores the current index of a character
        mp = {}

        i = 0
        # try to extend the range [i, j]
        for j in range(n):
            if s[j] in mp:
                i = max(mp[s[j]], i)

            ans = max(ans, j - i + 1)
            mp[s[j]] = j + 1

        return and

Question 3

Num Islands

Answer 3

Start with the outer stuff. Define num_islands.
Have 2 loops that iterate through matrix and call explore( ) func if you find island (cell == 1).
Increment the num_islands variable. Then return num_islands.

Now write the explore function which is either BFS or DFS. Don’t forget to mark the island as visited (set to cell == 2).
Also be careful to check if the cell value is a character or integer. You had bugs here in the past.

from pprint import pprint

class Solution:
    def numIslands_2024_08_02(self, grid) -> int:
        def adjacents(grid, row, col):
            adjacents = []
            last_row = len(grid) - 1
            last_col = len(grid[0]) -1

            coords = [[0,1], [0,-1], [1,0], [-1,0]]
            for coord in coords:
                new_row = row + coord[0]
                new_col = col + coord[1]

                if new_row >= 0 and new_row <= last_row and new_col >= 0 and new_col <= last_col:
                    adjacents.append([new_row, new_col])

            return adjacents

        def explore(grid, row, col):
            # mark as visited
            grid[row][col] = '2'

            for pair in adjacents(grid, row, col):
                r = pair[0]
                c = pair[1]
                # check if visited or ocean
                if grid[r][c] != '1':
                    continue
                explore(grid, r, c)

        num_islands = 0
        num_rows = len(grid)
        num_cols = len(grid[0])
        for i in range(num_rows):
            for j in range(num_cols):
                if grid[i][j] == '1':
                    explore(grid, i, j)
                    num_islands += 1

        return num_islands

Question 4

Binary Search template

Answer 4

def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:  # <= because left and right could point to the same element, < would miss it
        mid = (left + right) // 2 # double slash for integer division in python 3, we don't have to worry about integer `left + right` overflow since python integers can be arbitrarily large
        # found target, return its index
        if arr[mid] == target:
            return mid
        # middle less than target, discard left half by making left search boundary `mid + 1`
        if arr[mid] < target:
            left = mid + 1
        # middle greater than target, discard right half by making right search boundary `mid - 1`
        else:
            right = mid - 1
    return -1 # if we get here we didn't hit above return so we didn't find target