Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogle

Minimum Cost for Tickets

Choose your preparation mode4 modes available
</>
IDE
def mincostTickets(days: list[int], costs: list[int]) -> int:public int mincostTickets(int[] days, int[] costs)int mincostTickets(vector<int> days, vector<int> costs)function mincostTickets(days, costs)
def mincostTickets(days, costs):
    # Write your solution here
    pass
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int mincostTickets(vector<int> days, vector<int> costs) {
    // Write your solution here
    return 0;
}
function mincostTickets(days, costs) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: 14Summing only 1-day passes without considering longer passes.✅ At each day, compute min cost among 1-day, 7-day, and 30-day passes covering that day.
Wrong: 0Not handling empty input or base case properly.✅ Return 0 if days array is empty.
Wrong: 9Off-by-one error in coverage calculation causing undercoverage.✅ Ensure pass covers days[i] through days[i] + duration - 1 inclusive.
Wrong: Too slow / TLEBrute force recursion without memoization or optimization.✅ Implement memoization or bottom-up DP with binary search optimization.
Wrong: Incorrect cost due to 0/1 knapsack assumptionRestricting pass purchase to once instead of unbounded times.✅ Allow multiple purchases of same pass type in DP recurrence.
✓
Test Cases
t1_01basic
Input{"days":[1,4,6,7,8,20],"costs":[2,7,15]}
Expected11

Buy 1-day pass on day 1 (cost 2), 7-day pass on day 4 (cost 7) covering days 4-10, and 1-day pass on day 20 (cost 2). Total = 11.

t1_02basic
Input{"days":[1,2,3,4,5,6,7],"costs":[2,7,15]}
Expected7

Buying a 7-day pass for 7 covers all days at cost 7, cheaper than multiple 1-day passes (2*7=14).

t2_01edge
Input{"days":[],"costs":[2,7,15]}
Expected0

No travel days means no cost.

t2_02edge
Input{"days":[1],"costs":[2,7,15]}
Expected2

Single travel day; cheapest is 1-day pass costing 2.

t2_03edge
Input{"days":[1,2,3,4,5,6,7],"costs":[2,7,15]}
Expected7

Exact boundary test where 7-day pass covers all days exactly at cost 7.

t2_04edge
Input{"days":[1,15,30],"costs":[2,7,15]}
Expected6

Three 1-day passes cheaper than longer passes; tests unbounded vs 0/1 confusion.

t3_01corner
Input{"days":[1,2,3,4,5,6,7,8,9,10],"costs":[10,2,1]}
Expected1

1-day passes are expensive, 7-day pass very cheap; best to buy one 7-day pass and three 1-day passes or one 30-day pass is too expensive.

t3_02corner
Input{"days":[1,15,30],"costs":[2,7,15]}
Expected6

Three 1-day passes cheaper than longer passes; tests unbounded vs 0/1 confusion.

t3_03corner
Input{"days":[1,3,5,7,9],"costs":[3,8,20]}
Expected11

Tests off-by-one errors in coverage calculation; buying 1-day passes on days 1,3,5,7,9 costs 15, cheaper than 7-day or 30-day passes.

t4_01performance
Input{"days":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"costs":[2,7,15]}
⏱ Performance - must finish in 2000ms

n=100, O(n^2) brute force will TLE; efficient DP with memoization or binary search optimization required.

Practice

(1/5)
1. You need to split a positive integer n into at least two positive integers such that the product of these integers is maximized. Which algorithmic approach guarantees finding the optimal solution efficiently?
easy
A. Pure brute force recursion exploring all partitions without memoization
B. A greedy approach that always cuts the integer into 3s and 2s
C. Dynamic programming using bottom-up tabulation with state representing maximum product for each integer up to n
D. Divide and conquer by splitting the integer into two halves recursively without caching results

