Problem 3: rearrange of lists

The sequence [0, 1, ..., N] has been jumbled, and the only clue you have for its order is an array representing whether each number is larger or smaller than the last. Given this information, reconstruct an array that is consistent with it. For example, given [None, +, +, -, +], you could return [1, 2, 3, 0, 4].

Solution:

We will build an algorithm with the following idea in mind: we start from an arbitrary number, let us say, 0, and append it to a list K that we will return. We will cycle through the list L we are given, and every time we see a +, we will add 1 to the biggest number we have seen and append it to K, and every time we see a -, we will add -1 to the smallest number we have seen and append it to K. In this way we will construct an increasing sequence and a decreasing sequence, both disjoint. Since we started from zero, the minimum element of our list will be the number of - that we see during the whole process. If we subtract this number to the whole list, now it will range in [0,N]. We proceed to implement the algorithm:

def list_order(L):
    K = [0]
    max_last = 0 #Keeps track of the biggest number we have seen
    min_last = 0 #Keeps track of the smallest number we have seen

    for i in range(1,len(L)):
        if L[i] == '+':
            K.append(max_last + 1)
            max_last += 1
        elif L[i] == '-':
            K.append(min_last - 1)
            min_last -= 1
    return [k - min_last for k in K]

A jupyter notebook implementation with a few test cases can be found here.