Hackbright Code Challenges

Largest Smaller Than: Solution

Largest Smaller Than: Solution

Problem

Largest Smaller Than

Whiteboard

Easier

Concepts

Loops, Lists, Conditionals

Download

largest-smaller-than-solution.zip


The idea here is to ask the right questions in order to figure out what is required.

largest_smaller_than.py
def find_largest_smaller_than(nums, xnumber):
    """Find largest number in sorted list that is smaller than given number."""

    # START SOLUTION

    # Fail-fast optimization: since our list is sorted, if the first number
    # is bigger, a smaller number isn't in our list

    if nums[0] >= xnumber:
        return None

    # Optimization: if the last number isn't too big, it's the answer

    if nums[-1] < xnumber:
        return len(nums) - 1

    # Else, loop through and return the index right before the first number
    # that is too big

    for i, num in enumerate(nums):
        if num >= xnumber:
            return i-1

This has O(n) runtime; there are two cases where it can get out of the loop fast, but it still scales with n.

Advanced: Can you find a better runtime for this? There is an O(log n) solution.

Advanced Solution

Given that our list is sorted, we can search it more quickly than having to scan each item. Instead, we can use the principle of binary search to search it.

We could write the binary search code ourself, but Python has a built-in library, bisect, that does this for us.

largest_smaller_than.py
def find_largest_smaller_than_bisect(nums, xnumber):
    """Find largest number in sorted list that is smaller than given number.

    Advanced version:
        Since we have a list, we can search it quickly using binary search.
        Python has a nice library, `bisect`, that can do that.

    For example:

        >>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], 10)
        2

        >>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], 33)
        4

        >>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], -1)
        1

    Never find xnumber --- it's not smaller than itself!

        >>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], 8)
        1

    If no such number exists, return None:

        >>> find_largest_smaller_than_bisect([-5, -2, 8, 12, 32], -10) is None
        True
    """

    from bisect import bisect_left

    # Fail-fast optimization: since our list is sorted, if the first number
    # is bigger, a smaller number isn't in our list

    if nums[0] > xnumber:
        return None

    insertion_point = bisect_left(nums, xnumber)

    return insertion_point - 1

    if nums[insertion_point] == xnumber:
        return insertion_point - 1

    else:
        return insertion_point