Bus Fare - Amazon Top Interview Questions

                        Solution in C++ :

const int TICKET_TYPE = 3;
const int price[TICKET_TYPE] = {2, 7, 25};
const int duration[TICKET_TYPE] = {1, 7, 30};

int solve(vector<int>& days) {
    vector<int> pts(TICKET_TYPE);
    int n = days.size();
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    auto get_day = [&](int idx) { return idx == 0 ? 0 : days[idx - 1]; };
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < TICKET_TYPE; ++j) {
            while (get_day(i) - get_day(pts[j] + 1) >= duration[j]) pts[j]++;
            dp[i] = min(dp[i], dp[pts[j]] + price[j]);
        }
    }
    return dp[n];
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] days) {
        return lowest(new int[days.length], days, 0);
    }

    public int lowest(int[] dp, int[] days, int i) {
        if (i >= days.length) {
            return 0;
        }

        if (dp[i] != 0) {
            return dp[i];
        }

        int beg = i + 1;

        return dp[i] = min(2 + lowest(dp, days, search(days, beg, days[i] + 1)),
                   7 + lowest(dp, days, search(days, beg, days[i] + 7)),
                   25 + lowest(dp, days, search(days, beg, days[i] + 30)));
    }

    int search(int[] days, int beg, int day) {
        while (beg < days.length && days[beg] < day) {
            beg++;
        }
        return beg;
    }

    public int min(int... args) {
        int min = args[0];
        for (int i = 1; i < args.length; i++) {
            min = Integer.min(min, args[i]);
        }
        return min;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, days):
        dp = [0] * (len(days) + 1)
        for i in range(len(days) - 1, -1, -1):
            one = bisect.bisect_left(days, days[i] + 1)
            seven = bisect.bisect_left(days, days[i] + 7)
            thirty = bisect.bisect_left(days, days[i] + 30)
            dp[i] = min(2 + dp[one], 7 + dp[seven], 25 + dp[thirty])
        return dp[0]