How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

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

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Minimize image processing cost with discount

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

##### Question You have n images. For the i-th image, processing costs filterCost[i] per day and must run from startDay[i] to endDay[i] inclusive. Each day you may optionally apply a discount once: if used, processing all images that day costs discountPrice instead of the sum of their individual costs. Compute the minimum total cost to finish all images, modulo 1 000 000 007.

Quick Answer: This question evaluates a candidate's competence in algorithm design and optimization, including interval-based cost aggregation and modular arithmetic for large-number results within the Coding & Algorithms domain.

You have n images to process. The i-th image costs filterCost[i] per day and must be processed every day from startDay[i] to endDay[i], inclusive. On any day, you may choose to use a special discount at most once: if you use it, the total cost for processing all active images on that day becomes discountPrice instead of the sum of their individual daily costs. Compute the minimum total cost needed to finish all image processing, modulo 1000000007.

Constraints

0 <= n <= 200000
len(startDay) = len(endDay) = len(filterCost) = n
1 <= startDay[i] <= endDay[i] <= 1000000000 for each image
1 <= filterCost[i], discountPrice <= 1000000000

Examples

Input: ([1, 2], [3, 4], [10, 6], 10)

Expected Output: 36

Explanation: Day 1 costs 10. Days 2 and 3 each have total active cost 16, so using the discount makes each of those days cost 10. Day 4 costs 6. Total = 10 + 10 + 10 + 6 = 36.

Input: ([], [], [], 5)

Expected Output: 0

Explanation: There are no images to process, so the total cost is 0.

Input: ([1, 4], [2, 4], [3, 7], 20)

Expected Output: 13

Explanation: Days 1 and 2 each cost 3, day 3 has no active images, and day 4 costs 7. The discount is never useful. Total = 3 + 3 + 7 = 13.

Input: ([1, 1, 2], [2, 3, 3], [4, 5, 6], 10)

Expected Output: 29

Explanation: Day 1: 4 + 5 = 9. Day 2: 4 + 5 + 6 = 15, discounted to 10. Day 3: 5 + 6 = 11, discounted to 10. Total = 9 + 10 + 10 = 29.

Input: ([1], [1000000000], [1000000000], 1000000000)

Expected Output: 49

Explanation: The daily cost is 1000000000 for 1000000000 days, so the total is 10^18. Taking modulo 1000000007 gives 49.

Solution

def solution(startDay, endDay, filterCost, discountPrice):
    MOD = 1000000007

    if not startDay:
        return 0

    events = {}
    for s, e, c in zip(startDay, endDay, filterCost):
        events[s] = events.get(s, 0) + c
        events[e + 1] = events.get(e + 1, 0) - c

    total = 0
    active_cost = 0
    prev_day = None

    for day in sorted(events):
        if prev_day is not None:
            days = day - prev_day
            total = (total + days * min(active_cost, discountPrice)) % MOD
        active_cost += events[day]
        prev_day = day

    return total % MOD

Time complexity: O(n log n). Space complexity: O(n).

Hints

The choice for one day does not affect any other day. If you know the total active processing cost on a day, that day's contribution is simply min(totalActiveCost, discountPrice).
Do not iterate through every day. Track how the total active daily cost changes only at startDay[i] and endDay[i] + 1, then sweep through the sorted event days.

Quick Overview

This question evaluates a candidate's competence in algorithm design and optimization, including interval-based cost aggregation and modular arithmetic for large-number results within the Coding & Algorithms domain.