Solution

  1. Step 1: Understand problem structure

    The problem requires maximizing product by splitting an integer into parts, which naturally fits a DP approach where subproblems represent maximum product for smaller integers.
  2. Step 2: Evaluate options

    Greedy (always cutting 3s) fails on some inputs; brute force recursion is correct but inefficient; divide and conquer without memoization repeats work. Bottom-up DP tabulation efficiently computes all subproblems and combines results.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    DP tabulation ensures optimal substructure and overlapping subproblems [OK]
Hint: DP tabulation handles overlapping subproblems optimally [OK]
Common Mistakes:
  • Believing greedy always works for integer break
  • Ignoring memoization in recursion
2. Consider the following code for integer break. What is the value of dp[3] after the outer loop iteration i = 3 completes?
def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

print(integer_break(4))  # Output not asked here
easy
A. 2
B. 4
C. 3
D. 1

Solution

  1. Step 1: Trace dp for i=2

    dp[1] = 1 (given). For i=2, j=1: max_product = max(0, max(1,1)*max(1,1)) = 1, so dp[2] = 1.
  2. Step 2: Trace dp for i=3

    j=1: max_product = max(0, max(1,1)*max(2,dp[2])) = max(0,1*2) = 2 j=2: max_product = max(2, max(2,dp[2])*max(1,dp[1])) = max(2,2*1) = 2 So dp[3] = 2.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    dp[3] = 2 matches manual calculation [OK]
Hint: Trace inner loop carefully for each j [OK]
Common Mistakes:
  • Off-by-one in loop bounds
  • Confusing dp[i-j] with dp[j]
3. What is the time complexity of the space-optimized bottom-up 0/1 Knapsack algorithm when there are n items and the knapsack capacity is W?
medium
A. O(2^n)
B. O(n + W)
C. O(n * W)
D. O(n * log W)

Solution

  1. Step 1: Identify loops in the algorithm

    The algorithm has an outer loop over n items and an inner loop over capacities from W down to the item's weight, which can be up to W iterations.
  2. Step 2: Calculate total operations

    Multiplying the loops gives O(n * W) time complexity. Recursive brute force is exponential, and linear or logarithmic complexities are incorrect here.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Nested loops over n and W -> O(n * W) [OK]
Hint: Nested loops over items and capacity -> O(n * W) [OK]
Common Mistakes:
  • Confusing recursion stack space with time complexity.
4. The following code attempts to implement the space-optimized 0/1 Knapsack solution. Identify the line that contains a subtle bug that can cause incorrect results.
def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # Note: iterating forwards
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]
medium
A. Line 5: Inner loop iterating forwards over weights.
B. Line 4: Outer loop iterating over items.
C. Line 2: Initializing dp array with zeros.
D. Line 6: Updating dp[w] with max of current and new value.

Solution

  1. Step 1: Analyze iteration order in inner loop

    The inner loop iterates forwards from weights[i] to W, which causes the current item to be counted multiple times in the same iteration, violating 0/1 knapsack constraints.
  2. Step 2: Correct iteration direction

    Iterating backwards (from W down to weights[i]) ensures each item is only counted once per capacity, preserving correctness.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Forward iteration causes overcounting items [OK]
Hint: Inner loop must iterate backwards to avoid overcounting [OK]
Common Mistakes:
  • Iterating forwards in dp array updates for 0/1 knapsack.
5. The following code attempts to solve the minimum subset sum difference problem using space-optimized DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.
medium
A. Line 4: dp initialization without dp[0] = true
B. Line 6: Outer loop iterating over elements
C. Line 7: Inner loop iterating backwards from total_sum
D. Line 11: Returning difference using total_sum and w

Solution

  1. Step 1: Check base case initialization

    dp[0] must be true to represent sum zero achievable with empty subset; missing this causes no sums to be marked achievable.
  2. Step 2: Verify other lines

    Loops and return statement are correct; only missing dp[0] initialization breaks correctness.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without dp[0] = true, dp array never updates correctly [OK]
Hint: dp[0] = true is essential base case [OK]
Common Mistakes:
  • Forgetting dp[0] initialization
  • Using forward iteration causing overcounting
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard