Matching of Buyers with Sellers - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 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 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 `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

• Failing to correctly handle the case where a buyer cannot afford the current seller's price, which requires skipping to the next seller.
• 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:
            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