Beyond Cracking the Coding Interview

class DynamicArray:
  def __init__(self):
    self.capacity = 10
    self._size = 0
    self.fixed_array = [None] * self.capacity

  def get(self, i):
    if i < 0 or i >= self._size:
      raise IndexError('Index out of bounds')
    return self.fixed_array[i]

  def set(self, i, x):
    if i < 0 or i >= self._size:
      raise IndexError('Index out of bounds')
    self.fixed_array[i] = x

  def size(self):
    return self._size

  def append(self, x):
    if self._size == self.capacity:
      self.resize(self.capacity * 2)
    self.fixed_array[self._size] = x
    self._size += 1

  def resize(self, new_capacity):
    new_fixed_size_arr = [None] * (new_capacity)
    for i in range(self._size):
      new_fixed_size_arr[i] = self.fixed_array[i]
    self.fixed_array = new_fixed_size_arr
    self.capacity = new_capacity

  def pop_back(self):
    if self._size == 0:
      raise IndexError('Pop from empty array')
    self._size -= 1
    if self._size / self.capacity < 0.25 and self.capacity > 10:
      self.resize(self.capacity//2)

class DynamicArrayExtras(DynamicArray):
  def pop(self, i):
    if i < 0 or i >= self._size:
      raise IndexError('Index out of bounds')

    x = self.fixed_array[i]

    for j in range(i, self._size - 1):
      self.fixed_array[j] = self.fixed_array[j + 1]

    self._size -= 1
    if self._size / self.capacity < 0.25 and self.capacity > 10:
      self.resize(self.capacity // 2)
    return x

  def contains(self, x):
    for i in range(self._size):
      if self.fixed_array[i] == x:
        return True
    return False

  def insert(self, i, x):
    if i < 0 or i > self._size:
      raise IndexError('Index out of bounds')

    if self._size == self.capacity:
      self.resize(self.capacity * 2)

    for j in range(self._size - 1, i - 1, -1):
      self.fixed_array[j + 1] = self.fixed_array[j]

    self.fixed_array[i] = x
    self._size += 1

  def remove(self, x):
    for i in range(self._size):
      if self.fixed_array[i] == x:
        self.pop(i)
        return i
    return -1

def split(s, c):
  if not s:
    return []

  res = []
  current = []
  i = 0
  while i < len(s):
    if s[i] == c:
      res.append(''.join(current))
      current = []
    else:
      current.append(s[i])
    i += 1
  res.append(''.join(current))
  return res

def join(arr, s):
  res = []
  for i in range(len(arr)):
    if i != 0:
      for c in s:
        res.append(c)
    for c in arr[i]:
      res.append(c)
  return array_to_string(res)

def array_to_string(arr):
  # Function allowed by the problem statement.
  return ''.join(arr)

def index_of_naive_solution(s, t):
  if not t:
    return 0
  if not s:
    return -1

  for i in range(len(s) - len(t) + 1):
    found = True
    for j in range(len(t)):
      if s[i + j] != t[j]:
        found = False
        break
    if found:
      return i
  return -1

LARGE_PRIME = 10**9 + 7
def power(x):
  res = 1
  for i in range(x):
    res = (res * 128) % LARGE_PRIME
  return res

def str_to_num(str):
  res = 0
  for c in str:
    res = (res * 128 + ord(c)) % LARGE_PRIME
  return res

def next_hash(s, tn, i, current_hash, first_power):
  # Assumes that current_hash is the hash of s[i:i+tn].
  # Assumes that first_power is 128^(tn-1) % LARGE_PRIME.
  # Returns the hash of the next substring of s of length tn: s[i+1:i+tn+1].

  res = current_hash
  # 1. Remove the contribution from the first character (s[i]).
  res = (res - ord(s[i]) * first_power) % LARGE_PRIME
  # 2. Increase every exponent.
  res = (res * 128) % LARGE_PRIME
  # 3. Add the contribution from the new character (s[i+tn]).
  return (res + ord(s[i + tn])) % LARGE_PRIME

def index_of_using_rolling_hash(s, t):
  sn, tn = len(s), len(t)
  if tn > sn:
    return -1
  hash_t = str_to_num(t)
  current_hash = str_to_num(s[:tn])
  if hash_t == current_hash and t == s[:tn]:
    return 0  # Found t at the beginning.
  first_power = power(tn - 1)
  for i in range(sn - tn):
    current_hash = next_hash(s, tn, i, current_hash, first_power)
    if hash_t == current_hash and t == s[i + 1:i + tn + 1]:
      return i + 1
  return -1

def palindrome(s):
  l, r = 0, len(s) - 1
  while l < r:
    if s[l] != s[r]:
      return False
    l += 1
    r -= 1
  return True

def smaller_prefixes(arr):
  sp, fp = 0, 0
  slow_sum, fast_sum = 0, 0
  while fp < len(arr):
    slow_sum += arr[sp]
    fast_sum += arr[fp] + arr[fp + 1]
    if slow_sum >= fast_sum:
      return False
    sp += 1
    fp += 2
  return True

def common_elements(arr1, arr2):
  p1, p2 = 0, 0
  res = []
  while p1 < len(arr1) and p2 < len(arr2):
    if arr1[p1] == arr2[p2]:
      res.append(arr1[p1])
      p1 += 1
      p2 += 1
    elif arr1[p1] < arr2[p2]:
      p1 += 1
    else:
      p2 += 1
  return res

def palindromic_sentence(s):
  l, r = 0, len(s) - 1
  while l < r:
    if not s[l].isalpha():
      l += 1
    elif not s[r].isalpha():
      r -= 1
    else:
      if s[l].lower() != s[r].lower():
        return False
      l += 1
      r -= 1
  return True

def reverse_case_match(s):
  l, r = 0, len(s) - 1
  while l < len(s) and r >= 0:
    if not s[l].islower():
      l += 1
    elif not s[r].isupper():
      r -= 1
    else:
      if s[l] != s[r].lower():
        return False
      l += 1
      r -= 1
  return True

def merge(arr1, arr2):
  p1, p2 = 0, 0
  res = []
  while p1 < len(arr1) and p2 < len(arr2):
    if arr1[p1] < arr2[p2]:
      res.append(arr1[p1])
      p1 += 1
    else:
      res.append(arr2[p2])
      p2 += 1
  while p1 < len(arr1):
    res.append(arr1[p1])
    p1 += 1
  while p2 < len(arr2):
    res.append(arr2[p2])
    p2 += 1
  return res

def two_sum(arr):
  l, r = 0, len(arr) - 1
  while l < r:
    if arr[l] + arr[r] > 0:
      r -= 1
    elif arr[l] + arr[r] < 0:
      l += 1
    else:
      return True
  return False

def three_way_merge(arr1, arr2, arr3):
  p1, p2, p3 = 0, 0, 0
  res = []
  while p1 < len(arr1) or p2 < len(arr2) or p3 < len(arr3):
    # Find the smallest value among current positions
    min_val = float('inf')
    if p1 < len(arr1):
      min_val = min(min_val, arr1[p1])
    if p2 < len(arr2):
      min_val = min(min_val, arr2[p2])
    if p3 < len(arr3):
      min_val = min(min_val, arr3[p3])

    # Skip duplicates of min_val in all arrays
    if p1 < len(arr1) and arr1[p1] == min_val:
      p1 += 1
    if p2 < len(arr2) and arr2[p2] == min_val:
      p2 += 1
    if p3 < len(arr3) and arr3[p3] == min_val:
      p3 += 1

    # Only add if we haven't added this value before
    if not res or res[-1] != min_val:
      res.append(min_val)

  return res

def sort_valley_array(arr):
  if len(arr) == 0:
    return []
  l, r = 0, len(arr) - 1
  res = [0] * len(arr)
  i = len(arr) - 1
  while l < r:
    if arr[l] >= arr[r]:
      res[i] = arr[l]
      l += 1
      i -= 1
    else:
      res[i] = arr[r]
      r -= 1
      i -= 1
  res[0] = arr[l]
  return res

def missing_numbers(arr, low, high):
  p1 = 0  # pointer for arr
  p2 = low  # pointer for virtual arr2
  res = []

  while p1 < len(arr) and p2 <= high:
    if arr[p1] < p2:
      p1 += 1
    elif arr[p1] == p2:
      p1 += 1
      p2 += 1
    else:
      res.append(p2)
      p2 += 1

  if p2 <= high:
    res.extend(range(p2, high + 1))
  return res

def intersection(int1, int2):
  overlap_start = max(int1[0], int2[0])
  overlap_end = min(int1[1], int2[1])
  return [overlap_start, overlap_end]

def interval_intersection(arr1, arr2):
  p1, p2 = 0, 0
  n1, n2 = len(arr1), len(arr2)
  res = []
  while p1 < n1 and p2 < n2:
    int1, int2 = arr1[p1], arr2[p2]
    if int1[1] < int2[0]:
      p1 += 1
    elif int2[1] < int1[0]:
      p2 += 1
    else:
      res.append(intersection(int1, int2))
      if int1[1] < int2[1]:
        p1 += 1
      else:
        p2 += 1
  return res

def reverse(arr):
  l, r = 0, len(arr) - 1
  while l < r:
    arr[l], arr[r] = arr[r], arr[l]
    l += 1
    r -= 1

def sort_even(arr):
  l, r = 0, len(arr) - 1
  while l < r:
    if arr[l] % 2 == 0:
      l += 1
    elif arr[r] % 2 == 1:
      r -= 1
    else:
      arr[l], arr[r] = arr[r], arr[l]
      l += 1
      r -= 1

def remove_duplicates(arr):
  s, w = 0, 0
  while s < len(arr):
    must_keep = s == 0 or arr[s] != arr[s - 1]
    if must_keep:
      arr[w] = arr[s]
      w += 1
    s += 1
  return w

def partition(arr, pivot):
  # First pass: partition into <= pivot and > pivot
  l, r = 0, len(arr) - 1
  while l < r:
    if arr[l] <= pivot:
      l += 1
    elif arr[r] > pivot:
      r -= 1
    else:
      arr[l], arr[r] = arr[r], arr[l]
      l += 1
      r -= 1

  # Find the boundary between <= pivot and > pivot
  boundary = 0
  while boundary < len(arr) and arr[boundary] <= pivot:
    boundary += 1

  # Second pass: partition the <= pivot section into < pivot and = pivot
  l, r = 0, boundary - 1
  while l < r:
    if arr[l] < pivot:
      l += 1
    elif arr[r] == pivot:
      r -= 1
    else:
      arr[l], arr[r] = arr[r], arr[l]
      l += 1
      r -= 1

def sort_colors(arr):
  # Count occurrences of each color
  r_count = sum(1 for c in arr if c == 'R')
  w_count = sum(1 for c in arr if c == 'W')

  # Rewrite array with the right number of each color
  i = 0
  for _ in range(r_count):
    arr[i] = 'R'
    i += 1
  for _ in range(w_count):
    arr[i] = 'W'
    i += 1
  while i < len(arr):
    arr[i] = 'B'
    i += 1

def swap_prefix_suffix(arr):
  if len(arr) == 0:
    return

  n = len(arr)

  # Reverse the whole array
  l, r = 0, n - 1
  while l < r:
    arr[l], arr[r] = arr[r], arr[l]
    l += 1
    r -= 1

  # Reverse the last n/3 elements
  l, r = 2 * n // 3, n - 1
  while l < r:
    arr[l], arr[r] = arr[r], arr[l]
    l += 1
    r -= 1

  # Reverse the first 2n/3 elements
  l, r = 0, (2 * n // 3) - 1
  while l < r:
    arr[l], arr[r] = arr[r], arr[l]
    l += 1
    r -= 1

def move_word(arr, word):
  seeker, writer = 0, 0
  i = 0
  while seeker < len(arr):
    if i < len(word) and arr[seeker] == word[i]:
      seeker += 1
      i += 1
    else:
      arr[writer] = arr[seeker]
      seeker += 1
      writer += 1
  for c in word:
    arr[writer] = c
    writer += 1