How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Maximize Chef Assignment Profit | DoorDash Coding Question

Maximize Chef Assignment Profit

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given three integer arrays: - `chefSkill[i]`: the skill level of the `i`-th chef. - `dishDifficulty[j]`: the difficulty level required to cook the `j`-th dish. - `dishProfit[j]`: the profit earned by cooking the `j`-th dish. Each chef can cook at most one dish. A chef can cook dish `j` only if `chefSkill[i] >= dishDifficulty[j]`. Multiple chefs are allowed to cook the same dish independently, and each cooking earns the full profit for that dish. Return the maximum total profit obtainable by assigning each chef to at most one dish. Example: ```text chefSkill = [1, 2, 3] dishDifficulty = [1, 2, 3] dishProfit = [1, 2, 3] ``` The maximum total profit is `1 + 2 + 3 = 6`. Follow-up: Suppose you want to build an array `bestProfitByDifficulty` where index `d` represents a difficulty level and `bestProfitByDifficulty[d]` stores the maximum profit of any dish that a chef with skill level `d` can cook. Given `dishDifficulty` and `dishProfit`, describe how you would generate this array.

Quick Answer: This question evaluates skill in array manipulation, data preprocessing, and algorithmic optimization for matching resources to tasks and aggregating profits.

Part 1: Maximum Total Profit from Chef Assignments

You are given three integer arrays: `chefSkill`, `dishDifficulty`, and `dishProfit`. A chef can cook at most one dish, and chef `i` can cook dish `j` only if `chefSkill[i] >= dishDifficulty[j]`. Multiple chefs are allowed to cook the same dish independently, and each chef earns the full profit of the dish they cook. Return the maximum total profit obtainable if each chef chooses the most profitable dish they can cook.

Constraints

0 <= len(chefSkill) <= 100000
0 <= len(dishDifficulty) == len(dishProfit) <= 100000
0 <= chefSkill[i], dishDifficulty[j], dishProfit[j] <= 1000000000
The total profit may exceed 32-bit integer range.

Examples

Input: ([1, 2, 3], [1, 2, 3], [1, 2, 3])

Expected Output: 6

Explanation: Each chef can cook the dish with the matching difficulty, so the total is 1 + 2 + 3 = 6.

Input: ([5, 5, 5], [2, 4], [10, 50])

Expected Output: 150

Explanation: All three chefs can cook the difficulty-4 dish worth 50 profit, and the same dish can be reused.

Input: ([4, 2, 8], [2, 4, 2, 6], [10, 20, 15, 25])

Expected Output: 60

Explanation: Best profits are: skill 4 -> 20, skill 2 -> 15, skill 8 -> 25. Total = 60.

Input: ([1, 1], [2, 3], [10, 20])

Expected Output: 0

Explanation: No chef has enough skill to cook any dish.

Input: ([], [1, 2], [10, 20])

Expected Output: 0

Explanation: With no chefs, the total profit is 0.

Hints

If you sort dishes by difficulty, you can track the best profit seen so far as difficulty increases.
If you also sort the chefs by skill, you can scan through the dishes only once.

Part 2: Build Best Profit by Difficulty Array

You are given two integer arrays: `dishDifficulty` and `dishProfit`. Build and return an array `bestProfitByDifficulty` such that for every difficulty `d`, `bestProfitByDifficulty[d]` is the maximum profit of any dish with difficulty at most `d`. The returned array should cover every difficulty from `0` to `max(dishDifficulty)` inclusive. If there are no dishes, return `[0]`.

Constraints

0 <= len(dishDifficulty) == len(dishProfit) <= 100000
0 <= dishDifficulty[j] <= 200000
0 <= dishProfit[j] <= 1000000000

Examples

Input: ([1, 2, 3], [1, 2, 3])

Expected Output: [0, 1, 2, 3]

Explanation: At each difficulty, the best available profit is the largest profit among dishes up to that difficulty.

Input: ([2, 4, 2, 5], [10, 20, 15, 5])

Expected Output: [0, 0, 15, 15, 20, 20]

Explanation: Difficulty 2 has two dishes, so keep the better profit 15. Then apply prefix maxima.

Input: ([1, 3, 5], [10, 5, 7])

Expected Output: [0, 10, 10, 10, 10, 10]

Explanation: Even though later dishes are less profitable, the prefix maximum keeps the best value seen so far.

Input: ([0, 2], [5, 1])

Expected Output: [5, 5, 5]

Explanation: A difficulty-0 dish is available, so every difficulty from 0 to 2 can achieve at least profit 5.

Input: ([], [])

Expected Output: [0]

Explanation: No dishes means the result is defined as [0].

Hints

First store the best profit for each exact difficulty value.
Then sweep from left to right and turn the array into a prefix maximum array.

Quick Overview

This question evaluates skill in array manipulation, data preprocessing, and algorithmic optimization for matching resources to tasks and aggregating profits.