Manage Expiration Dates - 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 items in a stack are ordered correctly by their expiration dates, with the oldest expiration date at the top of the stack.
• Q: What are the inputs?
  • A: The input is a list of tuples, where each tuple contains a food item (as a string) and its expiration date (as a string in the format "YYYY-MM-DD").
• Q: What are the outputs?
  • A: The output is a boolean value: True if the items are correctly ordered by expiration date, and False otherwise.
• Q: How should the dates be compared?
  • A: The expiration dates should be compared as strings, since the format "YYYY-MM-DD" allows for correct chronological ordering using string comparison.
• Q: Are there any assumptions about the input?
  • A: The list is well-formed, with valid date strings and items in the correct format.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to simulate managing the food items by expiration dates. Compare the dates as they are popped from the stack to check if they are in the correct order.

1) Initialize an empty stack `expiration_stack`.
2) Push all expiration dates onto the stack.
3) Pop the first date from the stack and store it as `previous_date`.
4) While the stack is not empty:
   a) Pop the next date from the stack and store it as `current_date`.
   b) If `current_date` is greater than `previous_date`, return `False`.
   c) Update `previous_date` to `current_date`.
5) If all dates are in the correct order, return `True`.

**⚠️ Common Mistakes**

- Forgetting to correctly compare dates, which could lead to inaccurate results.
- Assuming that the stack will always have multiple elements, not handling the case of a single item or an empty stack.
- Misunderstanding the input format, leading to incorrect processing of the dates.

I-mplement

def check_expiration_order(expiration_dates):
    # Initialize an empty stack
    expiration_stack = []

    # Push all expiry dates onto the stack
    for item, date in expiration_dates:
        expiration_stack.append(date)

    # Initialize previous date with the first element popped from the stack
    previous_date = expiration_stack.pop()

    # Process each date in the stack (reverse order)
    while expiration_stack:
        current_date = expiration_stack.pop()
        # Check if the current date is earlier than or equal to the previous date
        if current_date > previous_date:
            return False
        # Update the previous date for the next comparison
        previous_date = current_date

    return True

Example Usage:

expiration_dates_1 = [
    ("Milk", "2024-08-05"),
    ("Bread", "2024-08-10"),
    ("Eggs", "2024-08-12"),
    ("Cheese", "2024-08-15")
]

expiration_dates_2 = [
    ("Milk", "2024-08-05"),
    ("Bread", "2024-08-12"),
    ("Eggs", "2024-08-10"),
    ("Cheese", "2024-08-15")
]

print(check_expiration_order(expiration_dates_1))  
# Output: True

print(check_expiration_order(expiration_dates_2))  
# Output: False