Solving Programming Problems with PowerShell (Problem 4)

I recently read a blog post by Santiago Valdarrama about developer programming problems. He said that any programmer should be able to solve five problems in an hour or less with a programming language of his choice. My language of choice is PowerShell, which is probably not what he had in mind when he wrote the blog post. So far, I’ve demonstrated In adding numbers in an array three different ways, merging lists together and solving the Fibonacci series.

Problem 4: The Maximal Combination

Problem 4 is described thusly:

Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

This one got me thinking. PowerShell has a cmdlet for sorting, but it won’t do what I want it to – it will sort numerically or lexically in ascending or descending mode. This isn’t flexible enough for my purposes. At the heart of every sort operation is a comparator – two elements in the list will be compared and one will be shown to be “before” the other. For example, 8 is before 9 (when sorting ascending).

Now, let’s take our problem. In order to compare two numbers, we have to look at their combination. Given 5 and 50, 5 comes before 50 because 5-50 is bigger than 50-5 when you push them together. We need to encode that logic in our comparator.

Fortunately, we have the full power of .NET at our disposal. Explicitly, there is a sort method on the System.Collections.ArrayList object that has a Sort method that takes a custom IComparer object. Every sort operation ultimately compares two things in the list – the IComparer interface allows us to specify a custom ordering. First of all, we need to get an ArrayList of strings. Let’s take a look at the code in two pieces:

# Custom sort routine for the ArrayList
$comparatorCode = @"
using System.Collections;

namespace Problem4 {
    public class P4Sort: IComparer {
        public static void Sorter(System.Collections.ArrayList foo) {
            foo.Sort(new P4Sort());

        public int Compare(object x, object y) {
            string v1 = (string)x + (string)y;
            string v2 = (string)y + (string)x;

            return v2.CompareTo(v1);

Add-Type -TypeDefinition $comparatorCode

The Compare method is used to compare our two numbers. The Sorter method is a static method that will do an in-place sort of the provided ArrayList usign the custom comparator. A quick note – you can only add this type once. You will likely have to restart your PowerShell session if you make changes to it. Now, let’s look at my cmdlet:

function ConvertTo-BiggestNumber
        # Param1 help description
        [Parameter(Mandatory=$true, Position=0)]
        [int[]] $Array

        $stringArray = new-object System.Collections.ArrayList

        # Convert the original list to an arraylist of strings
        for ($i = 0 ; $i -lt $Array.Length ; $i++) {
            $stringArray.Add($Array[$i].toString()) | Out-Null
        [string]::join("", $stringArray.ToArray())

This starts by converting the array we are provided to a string ArrayList as required by our custom type, and then sorts it using the .NET Framework Sort method we imported using Add-Type. Finally, we join the array list together. Use it like this:

$a = @( 60, 2, 1, 9)
ConvertTo-BiggestNumber -Array $a

You will get the output 96021.

That leaves the fifth puzzle. Unfortunately, I was not able to find a neat solution in PowerShell to the fifth problem. I ended up dropping down to embedded C# – my solution came pretty close to the authors solution to the same problem. Whether this one is a suitable question on an interview is an open debate – I contest that this doesn’t actually test programming skills but rather logic skills. Given the problem, you either see how to do it or you don’t. If you don’t then no amount of coding skills is going to solve the problem.