Round 1
Questions: A lender lent money to a borrower, each day a different lender lent the money to the borrower. The borrower borrowed money on the jth day should pay back on the (j+1)th day to maintain good credit and avoid defaulting. The borrower can pay back the jth day loan from (j+1)th day’s borrowed money and can use the leftover money on that day. Find the maximum number of days the borrower can survive before defaulting.
- lender[i] -> ith lending amount
- payback[i] -> ith payback amount
Example:
n = 4,
lender = [4, 6, 1, 8]
payback = [7, 10, 3, 9]
Output: 3
Solution Explanation:
- Choose lender -> 1, so payback is 3.
- Choose lender -> 4, repay previous payback 3, hence remaining 4 - 3 = 1 (borrower spends it), the current payback is 7.
- Choose lender -> 8, repay previous payback 7, hence remaining 8 - 7 = 1 (borrower spends it), the current payback is 9.
- Left with lender -> 6, cannot repay previous payback which is 9, 9 > 6 hence default.
So the borrower can survive 3 days.
Few other test cases:
-
Testcase 2:
n = 3,
lender = [2, 1, 5]
payback = [2, 2, 5]
Output: 3 -
Testcase 3:
n = 4,
lender = [1, 1, 1, 2]
payback = [2, 2, 2, 3]
Output: 2
Candidate's Approach
I was trying a greedy approach:
- Zip lender and payback.
- Sort based on payback and for equal payback, sort based on lender.
- Iterate and check.
Later thought merge interval might work for it (ran out of time before I could complete the code):
- After step 1 and 2, just check if the lender of the next day if pre_paycheck <= current_lender -> days++ (update previous paycheck with current payback).
- Else ignore the current item and move to the next item.
For example:
lender = [1, 1, 1, 2]
payback = [2, 2, 2, 3]
Sorted array = [[1, 2], [1, 2], [1, 2], [2, 3]] -> output: 2 (i.e. [[1, 2], [2, 3]]).
I tried to solve it in my IDE after the test, and it passed the above test cases. Not sure if it will pass all test cases of the OA.
Interviewer's Feedback
No feedback provided.