Day 86: Version-Controlled Data Structure

Day 86 — Version-Controlled Data Structure

Coding problem

Solution outline (coding)

• Model entity → (version, payload) with monotonic versions per write.
• get(T) returns latest version with version ≤ T — binary search versions.
• Clarify tie-breaking and concurrent writers.

Time complexity: O(log K) per read if K versions per key.

Space complexity: O(stored versions).

class ReviewDay:
  """Practice / review: Version-Controlled Data Structure."""

  def practice_plan(self):
    return [
      "Pick 2–3 problems from this phase; re-solve timed without notes.",
      "For each: pattern name, time/space complexity, one alternative approach.",
    ]


# Input:  (your choice of problems from this week or phase)
# Output: a short list of gaps to drill before the next session

SQL interview practice

1. Interview question

Companies / track: OpenAI

OpenAI / API-scale products: SQL often covers usage logs, experiments, and evaluation pipelines—clarity on keys and grain matters as much as syntax.

What you are asked to write (SQL prompt):

Frame this as metrics work for **OpenAI**-scale surfaces (ads, product, or engagement — as the tables suggest).
versioned_data(entity_id, version, payload, ts). BigQuery: design queries to retrieve latest consistent version at time T and audit version history per entity.

Tables implied by the prompt:

• versioned_data(entity_id, version, payload, ts)

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 Design / Build 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).

SELECT entity_id, version, payload
FROM versioned_data
WHERE ts <= @T
QUALIFY ROW_NUMBER() OVER (PARTITION BY entity_id ORDER BY version DESC) = 1;