Let's see an example of exercise you can face during a job interview, and let's use it to understand some concepts about code optimization, time complexity and the famous Big-O notation (essentially: how long it takes to execute your program for larger inputs expressed in terms of the inputs length)

Here is the challenge:

The first approach

So let's start with the first idea which comes to your mind: iterate over all the message letters and see if you can find all of them in the soup (removing from the soup the letter after every match).

def run2(message, bowl):
    # O(n)
    for l in message:
        try:
            # O(m)
            bowl.remove(l.upper())
        except ValueError:
            print('No!')
            return False
    print('Yes!')
    return True

Very simple, and easy to read. At line 6, the remove funcion will remove the message letter from the bowl, but if it doesn't find it, it raises a ValueError, meaning the message cannot be composed, though we return False.

The problem with such implementation is that when the message is long, and the bowl contains many and many characters, the execution time will increase a lot. How can we measure the execution time in relation to the length of the message and the number of letters included in the bowl?

We can use the Big-O notation: "a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity".

So let's examine our code:

• line 3: we loop through each letter of the message. Given the message length n, it means that the number of iterations will be n.
• line 6: we remove the first occurence of a letter from the bowl. Internally the remove function uses a loop also; let's suppose it finds the given element at index X, then it has to shift all remaining items: SIZE - X, so it'll take X + SIZE - X steps, in other words the execution time will be O(m), where m represents the number of letters in the bowl. 
• Since the letter is removed from the bowl, at the next iteration the bowl has (m-1) elements.

Given the points above, let's try to calculate the time complexity: for the first message letter we have m iterations, for the second m-1, then m-2... until m-n, and we need to sum all these contributions:

\[TC = m + (m - 1) + (m - 2) + ... + (m - n)\]

\[TC = mn - \sum_{k=1}^{n} (k)\]

The series above can be rewritten:

\[TC = mn - \frac{n(n + 1)}{2}\]

which leds to

\[TC = \frac{2mn - n^2 - n}{2}\]

Now, let's do something we, physics, appreciate a lot: simplification. For large numbers n*n is so much greater than n, that n can be ignored.

\[TC = mn - \frac{n^2}{2}\]

Now, if n == m

\[TC = \frac{n^2}{2} = O(n^2) = O(m*n)\]

While if the bowl contains many more letters than the message m >> n, let's say 10e9 against 10e3 we have:

\[TC = 10^9 * 10^3 - \frac{10^6}{2}\]

\[TC = 10^{12} - \frac{10^6}{2} \approx 10^{12} = m * n\]

So we can say that in such case our time complexity is O(m*n)

Basically we have the same complexity of two nested loops (and in fact we have two nested loops, but the second having a dynamic length). And using nested loops when dealing with big inputs is never a good idea.

We should try to find a solution that doesn't need nested loops and that can grow linearly with the input length.

Frequency histograms to the rescue!

Idea: it is better to loop many times through n or m items and sum each contribution instead of nesting loops multiplying their contributions.

Let's consider this code:

def run2(message, bowl): 
    fm = {}
    # O(n)
    for l in message:
        l = l.upper()
        if not fm.get(l, False):
            fm[l] = 0
        fm[l] += 1

    fb = {}
    # O(m)
    for l in bowl:
        if not fb.get(l, False):
            fb[l] = 0
        fb[l] += 1

    # O(26)
    for k in fm:
        try:
            if fb[k] < fm[k]:
                raise Exception()
        except:
            print('No!')
            return False

    print('Yes!')
    return true

The idea is simple, even if it is not the first approach that comes to your mind: we don't want to nest loops, ok, so we perform a first loop creating a dictionary which contains the frequencies of all the characters of the message, i.e. A: 20, B: 1, C: 3...
Then we do the same thing for the bowl. And finally we loop through the message dictionary and check if the bowl dictionary contains enough X letters to compose the message for every X being a letter of the message.

The first loop has a complexity of O(n), the second of O(m) and the last one of O(26) because we have al most 26 chars (accessing an array element has a time complexity of O(1)).

Cool, so what's the result?

\[TC = O(n) + O(m) + O(26) = O(m) + O(n)\]

And for m >> n

\[TC = O(m)\]

This is a better solution, we have a linear dependency instead of a quadratic one, cool!

Now the final touch: let's make this function more pythonic, also let's consider side cases, when we can exit before filling all the histograms, and maybe the bowl histogram is not needed anymore ;)

def runFTW(message, bowl):
    # O(n)
    tot = len(message)
    # O(n)
    fm = defaultdict(int)
    for l in message:
        fm[l.upper()] += 1

    # O(m)
    for l in bowl:
        if fm[l] > 1
            fm[l] -= 1
            tot -= 1
        if tot == 0:
            print('Yes')
            return True

    print('No!')
    return False

Time complexity:

\[TC = O(n) + O(n) + O(m) = O(2n) + O(m) = O(n) + O(m)\]

Oh well, some considerations:

• line 3: we keep track of the total number of letters of the message we still have to check, this allow us to exit from the function immediately if we find all the needed letters, without continuing adding bowl frequencies which will not be used
• line 5: we use the python defaultdict class because "when each key is encountered for the first time, it is not already in the mapping; so an entry is automatically created"
• line 10: looping through the bowl letters, every time we find any letter contained in the message, we decrease the message letter frequency (if still greater than one), we descrease the total number of letters remaining in the message, and then if such total is 0 we can return True, otherwise we continue. If we reach tot == 0 before looping through all the bowl, then it's done, otherwise we can return False.
• We could've used Counter class of the collections module, but it turns out to be slower than defaultdict from my tests.

We came to an end, finally. This post has been quite long and full of contents and some mathematics. But these is interesting stuff, and definitely a must know for an experienced developer that has to deal with challenging tasks.

Hope you enjoyed it, hasta la proxima!