TIP102 Unit 3 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
explorers
and supplies
, where explorers[j]
represents the preference of the j
th explorer, and supplies[i]
represents the type of the i
th resource in the stack.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
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