Solve date, shopping, and circle problems
Company: Point72
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
You have three independent coding tasks:
A) Date normalization and business-day delta
- Input: a list of strings with mixed, possibly ambiguous date/time formats, 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 to strict UTC ISO 8601 "YYYY-MM-DDTHH:MM:SSZ".
- Disambiguation rules: if a date is of the form dd/mm/yy or mm/dd/yy, treat as dd/mm/yy when the first number > 12; otherwise default to mm/dd/yy. Two‑digit years map 00–68 → 2000–2068, 69–99 → 1969–1999. Validate leap years. If a timezone is absent, assume local time is UTC−08:00; then convert to UTC.
- Then, given any two normalized instants, compute business-day difference between their dates (ignore time-of-day), excluding weekends and a provided holiday set H = {2025-01-01, 2025-07-04, 2025-12-25}. Return an integer that can be negative.
- Edge cases to handle: invalid dates (return an error with the offending token), Feb 29 on non‑leap years, zero-length input, and timezone offsets like +05:45.
B) Arbitrary shopping with bundles (DP/memoization)
- You are given: target quantities T over up to 6 item types, unit prices P, and 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; 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 a solution with pruning and memoization over states; state space must not exceed 7^k for k item types.
- Edge cases: zero-cost bundles, dominated bundles, and bundles that oversupply (not allowed).
C) Circle‑relationship classifier with numerics
- Implement a function 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"}.
- Use squared distances to avoid precision loss; treat values within eps as equal. Radii may be zero. If "intersecting", also return the two intersection points (ordered by x then y), or one point if tangency detected within eps.
- Edge cases: coincident centers, one or both radii zero, very large coordinates (|x|,|y| ≤ 1e9), and near‑tangency scenarios where |d − (r1±r2)| < eps.
Quick Answer: This multi‑part problem evaluates skills in robust date/time parsing and timezone normalization with business‑day arithmetic, dynamic programming and memoization for constrained bundle selection and cost minimization, and computational geometry for circle relationship classification and intersection point computation.
Normalize Dates and Business-Day Difference
Normalize mixed date strings to UTC ISO-8601 and optionally count business days in [date1, date2).
Constraints
- Ambiguous slash dates default to mm/dd/yy unless first number > 12
- Missing timezone means UTC-08:00
Examples
Input: (['2025/02/28 23:59 PST', '28-02-2025', '02/03/25', 'Mar 1, 2025 01:30 +0530'], None, None, None)
Expected Output: {'normalized': ['2025-03-01T07:59:00Z', '2025-02-28T08:00:00Z', '2025-02-03T08:00:00Z', '2025-02-28T20:00:00Z'], 'business_day_diff': None}
Explanation: Mixed supported formats.
Input: ([], '2025-07-03T00:00:00Z', '2025-07-08T00:00:00Z', {'2025-07-04'})
Expected Output: {'normalized': [], 'business_day_diff': 2}
Explanation: Business days exclude weekend and holiday.
Hints
- Parse into timezone-aware datetimes, then convert to UTC.
Shopping Bundles Minimum Cost
Given target quantities, unit prices, and special bundles, return a minimum exact cost and one deterministic decomposition.
Constraints
- Target quantities are small
- Oversupply is not allowed
Examples
Input: ({'A': 3, 'B': 2}, {'A': 5, 'B': 4}, [{'id': 'b1', 'items': {'A': 2, 'B': 1}, 'price': 12}, {'id': 'b2', 'items': {'A': 3}, 'price': 13}])
Expected Output: (21, {'bundles': {'b1': 1}, 'units': {'A': 1, 'B': 1}})
Explanation: Uses bundles plus units.
Input: ({'A': 0}, {'A': 5}, [{'id': 'free', 'items': {'A': 0}, 'price': 0}])
Expected Output: (0, {'bundles': {}, 'units': {}})
Explanation: Zero target.
Hints
- Memoize by remaining quantities; unit purchases provide the baseline when available.
Circle Relationship Classifier
Classify two circles and return tangent/intersection points when they exist.
Constraints
- Radii are nonnegative
- Points are rounded to six decimals
Examples
Input: ((0, 0, 1), (3, 0, 1), 1e-09)
Expected Output: {'relation': 'separate', 'points': []}
Explanation: Separate circles.
Input: ((0, 0, 1), (2, 0, 1), 1e-09)
Expected Output: {'relation': 'externally_tangent', 'points': [(1.0, 0.0)]}
Explanation: External tangency.
Hints
- Use the standard two-circle intersection formula after classifying distance relationships.