Take-Home Project: Comprehensive Algorithmic and Data Processing Challenges

This take-home project requires the implementation of three independent functions, each addressing a distinct algorithmic or data processing challenge. Solutions must be efficient, robust to edge cases, and include clear error handling and documentation of assumptions. Each function will be unit-tested separately.

A) Date Normalization and Business-Day Difference

Implement two functions to handle date normalization and business day calculations:

1. normalize_dates(list[str]) -> list[str] (or an error with the offending token):

   • Input: A list of strings representing dates and times in various, potentially ambiguous formats (e.g., "2025/02/28 23:59 PST", "28-02-2025", "02/03/25", "2025-02-29", "Mar 1, 2025 01:30 +0530").
   • Output: Each input string normalized to a strict UTC ISO 8601 format: "YYYY-MM-DDTHH:MM:SSZ".
   • Disambiguation Rules:
     • Ambiguous Slashed Dates: For formats like dd/mm/yy or mm/dd/yy, if the first number is greater than 12, treat it as dd/mm/yy; otherwise, default to mm/dd/yy.
     • Two-Digit Years: Map years 00-68 to 2000-2068 and 69-99 to 1969-1999.
     • Leap Years: Validate leap years correctly.
     • Missing Timezone: If no timezone is specified, assume local time is UTC-08:00, then convert to UTC.
   • Edge Cases:
     • Invalid dates (should return an error including the offending token).
     • February 29th on non-leap years.
     • Zero-length input list.
     • Timezone offsets with minutes (e.g., +05:45).

2. business_day_diff(iso_utc_1: str, iso_utc_2: str, holidays: set[str]) -> int:

   • Input: Two normalized ISO 8601 UTC instant strings, and a set of holiday dates H = {2025-01-01, 2025-07-04, 2025-12-25}.
   • Output: A signed integer representing the business-day difference between the dates of the two instants (time-of-day should be ignored).
   • Definition: The difference is the count of business days in the half-open interval [date1, date2).
   • Exclusions: Exclude weekends (Saturday, Sunday) and the provided holiday set H.

B) Arbitrary Shopping with Bundles (Dynamic Programming/Memoization)

Implement a function to calculate the minimum cost for a shopping list:

• shop_min_cost(T, P, Bundles) -> (min_cost: int, decomposition: any suitable structured description):
  • Input:
    • T: Target quantities for up to 6 item types (e.g., {A: 3, B: 2}).
    • P: Unit prices for each item type (e.g., {A: 5, B: 4}).
    • Bundles: A list of special bundles, where each bundle specifies item counts and a bundle price (e.g., [b1: {A: 2, B: 1} @ 12, b2: {A: 3, B: 0} @ 13]).
  • Output: The minimum total cost to satisfy target quantities T exactly (oversupply is not allowed). If impossible, return -1. Also return one optimal combination of bundles and leftover unit purchases (e.g., b1×1 + unit A×1 + unit B×1).
  • Constraints:
    • 0 ≤ T[i] ≤ 6 for each item type i.
    • 1 ≤ |Bundles| ≤ 20.
    • Prices are non-negative integers.
    • The solution must use Dynamic Programming (DP) with memoization over states.
    • The state space must not exceed 7^k for k item types.
  • Edge Cases:
    • Zero-cost bundles.
    • Dominated bundles (bundles that are strictly worse than another combination).
    • Bundles that would oversupply any item are not allowed in a single purchase step.

C) Circle-Relationship Classifier with Intersection Points

Implement a function to classify the relationship between two circles and find their intersection points:

• relate(c1, c2, eps=1e-9) -> {relation: str, points: list[tuple[float, float]]}:
  • Input: Two circles c1 and c2, each defined as a tuple (x, y, r) (center coordinates and radius), and an optional eps (epsilon) value for floating-point comparisons, defaulting to 1e-9.
  • Output: A dictionary containing:
    • relation: A string describing the relationship. Possible values: "separate", "externally_tangent", "intersecting", "internally_tangent", "contained_no_touch", "concentric_equal", "concentric_distinct".
    • points: A list of (float, float) tuples representing intersection points. If the relation is "intersecting", return two points ordered by x then y. If tangency is detected within eps, return the single point.
  • Requirements:
    • Use squared distances where possible to mitigate floating-point precision loss.
    • Treat values within eps as equal for comparisons.
    • Radii may be zero.
  • Edge Cases:
    • Coincident centers.
    • One or both radii are zero.
    • Very large coordinates (e.g., |x|,|y| ≤ 1e9).
    • Near-tangency where |d − (r1±r2)| < eps (where d is the distance between centers).