Minimum Cost to Process Priority Tasks
Updated
Problem statement
A CPU must process n tasks numbered 1 to n. The tasks listed in priorityTasks are priority tasks. The CPU works on contiguous groups of tasks, starting with the group of all n tasks:
- Normal processing: a group with no priority task costs
normalTime, whatever its size. - Priority processing: a group with priority tasks can be processed directly for
priorityTime × count × length, wherecountis the number of priority tasks in the group andlengthis the number of tasks in the group. - Splitting: instead, a group with more than one task may be split into two equal halves (the first half and the second half), and each half is processed the same way. Splitting itself costs nothing.
n is a power of two, so every split is exact. Return the minimum total time to process all n tasks.
Function
minProcessingTime(n: int, priorityTasks: int[], normalTime: int, priorityTime: int) → longExamples
Example 1
n = 4priorityTasks = [1,3]normalTime = 1priorityTime = 2return = 6- Processing all four tasks at once costs
2 × 2 × 4 = 16. - Splitting into
[1, 2]and[3, 4]: each half has one priority task. Directly each costs2 × 1 × 2 = 4, but splitting again gives[1](cost2 × 1 × 1 = 2) and[2](no priority task, cost 1), so 3 per half. - The total is
3 + 3 = 6.
Example 2
n = 8priorityTasks = []normalTime = 5priorityTime = 3return = 5- There are no priority tasks, so processing all 8 tasks as one group costs
normalTime = 5.
Example 3
n = 2priorityTasks = [1,2]normalTime = 10priorityTime = 1return = 2- Directly:
1 × 2 × 2 = 4. Split:1 + 1 = 2. The answer is 2.
Constraints
n = 2mfor some integer0 <= m <= 20, so1 <= n <= 220.0 <= priorityTasks.length <= 2 × 1041 <= priorityTasks[i] <= n, and all values inpriorityTasksare distinct.1 <= normalTime, priorityTime <= 104
More Microsoft Online Assessment questions
- Most Visited Sprint MarkerOA · Seen Nov 2026
- Maximum Escape Game ScoreOA · Seen Nov 2026
- Count Subarrays with a Perfect-Square ProductOA · Seen Nov 2026
- Maximum Interactive Team SizeOA · Seen Nov 2026
- Maximize Pipeline Throughput Under a Scaling BudgetOA · Seen Nov 2026
- Minimum Cost K-Capable ModelsOA · Seen Nov 2026
- Find Available Meeting RoomsOA · Seen Oct 2026
- Maximum Sum of a K-StarOA · Seen Oct 2026
- Capacity to Ship Packages Within DaysOA · ONSITE INTERVIEW · Seen Oct 2026
- Count Digit Replacements with No Equal Adjacent DigitsOA · Seen Oct 2026
Similar questions at other companies
- AVL Insertion and RotationsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Delete Node in a BSTBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Node in a BSTTokopedia · PHONE SCREENTokopedia interview questions
- Recursive Binary SearchEPAM · ONSITE INTERVIEWEPAM interview questions
- Out-of-Order Bank Ledger BalancesPerplexity AI · OAPerplexity AI interview questions
- Server Upgrade PlanningWells Fargo · OAWells Fargo interview questions
- Find Minimum TimeAlphaSense · OA
- Subscription and Usage-Based Billing CalculatorStripe · OAStripe interview questions
- Find Minimum TimeBlackRock · OABlackRock interview questions
- Perfect Squares Matching a PatternNielsen · OA
Microsoft interview experiences
- Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
- Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
- Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
- Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
- Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
- Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)