Day 36: Kth Largest Element in Array

Day 36 — Kth Largest Element in Array

Coding problem

Solution outline (coding)

• Quickselect: partition like quicksort until pivot index = n-k (kth largest).
• Or min-heap of size k over elements.
• Heap is simpler to code; quickselect is O(n) average.

Time complexity: O(n) average quickselect; O(n log k) with a heap.

Space complexity: O(1) in-place partition; O(k) for heap.

import heapq
from typing import List


class Solution:
  def findKthLargest(self, nums: List[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]


# Input:  nums = [3,2,1,5,6,4], k = 2
# Output: 5

SQL interview practice

1. Interview question

Companies / track: Meta, Google

Meta and Google both lean on ads and product surfaces: event streams, CTR-style rates, windowed metrics, and careful handling of identity joins.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta, Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
orders(user_id, order_id, amount). BigQuery: compute kth largest order amount per user and overall using window RANK/DENSE_RANK.

Tables implied by the prompt:

• orders(user_id, order_id, amount)

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 Heap / Quickselect to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT user_id, order_id, amount,
  RANK() OVER (PARTITION BY user_id ORDER BY amount DESC) AS amt_rank
FROM orders;