Manage Food Waste - codepath/compsci_guides GitHub Wiki

Unit 4 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 goal of the problem?
  • A: The goal is to determine if the total food waste in a queue decreases over time as records are processed.
• Q: What are the inputs?
  • A: The input is a list of tuples, where each tuple contains a date (in the format "YYYY-MM-DD") and an integer representing the amount of food wasted on that date.
• Q: What are the outputs?
  • A: The output is a boolean value: True if the food waste decreases over time as records are processed, and False otherwise.
• Q: How should the waste reduction be managed?
  • A: Use a queue to process the waste records and check if each subsequent waste amount is less than the previous one.
• Q: Are there any assumptions about the input?
  • A: The list of waste records is well-formed, sorted by date, and contains valid date strings and non-negative integers.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a queue to simulate processing the waste records in the order they are provided. Compare each waste amount with the previous one to check for a decreasing trend.

1) Initialize a queue with the `waste_records`.
2) If the queue is empty, return `True` since no trend can be identified.
3) Dequeue the first element and store its waste amount in `previous_waste`.
4) While the queue is not empty:
   a) Dequeue the next element and compare its waste amount with `previous_waste`.
   b) If the current waste amount is not less than `previous_waste`, return `False`.
   c) Update `previous_waste` with the current waste amount.
5) If all records show a decreasing trend, return `True`.

**⚠️ Common Mistakes**

- Forgetting to correctly dequeue elements from the queue, which could lead to incorrect comparisons.
- Assuming that the queue will always have multiple records, not handling the case of a single record or an empty list.
- Misunderstanding the input format, leading to incorrect processing of the records.

I-mplement

from collections import deque

def manage_food_waste_with_queue(waste_records):
    # Initialize a queue with the waste records
    waste_queue = deque(waste_records)

    # Check if there are no records
    if not waste_queue:
        return True  # No trend can be identified if there are no records

    # Initialize the previous waste amount with the waste of the first record
    previous_waste = waste_queue.popleft()[1]

    # Process each record in the queue
    while waste_queue:
        current_waste = waste_queue.popleft()[1]
        # If the current waste is not less than the previous waste, the trend is not reducing
        if current_waste >= previous_waste:
            return False
        # Update previous waste amount for the next comparison
        previous_waste = current_waste

    return True

Example Usage:

waste_records_1 = [
    ("2024-08-01", 150),
    ("2024-08-02", 120),
    ("2024-08-03", 100),
    ("2024-08-04", 80),
    ("2024-08-05", 60)
]

waste_records_2 = [
    ("2024-08-01", 150),
    ("2024-08-02", 180),
    ("2024-08-03", 160),
    ("2024-08-04", 140),
    ("2024-08-05", 120)
]

print(manage_food_waste_with_queue(waste_records_1))  
# Output: True

print(manage_food_waste_with_queue(waste_records_2))  
# Output: False