Number of Explorers Unable to Gather Supplies - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Standard (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 explorers and supplies, where explorers[j] represents the preference of the jth explorer, and supplies[i] represents the type of the ith resource in the stack.
• Q: What is the output?
  • A: The output is the number of explorers that are unable to gather their preferred supplies.
• Q: How are the supplies and explorers matched?
  • A: If the explorer at the front of the queue prefers the resource on top of the stack, they take it and leave the queue. If not, they go to the end of the queue. The process continues until no explorer in the queue wants to take the top resource.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a queue to manage the explorers and simulate the process of checking whether they can collect their preferred supplies. The process continues until either all explorers have gathered their supplies or no more matches can be made.

1. Convert the `explorers` array into a deque (double-ended queue) to efficiently manage the order of explorers.
2. Iterate over each supply in the `supplies` array:
   1. For each supply, check the explorers in the queue:
      * If the explorer at the front of the queue prefers the current supply, remove them from the queue.
      * If they do not prefer the supply, move them to the end of the queue.
   2. If no explorer wants the current supply after checking all, stop the process.
3. Return the number of explorers remaining in the queue.

⚠️ Common Mistakes

• Incorrectly managing the queue, leading to an infinite loop or incorrect number of explorers being unable to gather supplies.
• Not properly breaking out of the loop when no explorer matches the current supply, which could result in unnecessary iterations.
• Misunderstanding the process of matching explorers with supplies, leading to incorrect results.

I-mplement

from collections import deque

def count_explorers(explorers, supplies):
    explorer_queue = deque(explorers)
    
    for supply in supplies:
        size = len(explorer_queue)
        matched = False
        
        for _ in range(size):
            explorer = explorer_queue.popleft()
            if explorer == supply:
                matched = True
                break
            else:
                explorer_queue.append(explorer)
                
        if not matched:
            break

    return len(explorer_queue)

# Example usage
print(count_explorers([1, 1, 0, 0], [0, 1, 0, 1]))  # Output: 0
print(count_explorers([1, 1, 1, 0, 0, 1], [1, 0, 0, 0, 1, 1]))  # Output: 3