Arrange an array such that the average of 2 numbers does not lie between them

Question

As the question says, find an algorithm to arrange the array. This was a Facebook interview question.

The average needs to be exact. We do not round of, take floor or ceil of the average.

Edit : To quote an example, if the numbers are 1,2,5,9, then the arrangement {1,9,2,5} is valid but {1,5,9,2} is not since average of 1 and 9 is 5 and lies between them.

Answer 1

Beaten to it by Captain Skyhawk, but...

Module Module1

    Sub Main()
        Dim a() As Integer = {9, 4, 7, 6, 4, 4, 3, 4, 1}
        Dim n = a.Length

        'TODO: check that sanity has a reasonable vale
        Dim sanity As Integer = n
        Dim ok As Boolean = False
        Dim temp As Integer

        While Not ok And sanity > 0
            ok = True
            For i = 0 To n - 3
                If ((a(i) + a(i + 2)) / 2) = a(i + 1) Then
                    temp = a(i)
                    a(i) = a(i + 1)
                    a(i + 1) = temp
                    ok = False
                End If

            Next

            sanity -= 1
        End While
        Console.WriteLine("OK: " & ok.ToString())

        Console.WriteLine(String.Join(" ", a))

        Console.ReadLine()

    End Sub

End Module

Answer 2

Barring no funny business(duplicate entries), initial check showed this works:

    void check(ref int x, ref int y, int z)
    {
        if ((x + z) / 2 == y)
        {
            int temp = x;
            x = y;
            y = temp;
        }
    }

    int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };

    for( int i = 0; i < nums.Count() - 3; i++)
    {
        check(ref nums[i], ref nums[i + 1], nums[i + 2]);
    }

Creating an algorithm for this on the spot that handles all cases(duplicate entries) though might be a little tricky. You would need some form of recursive function to go through and find the next entry that meets the criteria, yet doesn't break the list.

This might seem trivial, but consider the case of:

  { 2,2,2,4,5,6,2,2,2,2 }

You'd have to loop back to the beginning, which still doesn't have the right answer.