Blueprint Approval Process - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the input to the problem?
    • A: The input consists of a list of integers blueprints, where each integer represents the complexity level of a blueprint.
  • Q: What is the output?
    • A: The output is a list of integers representing the order in which the blueprints are approved, sorted by increasing complexity.
  • Q: How should the blueprints be processed?
    • A: Blueprints should be approved in order of increasing complexity, meaning that simpler (lower complexity) blueprints are approved before more complex ones.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the list of blueprints by complexity and then process each blueprint in that order using a queue to simulate the approval process.

1. Sort the list `blueprints` in ascending order based on their complexity levels.
2. Initialize a queue (using `deque`) and append each sorted blueprint to the queue.
3. Initialize an empty list `approved` to keep track of the order of approved blueprints.
4. While the queue is not empty:
   1. Remove the first blueprint from the queue and add it to the `approved` list.
5. Return the `approved` list, which contains the blueprints in the order they were approved.

⚠️ Common Mistakes

  • Forgetting to sort the blueprints by complexity before processing them.
  • Misunderstanding the use of a queue to manage the approval process.

I-mplement

from collections import deque

def blueprint_approval(blueprints):
    queue = deque()
    for blueprint in sorted(blueprints):
        queue.append(blueprint)

    approved = []
    while queue:
        approved.append(queue.popleft())

    return approved

# Example usage
print(blueprint_approval([3, 5, 2, 1, 4]))  # Output: [1, 2, 3, 4, 5]
print(blueprint_approval([7, 4, 6, 2, 5]))  # Output: [2, 4, 5, 6, 7]