Thursday, July 25, 2013

How to Solve Minimum Difference Problem

Given two arrays, sorted and exactly the same length, write a function that finds a pair of numbers, one from each of the arrays,such that the difference between both is as small as possible.
Input:
[0, 3, 5, 8, 10], [6, 9, 12, 13, 14]
Output:
[5, 6]

Input:
[7.12, 15, 20, 21], [1, 5, 9, 13, 17]
Output:
[12, 13]

Input:
[6, 10, 15, 18, 21], [16, 17, 18, 23, 27]
Output:
[8, 8]
package main

import (
    "fmt"
)

func diff(n int) int {
    if n < 0 {
        return n * -1
    }
    return n
}

func minDiff(a []int, b []int) (int, int) {
    min := -1
    var result1, result2 int
    for i, j := 0, 0; i < len(a) && j < len(b); {
        newMin := diff(a[i] - b[j])
        if min == -1 {
            min = newMin
            result1, result2 = a[i], b[j]
        } else {
            if newMin < min {
                min = newMin
                result1, result2 = a[i], b[j]
            }
        }
        if a[i] < b[j] {
            i++
        } else {
            j++
        }
    }
    return result1, result2
}

func main() {
    fmt.Println(minDiff([]int{0, 3, 5, 8, 10}, []int{6, 9, 12, 13, 14}))
    fmt.Println(minDiff([]int{7, 12, 15, 20, 21}, []int{1, 5, 9, 13, 17}))
    fmt.Println(minDiff([]int{6, 10, 15, 18, 21}, []int{16, 17, 18, 23, 27}))
}

Friday, July 12, 2013

How to Solve Balancing Arrays Problem

Given an array of numbers, return the index at which the array can be balanced by all numbers on the left side add up the sum of all numbers of the right side.

For example:
an array with [1,5,6,7,9,10] can be balanced by splitting the array at position 4
an array with [1, 5, 6, 7, 9, 10] can be balanced by splitting the array at position 4
an array with [3, 8, 4, 15] can be balanced by splitting the array at position 3
an array with [1, 8, 1, 2, 8]) can be balanced by splitting the array at position 3
an array with [1, 3, 5, 1, 2] can't be balanced, hence position -1

package main

import (
    "fmt"
)

func balancingArrays(slice []int) int {
    left := 0
    right := len(slice) - 1
    sumLeft := 0
    sumRight := 0
    for left <= right {
        if sumLeft < sumRight {
            sumLeft += slice[left]
            left++
        } else {
            sumRight += slice[right]
            right--
        }
    }
    if sumLeft == sumRight {
        return left
    }
    return -1
}

func main() {
    fmt.Println(balancingArrays([]int{1, 5, 6, 7, 9, 10})) // 4
    fmt.Println(balancingArrays([]int{3, 8, 4, 15}))       // 3
    fmt.Println(balancingArrays([]int{1, 8, 1, 2, 8}))     // 3
    fmt.Println(balancingArrays([]int{1, 3, 5, 1, 2}))     // -1
}