Matching of Buyers with Sellers

TIP103 Unit 3 Session 2 (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 lists, 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.
• Q: What is the output?
  • A: The output is an integer representing the maximum number of transactions that can be made where each buyer can purchase from a seller if the buyer's gold is greater than or equal to the seller's price.
• Q: What are the constraints on transactions?
  • A: Each buyer can make at most one purchase, and each seller can sell their goods to at most one buyer.

P-lan

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 `buyer_ptr` to the next buyer — since sellers are sorted in ascending order, a buyer who cannot afford the cheapest remaining seller cannot afford any later seller either.
5. Continue this process until one of the lists is fully traversed.
6. Return the value of `matches` as the result.

⚠️ Common Mistakes

• Advancing the seller pointer when a buyer cannot afford the current seller's price — with both lists sorted in ascending order, that buyer cannot afford any later (more expensive) seller either, so it is the buyer pointer that must advance.
• Incorrectly updating the pointers, leading to potential infinite loops or incorrect counting of matches.

I-mplement

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:
            buyer_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