Take‑Home: Three Independent Tasks (Data/Algorithms)

Implement three independent functions that will be unit‑tested separately. Provide clear error handling and document assumptions. Keep solutions efficient and robust to edge cases.

A) Date Normalization and Business‑Day Difference

• Input: a list of strings with mixed, possibly ambiguous date/time formats (may include timezone abbreviations or numeric offsets), e.g.,
  • ["2025/02/28 23:59 PST", "28-02-2025", "02/03/25", "2025-02-29", "Mar 1, 2025 01:30 +0530"]
• Normalize each string to strict UTC ISO 8601 format: "YYYY-MM-DDTHH:MM:SSZ".
• Disambiguation rules:
  1. Ambiguous slashed dates: if form dd/mm/yy or mm/dd/yy, treat as dd/mm/yy when the first number > 12; otherwise default to mm/dd/yy.
  2. Two‑digit years: map 00–68 → 2000–2068, and 69–99 → 1969–1999.
  3. Validate leap years properly.
  4. If no timezone is present, assume local time is UTC−08:00; then convert to UTC.
• Then, given any two normalized instants, compute the business‑day difference between their dates (ignore time‑of‑day):
  • Exclude weekends (Saturday, Sunday) and a holiday set H = {2025-01-01, 2025-07-04, 2025-12-25}.
  • Return a signed integer (can be negative). Define the difference as the count of business days in the half‑open interval [date1, date2).
• Edge cases to handle:
  • Invalid dates (return an error including the offending token).
  • Feb 29 on non‑leap years.
  • Zero‑length input list.
  • Timezone offsets with minutes (e.g., +05:45).

Deliverables:

• A function normalize_dates(list[str]) → list[str] (or an error with the offending token).
• A function business_day_diff(iso_utc_1: str, iso_utc_2: str, holidays: set[str]) → int.

B) Arbitrary Shopping with Bundles (DP/Memoization)

• You are given:
  • Target quantities T over up to 6 item types.
  • Unit prices P for each item type.
  • A list of special bundles; each bundle is a vector of item counts plus a bundle price.
• Compute the minimum total cost to satisfy T exactly (oversupply not allowed). If impossible, return −1. Also return one optimal combination of bundles and leftover unit purchases.
• Example:
  • T = {A: 3, B: 2}, P = {A: 5, B: 4}
  • Bundles = [b1: {A: 2, B: 1} @ 12, b2: {A: 3, B: 0} @ 13]
  • Output: min_cost and a decomposition (e.g., b1×1 + unit A×1 + unit B×1).
• Constraints:
  • 0 ≤ T[i] ≤ 6, 1 ≤ |Bundles| ≤ 20, prices are nonnegative integers.
  • Require pruning and memoization over states; state space must not exceed 7^k for k item types.
• Edge cases:
  • Zero‑cost bundles.
  • Dominated bundles.
  • Bundles that oversupply any item are not allowed in a step.

Deliverable:

• A function shop_min_cost(T, P, Bundles) → (min_cost: int, decomposition: any suitable structured description). Use DP with memoization over remaining needs.

C) Circle‑Relationship Classifier with Intersection Points

• Implement relate((x1, y1, r1), (x2, y2, r2), eps=1e-9) that returns one of:
  • {"separate", "externally_tangent", "intersecting", "internally_tangent", "contained_no_touch", "concentric_equal", "concentric_distinct"}.
• Requirements:
  • Use squared distances where possible to avoid precision loss; treat values within eps as equal.
  • Radii may be zero.
  • If the relation is "intersecting", also return the two intersection points (ordered by x then y). If tangency is detected within eps, return the single point.
• Edge cases:
  • Coincident centers.
  • One or both radii zero.
  • Very large coordinates (|x|,|y| ≤ 1e9).
  • Near‑tangency where |d − (r1±r2)| < eps.

Deliverable:

• A function relate(c1, c2, eps=1e-9) → {relation: str, points: list[tuple[float, float]]}.