Extra Treats - 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 is a string votes where each character represents a volunteer's group affiliation: 'C' for "Cat Lovers" and 'D' for "Dog Lovers".
  • Q: What is the output?
    • A: The output is the name of the group ("Cat Lovers" or "Dog Lovers") that will ultimately announce victory and decide which pet receives extra treats.
  • Q: What rules govern the voting process?
    • A: In each round, volunteers can ban an opposing group member's vote or announce victory if all remaining voters are from the same group.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two queues to simulate the voting rounds. One queue tracks the positions of the "Cat Lovers" and the other for "Dog Lovers". In each round, compare the front of each queue. The volunteer whose position comes earlier in the string gets to ban the other, and the loser is delayed by adding their index plus the length of the string to the end of the queue.

1. Initialize two queues, `cat_queue` and `dog_queue`, to hold the indices of the 'C' and 'D' volunteers, respectively.
2. Populate the queues with the positions of each 'C' and 'D' in the `votes` string.
3. Process the queues until one is empty:
   1. Compare the front positions of both queues.
   2. The volunteer whose position is earlier bans the other (i.e., removes them from the queue).
   3. The winner of this round re-enters the queue at a position that simulates moving to the end of the voting sequence (index + len(votes)).
4. If `cat_queue` is empty, return "Dog Lovers"; if `dog_queue` is empty, return "Cat Lovers".

⚠️ Common Mistakes

  • Failing to correctly simulate the cyclical nature of the voting rounds.
  • Not properly managing the re-entry of volunteers into the queue.
  • Assuming the process ends too early without checking both queues.

I-mplement

from collections import deque

def predictAdoption_victory(votes):
    cat_queue = deque()
    dog_queue = deque()
    
    # Populate the queues with the initial positions of 'C' and 'D'
    for i, vote in enumerate(votes):
        if vote == 'C':
            cat_queue.append(i)
        else:
            dog_queue.append(i)
    
    # Process the queues until one of them is empty
    while cat_queue and dog_queue:
        cat_index = cat_queue.popleft()
        dog_index = dog_queue.popleft()
        
        # The earlier index gets to ban the later one
        if cat_index < dog_index:
            cat_queue.append(cat_index + len(votes))
        else:
            dog_queue.append(dog_index + len(votes))
    
    # Determine the winner
    return "Cat Lovers" if cat_queue else "Dog Lovers"

# Example usage
print(predictAdoption_victory("CD"))    # Output: "Cat Lovers"
print(predictAdoption_victory("CDD"))   # Output: "Dog Lovers"