Optimize password transform and discount scheduling
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Part 1 — Transform to palindromic k-periodic string:
Input: a lowercase string currentPassword and integer k.
Constraints: 1 <= k < len(currentPassword) <= 2*10^5, and len(currentPassword) is divisible by k.
Operation: you may change any character to any lowercase letter; the cost is the number of positions changed.
Goal: convert currentPassword to newPassword such that
(a) newPassword is a palindrome, and
(b) newPassword[i] = newPassword[i + k] for all valid i (0-based). Return the minimum number of character changes required and describe the algorithm with time and space complexity.
Example: currentPassword = "abzzbz", k = 3 → one optimal newPassword is "zbzzbz"; answer = 1.
Part 2 — Minimize processing cost with daily discount:
Input: integer n; arrays filterCost[1..n], startDay[1..n], endDay[1..n]; and integer discountPrice. For each day d, the set of active images is { i | startDay[i] <= d <= endDay[i] }. Without a discount, day d costs sum(filterCost[i] over active images i). You may apply the discount at most once per day; if applied on day d, the total cost that day is exactly discountPrice.
Goal: process all n images over their required day ranges to minimize the total cost across all days; return the minimum total cost modulo 1,000,000,007. Provide the algorithm and its time and space complexity.
Example: n = 3; filterCost = [2,3,4]; startDay = [1,1,2]; endDay = [2,3,4]; discountPrice = 6. Per-day sums: day1=5, day2=9, day3=7, day4=4. Using the discount on days 2 and 3 gives total 5 + 6 + 6 + 4 = 21.
Quick Answer: Optimize password transform and discount scheduling evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Part 1: Minimum Changes to a Palindromic k-Periodic Password
Given a lowercase string currentPassword and an integer k, change as few characters as possible so that the resulting string is both a palindrome and k-periodic. A string is k-periodic if newPassword[i] == newPassword[i + k] for every valid index i. Return the minimum number of character changes required. Assume inputs are valid and len(currentPassword) is divisible by k.
Constraints
- 1 <= k < len(currentPassword) <= 2 * 10^5
- len(currentPassword) is divisible by k
- currentPassword contains only lowercase English letters
Examples
Input: ('abzzbz', 3)
Expected Output: 1
Explanation: Residue classes 0 and 2 must become the same character. Changing the first 'a' to 'z' gives 'zbzzbz'.
Input: ('ab', 1)
Expected Output: 1
Explanation: With k = 1, the whole string must be one repeated character. Change either 'a' or 'b'.
Hints
- k-periodicity forces all positions with the same index modulo k to contain the same character.
- The palindrome condition pairs residue class r with residue class k - 1 - r.
Part 2: Minimize Processing Cost with a Daily Discount
You are given n images. Image i is active on every day from startDay[i] through endDay[i], inclusive, and contributes filterCost[i] to that day's processing cost. On each day, you may optionally apply a discount, making that day's total cost exactly discountPrice. Return the minimum total cost across all days, modulo 1,000,000,007. A reasonable assumption for this standalone problem is that n may be 0; in that case, the answer is 0.
Constraints
- 0 <= n <= 2 * 10^5
- len(filterCost) == len(startDay) == len(endDay) == n
- 0 <= filterCost[i] <= 10^9
- 1 <= startDay[i] <= endDay[i] <= 10^9
- 0 <= discountPrice <= 10^9
Examples
Input: (3, [2, 3, 4], [1, 1, 2], [2, 3, 4], 6)
Expected Output: 21
Explanation: Daily sums are 5, 9, 7, 4. Use the discount on days 2 and 3 for total 5 + 6 + 6 + 4 = 21.
Input: (0, [], [], [], 6)
Expected Output: 0
Explanation: There are no images and no active days.
Hints
- For any fixed day, the optimal cost is min(activeCostSum, discountPrice).
- The active cost sum only changes on startDay[i] and endDay[i] + 1, so sweep those event days instead of iterating over every day.