Day 40: Task Scheduler

Day 40 — Task Scheduler

Coding problem

Solution outline (coding)

• Count task frequencies; the answer involves max_freq and how tasks fill idle slots.
• Greedy: arrange the most frequent task first in chunks of n+1 (cooldown), then fill with others.
• Formula approach: (max_freq-1)*(n+1) + count of tasks with max_freq.

Time complexity: O(n) — count and compute.

Space complexity: O(1) — 26 letters or O(k) distinct tasks.

from typing import List
from collections import Counter


class Solution:
  def leastInterval(self, tasks: List[str], n: int) -> int:
    c = Counter(tasks)
    mx = max(c.values())
    mx_count = sum(1 for v in c.values() if v == mx)
    return max(len(tasks), (mx - 1) * (n + 1) + mx_count)


# Input:  tasks = ["A","A","A","B","B","B"], n = 2
# Output: 8

SQL interview practice

1. Interview question

Companies / track: Meta

Meta: expect event logging, ads / integrity, and social product analytics—deduping, sessionization, and window functions are frequent themes.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
tasks(task_id, type, duration). BigQuery: design a schedule report that groups tasks to minimize CPU idle time; focus on how inputs/outputs are modeled, not algorithm details.

Tables implied by the prompt:

• tasks(task_id, type, duration)

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

SELECT task_id, type, duration,
  SUM(duration) OVER (ORDER BY task_id) AS cumulative_cpu
FROM tasks;