Solve date, shopping, and circle problems

Q: Solve date, shopping, and circle problems

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Point72.

Q: What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Point72 during technical interviews.

Question

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]]}.

Solve date, shopping, and circle problems

Quick Overview

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

A) Date Normalization and Business‑Day Difference

B) Arbitrary Shopping with Bundles (DP/Memoization)

C) Circle‑Relationship Classifier with Intersection Points

Solution

Comments (0)