main.go

package main

import (
	"fmt"
	"os"
	"sort"
)

func getMedian(array1 []uint32, array2 []uint32) uint32 {
	// O(n/2) solution with optimization for edge cases

	// Boundary checks
	l := len(array1)
	if l == 0 {
		return 0
	}

	// Quick win, both array consists of only one element
	if l == 1 {
		return (array1[0] + array2[0]) / 2
	}

	// Quick win, if arrays do not intersect
	if array1[l-1] <= array2[0] {
		return (array1[l-1] + array2[0]) / 2
	} else if array2[l-1] <= array1[0] {
		return (array2[l-1] + array1[0]) / 2
	}

	// This array will hold 2 elements to calculate median
	a := make([]uint32, 2)

	for i, i1, i2 := 0, 0, 0; i <= l; i++ {
		if array1[i1] <= array2[i2] {
			a[i%2] = array1[i1]
			i1++
		} else {
			a[i%2] = array2[i2]
			i2++
		}
	}

	return (a[0] + a[1]) / 2
}

func Perm(a []uint32, f func([]uint32)) {
	perm(a, f, 0)
}

func perm(a []uint32, f func([]uint32), i int) {
	if i > len(a) {
		f(a)
		return
	}
	perm(a, f, i+1)
	for j := i + 1; j < len(a); j++ {
		a[i], a[j] = a[j], a[i]
		perm(a, f, i+1)
		a[i], a[j] = a[j], a[i]
	}
}

func main() {
	fmt.Println("empty:", getMedian([]uint32{}, []uint32{}) == 0)
	fmt.Println("one element:", getMedian([]uint32{1}, []uint32{3}) == 2)

	// Brute force tests
	Perm([]uint32{1, 2, 3, 4, 5, 6}, func(a []uint32) {
		a1 := make([]uint32, 3)
		a2 := make([]uint32, 3)

		copy(a1, a[:3])
		copy(a2, a[3:])

		sort.Slice(a1, func(i, j int) bool { return a1[i] < a1[j] })
		sort.Slice(a2, func(i, j int) bool { return a2[i] < a2[j] })

		median := getMedian(a1, a2)

		fmt.Printf("Test case %+v, %+v, median = %d, passed = %v\n", a1, a2, median, median == 3)

		if median != 3 {
			fmt.Println("FAILED")
			os.Exit(1)
		}
	})
	fmt.Println("ALL TESTS PASSED")
}