TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
buyers
and sellers
. Each element in buyers
represents the amount of gold a buyer has, and each element in sellers
represents the price of goods a seller is offering.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Sort both the buyers and sellers lists. Then, use a two-pointer approach to match buyers with sellers in a greedy manner, maximizing the number of transactions.
1. Sort the `buyers` list in ascending order.
2. Sort the `sellers` list in ascending order.
3. Initialize two pointers `buyer_ptr` and `seller_ptr` to 0 and a counter `matches` to 0.
4. Iterate through both lists:
1. If the current buyer's gold is greater than or equal to the current seller's price, increment `matches`, and move both pointers to the next buyer and seller.
2. If the current buyer's gold is less than the current seller's price, move the `seller_ptr` to the next seller.
5. Continue this process until one of the lists is fully traversed.
6. Return the value of `matches` as the result.
⚠️ Common Mistakes
def match_buyers_and_sellers(buyers, sellers):
buyers.sort()
sellers.sort()
buyer_ptr, seller_ptr = 0, 0
matches = 0
while buyer_ptr < len(buyers) and seller_ptr < len(sellers):
if buyers[buyer_ptr] >= sellers[seller_ptr]:
matches += 1
buyer_ptr += 1
seller_ptr += 1
else:
seller_ptr += 1
return matches
# Example usage
buyers1 = [4, 7, 9]
sellers1 = [8, 2, 5, 8]
print(match_buyers_and_sellers(buyers1, sellers1)) # Output: 3
buyers2 = [1, 1, 1]
sellers2 = [10]
print(match_buyers_and_sellers(buyers2, sellers2)) # Output: 0