Library Late Fee Calculator - Solution & Explanation

Problem Overview: You receive borrowing or return information for library books and must compute the total late fee according to the library's rules. The task is mainly about correctly applying the fee policy for each record and summing the result.

Approach 1: Direct Simulation (O(n) time, O(1) space)

The most natural solution is to simulate the fee calculation exactly as described. Iterate through the array of borrowing records, compute how many days each book was returned late, and apply the fee rule for that record. Each iteration performs constant work: compare dates or day counts, compute the overdue duration, and multiply by the per‑day penalty if the book is late.

This approach works well because the problem has no complicated dependencies between entries. Each record can be processed independently, which means a single pass over the input is sufficient. The time complexity is O(n) since you process each entry once, and the space complexity is O(1) because you only maintain a running total of fees.

The implementation is essentially a straightforward simulation. You replicate the real‑world rules programmatically: determine if the return date exceeds the allowed period, compute the overdue days, and accumulate the corresponding fee. This pattern shows up frequently in easy interview problems where the focus is correct rule handling rather than algorithmic optimization.

Approach 2: Structured Fee Calculation with Precomputed Rules (O(n) time, O(1) space)

If the fee policy contains multiple tiers (for example, different rates after certain day thresholds), you can encode those rules into simple condition checks or a small lookup structure. During iteration, determine the overdue duration and map it to the correct fee calculation logic.

This still processes each record exactly once, so the time complexity remains O(n). Space complexity stays O(1) because the rule set is fixed and small. The benefit of structuring the rules explicitly is cleaner code when fee policies contain several conditions or thresholds.

This version still relies on simulation of the rules but organizes the logic to make extensions easier. In production systems, fee policies often change, so separating rule logic from the main loop improves maintainability.

Recommended for interviews: The direct simulation approach is exactly what interviewers expect. It demonstrates that you can read problem constraints carefully and implement rule-based logic correctly. Mentioning that each record is independent and therefore solvable in a single pass shows good algorithmic reasoning, even though the implementation is simple.