Gift Card Satisfaction FAANG Python Interview Question

Imagine you're a VP at FAANG, and you want to reward your team with gifts at the end of the year during Christmas time. You check in with stingy HR, and the best they could do is scrounge up a limited set of gift cards – each with different values and to various stores.

Each teammate has different expectations for their end-of-year gift – your Director expects a $1000+ gift card for something luxurious, while the new grad on your team would be thrilled with something as simple as a $10 gift card to Starbucks.

You can only give each person at most one gift card, and if a gift card doesn’t meet someone’s minimum expectation, it’s better not to give them one at all, as we definitely don't want to disappoint.

Find a way to satisfy as many teammates as possible by assigning each one a gift card that meets or exceeds their expectation.

Return the maximum number of teammates you can make satisfy.

Example #1

Input:
Expectations = , Cards =

Output:

Explanation:

• The team member expecting $5 can be satisfied with the $10 gift card.
• The team member expecting $20 is satisfied with the $100 card.
• Unfortunately, your Director, expecting a $1000 gift card, will have to wait – nothing in stock would satisfy their high standards!

Example #2

Input:
Expectations = , Cards =

Output:

Explanation:

• None of the available gift cards can satisfy any expectations, as even the lowest is $10, while the highest card is just $9. Looks like everyone will be going home empty-handed!

Intuition

To maximize the number of satisfied team members, we want to match lower-value gift cards with teammates who have lower expectations. This lets us reserve the higher-value gift cards for those who need more to feel satisfied, while still using each card effectively.

Approach

1. By sorting both the and the , we can start with the smallest expectations and try to meet them with the smallest available cards.
2. Use two pointers, one for and one for . Starting from the smallest values, check if a gift card meets or exceeds a teammate's expectation:
   • If the gift card is big enough, we satisfy that teammate by moving to the next expectation (increment the pointer) and the next card (increment the pointer).
   • If the gift card is too small, we move to the next card only.
3. Each time we find a card that satisfies a teammate, we increase our satisfaction count.

This approach is efficient because sorting takes $O(n \log n)$ and we only pass through each list once with the two pointers.

Here’s the implementation:

Alternative without an Extra Variable

Instead of using a separate variable, we can simply return the as it will equal the number of satisfied teammates: