Day 46: Longest Increasing Subsequence

Day 46 — Longest Increasing Subsequence

Coding problem

Solution outline (coding)

• O(n²): dp[i] = LIS ending at i by checking all j < i.
• O(n log n): maintain a list; for each x, binary search position to replace or extend.
• Patience sorting / tails array method.

Time complexity: O(n log n) optimal; O(n²) simpler.

Space complexity: O(n) — DP or tails array.

import bisect
from typing import List


class Solution:
  def lengthOfLIS(self, nums: List[int]) -> int:
    tails = []
    for x in nums:
      i = bisect.bisect_left(tails, x)
      if i == len(tails):
        tails.append(x)
      else:
        tails[i] = x
    return len(tails)


# Input:  nums = [10,9,2,5,3,7,101,18]
# 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).
salary_history(emp_id, eff_date, salary). BigQuery: compute longest strictly increasing salary run per employee.

Tables implied by the prompt:

• salary_history(emp_id, eff_date, salary)

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 DP / Binary Search to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH ordered AS (
  SELECT emp_id, eff_date, salary,
    LAG(salary) OVER (PARTITION BY emp_id ORDER BY eff_date) AS prev_sal
  FROM salary_history
),
flags AS (
  SELECT emp_id, eff_date,
    SUM(CASE WHEN salary > prev_sal THEN 0 ELSE 1 END) OVER (PARTITION BY emp_id ORDER BY eff_date) AS run_grp
  FROM ordered
)
SELECT emp_id, COUNT(*) AS lis_run_length
FROM flags
GROUP BY emp_id, run_grp
ORDER BY lis_run_length DESC
LIMIT 1;