Validate Animal Sheltering Sequence - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 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 two integer arrays admitted and adopted, each containing distinct values representing animals in an animal shelter.
• Q: What is the output?
  • A: The output is a boolean value True if the adopted sequence could be the result of admitting and adopting animals in the shelter according to the admitted sequence, or False otherwise.
• Q: How should the sequences be validated?
  • A: The validation should determine if the adopted sequence can be achieved by pushing animals onto a stack (admitting them) and then popping them off the stack (adopting them) in the given order.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to simulate the sheltering process. Push animals onto the stack as they are admitted, and pop them off the stack when they match the next animal in the adopted sequence. If the entire adopted sequence can be matched in this way, return True; otherwise, return False.

1. Initialize an empty stack and a pointer `j` set to `0` to track the current position in the `adopted` sequence.
2. Iterate over each animal in the `admitted` list:
   1. Push the current animal onto the stack (admitting the animal).
   2. While the stack is not empty and the top of the stack matches the current animal in the `adopted` sequence:
      * Pop the top animal from the stack (adopting the animal).
      * Move the `j` pointer to the next position in the `adopted` sequence.
3. After processing all animals in the `admitted` list, check if all animals in the `adopted` list have been matched (i.e., `j` has reached the end of the `adopted` list).
4. Return `True` if all animals in the `adopted` list have been matched; otherwise, return `False`.

⚠️ Common Mistakes

• Failing to correctly manage the stack operations, leading to incorrect validation of the sequence.
• Not accounting for the case where the adopted sequence cannot be achieved with the given admitted sequence.
• Mismanaging the pointer j, which tracks the position in the adopted sequence.

I-mplement

def validate_shelter_sequence(admitted, adopted):
    stack = []
    j = 0  # Pointer for the adopted list
    
    for animal in admitted:
        stack.append(animal)  # Admit the animal (push onto stack)
        
        # While the top of the stack matches the next animal to be adopted, pop the stack
        while stack and stack[-1] == adopted[j]:
            stack.pop()
            j += 1
    
    # If we have matched all animals in the adopted list, return True
    return j == len(adopted)

# Example usage
print(validate_shelter_sequence([1,2,3,4,5], [4,5,3,2,1]))  # Output: True
print(validate_shelter_sequence([1,2,3,4,5], [4,3,5,1,2]))  # Output: False