Amazon interview question - divide a list of integers into 2 lists where the sum of each list is as "balanced" as possible - here's a greedy hill-climbing algorithm:


Option Strict On
Option Explicit On
Module Module1
Public Const N As Integer = 100
Public Const HalfN As Integer = CInt(N / 2)
Public Const maxval As Integer = 1000
Public Const maxTries As Integer = 10000000
Dim list1 As List(Of Integer) = Nothing
Dim list2 As List(Of Integer) = Nothing
Dim tries As Integer = 0
Dim genRand As New Random()
Class Swap
Public i As Integer
Public j As Integer
Sub New(ByVal iv As Integer, ByVal jv As Integer)
i = iv
j = jv
End Sub
End Class
Public Sub generateRandom()
list1 = New List(Of Integer)
list2 = New List(Of Integer)
tries = 0
For i As Integer = 0 To HalfN - 1
list1.Add(genRand.Next(0, maxval))
list2.Add(genRand.Next(0, maxval))
Next
End Sub
Public Function findFirstSwap() As Swap
Dim diff As Integer = list1.Sum - list2.Sum
If (diff = 0) Then
Return Nothing
End If
For i As Integer = HalfN - 1 To 1 Step -1
For j As Integer = 0 To i - 1
tries = tries + 1
Dim x = list1.Item(i)
Dim y = list2.Item(j)
Dim newDiff = abs(diff - 2 * x + 2 * y)
If (newDiff < abs(diff)) Then
Return New Swap(i, j)
End If
Next
Next
Return Nothing
End Function
' just use greedy hillclimbing algorithm
Public Sub trySwap()
Dim firstSwap As Swap = findFirstSwap()
While (Not firstSwap Is Nothing And tries < maxTries)
With firstSwap
Dim x = list1.Item(.i)
Dim y = list2.Item(.j)
list1.Item(.i) = y
list2.Item(.j) = x
End With
firstSwap = findFirstSwap()
End While
End Sub
Public Sub output()
Console.WriteLine("partitions - difference in size is : " _
& (list1.Sum - list2.Sum).ToString() & _
" ops = " & tries.ToString())
Console.Write(list1.Sum.ToString() & ": ")
For Each x In list1
Console.Write(x.ToString & " ")
Next
Console.WriteLine()
Console.WriteLine("--------------------------------------------------------------")
Console.Write(list2.Sum.ToString() & ": ")
For Each x In list2
Console.Write(x.ToString & " ")
Next
Console.WriteLine()
End Sub
Public Function abs(ByVal x As Integer) As Integer
If x < 0 Then
Return -x
Else
Return x
End If
End Function
Public Sub test()
generateRandom()
trySwap()
output()
End Sub
Sub Main()
For I As Integer = 0 To 10
test()
Console.WriteLine()
Next
Console.ReadLine()
End Sub
End Module