Ascending Sort - Google CodeJam

Photo by Mehmet Akif from Pexels

I recently got an invite to Google's CodeJam coding competition. I've never taken part in any coding competitions prior, nor do I consider myself good at many algorithms. Still, I am genuinely interested in the problem-solving aspect of problems, so I decided to enroll. 

The CodeJam site lets you view past problems, and I decided to take a stab at one of them - ascending sort. It is a Round 1 Qualifying question, and it can be found in its entirety over here.

Thoughts on Solving this problem

Determining an approach to solve this problem took me around 10 to 15 minutes. However, implementing a solution took about 2 hours. I hadn't accounted for some edge cases in my initial approach. Figuring out these failed edge cases was challenging. 

Google's coding interface is exceptionally sparse and does not provide any more information besides a pass or a fail. I used the 100 samples provided in the analysis section to determine failed cases.

The site also provides a list of each round's winners. Most of the top rankers had solved this problem in under 15 minutes.

The Problem

You are given a list of numbers and asked to modify each number such that the final list is in a strictly sorted order. The output of the code would be the number of digits added to all the numbers in the list.

In the example below, the second number is modified to 748. As a result, the first two numbers in the list are now sorted. The third number is changed similarly.

The Approach

It was clear that the approach required modifying two numbers at a time. The second number in the pair would need to be appended to be sorted. The revised second number would now form the first number of the next pair to the considered. The solutions would run in linear time.

Sorted Numbers in the Pair

If the two numbers in the pair are already sorted, they can be ignored, and we can then consider the next pair. 

Equal Numbers in the Pair

If both numbers are equal, we can simply add a zero to the end of the second number. We append a Zero so that the new number is the lowest possible. 

Note - the original example in the problem seems to deliberately confuse the solver by appending arbitrary numbers. Appending Zeroes is sufficient.

Unsorted Numbers in the Pair

Things get interesting as we need to determine what exactly to append. 

Finding the Common Numbers

We first determine how many digits are in the second number and pick those same digits from the first number. For example, we choose 1 and 56 from the first numbers in the following example.

Common Numbers in Ascending Order

In the case above, since both common numbers are already in ascending order, we only need to append zeros in the remaining spaces (number of digits in first - number of digits in second)

Common Numbers in Descending Order

If the two common numbers are not sorted, and in ascending order, we simply need to append zeros in the remaining spaces plus an extra Zero. 

Common Numbers are Equal

If the two common numbers are equal, we could just add an extra zero, but...

We also need to consider whether we can find a lower number. In the following example, we can find a lower number rather than simply appending an extra Zero. This can be determined by picking the second part of the first number and adding a 1. If the new number fits, we use it as shown below. 

However, if the new number's digits increase by 1, we simply append zeroes and an extra zero.

Helper Functions

I thought these deserved their own section, as I had previously not known of a proper way to figure out the number of digits in a number other than converting them to a string. 

It is possible to determine the number of digits mathematically -

def numberOfDigits(num):
    return math.floor(math.log(num,10) + 1) 

To pick the first few digits of a number mathematically -

number // (10 ** numberOfDigits)

To pick the last few digits of a number as follows -

number % (10 ** numberOfDigits)

The Code

The following code is a culmination of everything described in the previous section, and it only covers the sorting of a single pair of numbers. I haven't shown the code that parses through the input of multiple test cases.

def sortTwoNumbers(pair):
    first,second = pair
    sortedFirst, sortedSecond = pair
    numberOfAdds = 0
    
    if first == second:
        sortedSecond = second * 10
        numberOfAdds = 1
    elif first > second:
        
        firstNumberOfDigits = numberOfDigits(first)
        secondNumberOfDigits = numberOfDigits(second)
        diffFirstSecond = firstNumberOfDigits-secondNumberOfDigits

        if diffFirstSecond > 0: # second number needs appending to
            
             # get the first digits of the first number that correspond to the second number digits
            firstCommon = first // (10 ** diffFirstSecond)
            
            if firstCommon > second:
                numberOfAdds = diffFirstSecond + 1 # fill the rest with zeroes and add one more
                sortedSecond = second * (10 ** numberOfAdds) 
            elif firstCommon == second:
                firstRemainingDigits = (first % (10 ** diffFirstSecond)) # second part of the first number
                secondNumberAppend = firstRemainingDigits+1              # what needs to be appended
                
                numberOfAdds = numberOfDigits(secondNumberAppend)    # the number maybe larger (999+1)
                if numberOfAdds < diffFirstSecond:                   # or might be smaller
                    numberOfAdds = diffFirstSecond

                sortedSecond = second * (10 ** numberOfAdds)    # append all the zeroes
                if numberOfAdds == diffFirstSecond:             # also add the apend part if no extra zeroes were appended
                    sortedSecond += secondNumberAppend 
            else: # firstCommon < second
                numberOfAdds = diffFirstSecond # just fill the rest with zeros
                sortedSecond = second * (10 ** numberOfAdds)
        else: # diffFirstSecond == 0 , cannot be anything else
            numberOfAdds = 1
            sortedSecond = second * 10

    return (sortedFirst,sortedSecond,numberOfAdds)