Frontend School

Feature Release Planner

DSA
hard

Feature Release Planner

Hard
Dynamic Programming
Bitmask DP
Knapsack
Graph

Overview

As a product manager leading a software development team, you're tasked with planning the next release. Your goal is to deliver the maximum variety of features to customers, represented by distinct feature categories, while staying within a strict development budget. A key challenge is that some feature categories have prerequisites: certain other categories must be present in the release for features from a dependent category to be considered.

This problem requires you to optimize feature selection to maximize customer value (distinct categories) under financial and logical constraints, mirroring real-world product planning.

What you need to do / Task

Implement the maximizeDistinctFeatureCategories function that determines the maximum number of distinct feature categories that can be included in a release, given a list of available features and a total budget.

Your solution must:

  1. Identify and map all unique feature categories to integer indices for efficient processing.
  2. Correctly handle the cost of each feature and the overall budget constraint.
  3. Ensure that if a feature is selected, all its prerequisite categories are also satisfied (i.e., at least one feature from each prerequisite category must also be selected).
  4. Return the maximum count of distinct categories that can be achieved.

Input & output

Input:

  • features: An array of Feature objects. Each Feature object has the following structure:
    • id: string - A unique identifier for the feature.
    • cost: number - The development cost of this feature.
    • category: string - The category this feature belongs to.
    • prerequisites: string[] - An array of category names that must be present in the release for this feature to be considered.
  • budget: number - The total development budget available.

Output:

  • number - The maximum number of distinct feature categories that can be included in the release, adhering to the budget and all prerequisite rules.

Clarifications

  • If the features array is empty or no features can be acquired within the budget, return 0.
  • A feature can be selected independently if it has no prerequisites.
  • If multiple features belong to the same category, selecting any one of them satisfies that category. You should choose the cheapest combination to satisfy categories and their prerequisites.

Examples

1

Example 1

Input:

features = [ { id: "F1", cost: 10, category: "UI", prerequisites: [] }, { id: "F2", cost: 20, category: "Backend", prerequisites: [] }, { id: "F3", cost: 15, category: "Analytics", prerequisites: ["Backend"] } ], budget = 30

Output:

2

Note:

Categories: UI, Backend, Analytics. Mapped to 0, 1, 2.

  • To get UI (mask 1): F1 (cost 10).
  • To get Backend (mask 2): F2 (cost 20).
  • To get Analytics (mask 4): Requires Backend. F3 costs 15. Total for (Backend + Analytics) = F2 (20) + F3 (15) = 35. This is too expensive for the budget of 30.

Within budget 30:

  • We can get UI for 10 (1 category).
  • We can get Backend for 20 (1 category).
  • We can get UI + Backend for 10 (F1) + 20 (F2) = 30 (2 categories). This is the maximum number of distinct categories achievable.
2

Example 2

Input:

features = [ { id: "F_CORE", cost: 5, category: "Core", prerequisites: [] }, { id: "F_ADV", cost: 10, category: "Advanced", prerequisites: ["Core"] }, { id: "F_UTIL", cost: 8, category: "Utility", prerequisites: [] } ], budget = 15

Output:

2

Note:

Categories: Core, Advanced, Utility. Mapped to 0, 1, 2.

  • To get Core (mask 1): F_CORE (cost 5).
  • To get Advanced (mask 2): Requires Core. F_ADV costs 10. Total for (Core + Advanced) = F_CORE (5) + F_ADV (10) = 15.
  • To get Utility (mask 4): F_UTIL (cost 8).

Within budget 15:

  • We can get Core for 5 (1 category).
  • We can get Utility for 8 (1 category).
  • We can get Core + Advanced for 15 (2 categories). This is the maximum.
  • We can also get Core + Utility for 5 (F_CORE) + 8 (F_UTIL) = 13 (2 categories).
3

Example 3

Input:

features = [ { id: "F1", cost: 100, category: "UI", prerequisites: [] } ], budget = 50

Output:

0

Note:

The only feature F1 costs 100, which exceeds the budget of 50. No features can be selected, resulting in 0 distinct categories.

Constraints

Constraints & assumptions

  • 1 <= features.length <= 50
  • 1 <= budget <= 1000
  • 1 <= feature.cost <= 100
  • feature.category is a string with 1 <= category.length <= 20.
  • The total number of distinct categories across all features is between 1 and 15 (inclusive). This constraint is critical for bitmasking approaches.
  • feature.prerequisites: An array of category strings. 0 <= prerequisites.length <= 5. All prerequisite category strings will be valid categories present in at least one feature.
  • There are no circular dependencies among categories (e.g., Category A requires B, B requires C, C requires A is not possible).

Out of scope

  • Optimizing for specific feature IDs, only distinct categories matter.
  • Handling invalid input formats or negative costs/budgets.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies the maximum distinct categories under all constraints.
  • Dynamic Programming Application: Effective use of Dynamic Programming, specifically with bitmasking, to explore the state space.
  • Complexity Analysis: Understanding and managing the time and space complexity to fit within typical interview limits for hard problems.
  • Code Quality: Readability, maintainability, and clarity of the implementation.

Loading editor...