Greedy Algorithms - Two City Scheduling
Given the following memoization cache state for Two City Scheduling at i=3, a_count=1 with memo[(3,1)] = 250, what could be the original costs input for the first 4 people?
Given the following memoization cache state for Two City Scheduling at i=3, a_count=1 with memo[(3,1)] = 250, what could be the original costs input for the first 4 people?
hard🔄 Reverse Engineer Q9 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand memo meaning
memo[(3,1)] = 250 means minimum cost after assigning first 3 people with 1 assigned to city A.Step 2: Match costs to memo state
[[10,20],[200,30],[50,400],[20,30]] matches cost pattern where assigning second person to city B (200,30) and third to city B (50,400) leads to total 250 at this state.Final Answer:
Option C -> Option CQuick Check:
Only [[10,20],[200,30],[50,400],[20,30]] matches memo cost and assignment counts [OK]
Quick Trick: Match memo state with partial assignments and costs [OK]
Common Mistakes:
MISTAKES- Ignoring assignment counts in memo
- Confusing cost order
- Assuming memo stores total cost for all people
Trap Explanation:
PITFALL- Candidates often fail to reason backward from memo to input costs.
Interviewer Note:
CONTEXT- Tests deep understanding of DP memoization states
Master "Two City Scheduling" in Greedy Algorithms
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Greedy Algorithms Quizzes