Day 80: Search in Rotated Sorted Array

Day 80 — Search in Rotated Sorted Array

Coding problem

Solution outline (coding)

• Binary search on index range; at mid, compare nums[mid] to ends to see which half is sorted.
• Decide whether target lies in sorted half; shrink lo/hi.
• Duplicates optional variant — compare nums[lo], nums[mid], nums[hi].

Time complexity: O(log n) without duplicates; O(n) worst with many duplicates.

Space complexity: O(1).

from typing import List


class Solution:
  def search(self, nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      if nums[mid] == target:
        return mid
      if nums[lo] <= nums[mid]:
        if nums[lo] <= target < nums[mid]:
          hi = mid - 1
        else:
          lo = mid + 1
      else:
        if nums[mid] < target <= nums[hi]:
          lo = mid + 1
        else:
          hi = mid - 1
    return -1


# Input:  nums = [4,5,6,7,0,1,2], target = 0
# Output: 4

SQL interview practice

1. Interview question

Companies / track: Google

Google: SQL screens usually assume BigQuery, Ads / Search / YouTube-style fact tables, and talking through bytes processed and partition pruning.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
rotated_arrays(id, arr). BigQuery: with arrays stored as ARRAY<INT64>, implement search for a value using UDF and record latency by array length.

Tables implied by the prompt:

• rotated_arrays(id, arr)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map Binary Search to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT id, arr,
  (SELECT MIN(i) FROM UNNEST(arr) AS x WITH OFFSET i WHERE x = @target) AS idx
FROM rotated_arrays;