Find Closest NFT Values - codepath/compsci_guides GitHub Wiki

Unit 4 Session 1 Standard (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 structure of the input?

  • A: The input is a sorted list of NFT values (floats) and a budget (float).

• Q: What is the output?

  • A: The output is a tuple containing two values: the closest NFT value below or equal to the budget, and the closest NFT value above or equal to the budget.

• Q: What happens if the budget is exactly equal to one of the NFT values?

  • A: The exact match should be returned as both the closest below and closest above values.

• Q: What should be returned if the budget is lower than the smallest value or higher than the largest value in the list?

  • A: If the budget is lower, the closest below value should be None. If the budget is higher, the closest above value should be None.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a binary search approach to efficiently find the closest values. Track the closest value below or equal to the budget and the closest value above or equal to the budget.

1) Initialize `left` at the start of the list and `right` at the end of the list.
2) Initialize `closest_below` and `closest_above` to `None`.
3) While `left` is less than or equal to `right`:
   a) Calculate the middle index `mid`.
   b) If `nft_values[mid]` is equal to the budget, return it as both `closest_below` and `closest_above`.
   c) If `nft_values[mid]` is less than the budget, update `closest_below` and move `left` to `mid + 1`.
   d) If `nft_values[mid]` is greater than the budget, update `closest_above` and move `right` to `mid - 1`.
4) Return the tuple `(closest_below, closest_above)`.

**⚠️ Common Mistakes**

- Not handling edge cases where the budget is outside the range of the list values.
- Mismanaging the binary search pointers, leading to incorrect results or infinite loops.

I-mplement

def find_closest_nft_values(nft_values, budget):
    left = 0
    right = len(nft_values) - 1
    closest_below = None
    closest_above = None

    while left <= right:
        mid = (left + right) // 2
        if nft_values[mid] == budget:
            return (nft_values[mid], nft_values[mid])
        elif nft_values[mid] < budget:
            closest_below = nft_values[mid]
            left = mid + 1
        else:
            closest_above = nft_values[mid]
            right = mid - 1

    return (closest_below, closest_above)