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.

• 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.

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.

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