Smallest Difference

Challenge

Harder

Concepts

Algorithms, Runtime

Download

smallest-diff.zip

Solution

Smallest Difference: Solution

Credit: Adapted from a problem in Cracking the Coding Interview, 6th Edition. Gayle Laakmann McDowell, Career Cup (Palo Alto, CA). 2015.

This is a short-length challenge, but requires some clever thinking.

Given two lists, find the smallest difference between any two nums.

For example, given the lists:

[10, 20, 14, 16, 18]
[30, 23, 54, 33, 96]

The result would be 3, since 23 - 20 = 3 is the smallest difference of any pair of numbers in those lists.

We’ve given you a file, smallestdiff.py, with a function, smallest_diff:

def smallest_diff(a, b):
    """Return smallest diff between all items in a and b.

        >>> smallest_diff([10, 20, 30, 40], [15, 25, 33, 45])
        3
    """

However, this is not yet implemented.

Runtime

You must solve this with an algorithm that is faster than O(ab) —- that is, you cannot compare each item of list a against each item of list b (that would be O(ab) time).