programming_solutions

Programming_solutions.go

package main

import (
	"math"
	"sort"
)

// Problem 7
func findMinNoOfPlatformRequired(arrivals []int, departures []int) int {
	sort.Ints(arrivals)
	sort.Ints(departures)
	var i, j, count int
	result := 1
	for i < len(arrivals) && j < len(departures) {
		if arrivals[i] < departures[j] {
			count++
			i++
		} else {
			count--
			j++
		}
		result = int(math.Max(float64(result), float64(count)))
	}
	return result
}

// Problem 6
func findOddOccurrenceFromArray(input []int) int {
	freqMap := make(map[int]int)
	for _, v := range input {
		if count, ok := freqMap[v]; ok {
			freqMap[v] = count + 1
		} else {
			freqMap[v] = 1
		}
	}
	for k := range freqMap {
		if freqMap[k]%2 != 0 {
			return k
		}
	}
	return 0
}

// Problem 5
func findMinFromSortedRotatedArray(input []int) int {
	return findMinFromSortedRotatedArrayHelper(input, 0, len(input)-1)
}

func findMinFromSortedRotatedArrayHelper(input []int, low int, high int) int {
	mid := (high + low) / 2
	if low == high {
		return input[low]
	}
	if input[low] <= input[mid] && input[mid] < input[high] {
		return input[low]
	}
	if input[mid+1] < input[mid] {
		return input[mid+1]
	}
	if input[mid] < input[mid-1] {
		return input[mid]
	}
	if input[high] > input[mid] {
		return findMinFromSortedRotatedArrayHelper(input, low, mid-1)
	}
	return findMinFromSortedRotatedArrayHelper(input, mid+1, high)
}

// Problem 4
func getElementFromRotatedArray(input []int, key int) int {
	pivot := findPivot(input, 0, len(input)-1)
	if input[pivot] == key {
		return pivot
	} else if input[0] < key {
		return binarySearch(input, 0, pivot-1, key)
	} else {
		return binarySearch(input, pivot+1, len(input)-1, key)
	}
}

func binarySearch(input []int, low int, high int, key int) int {
	if low > high {
		return -1
	}
	mid := (low + high) / 2
	if input[mid] == key {
		return mid
	} else if input[mid] < key {
		return binarySearch(input, mid+1, high, key)
	}
	return binarySearch(input, low, mid-1, key)
}

func findPivot(input []int, low int, high int) int {
	mid := (high + low) / 2
	if low == high {
		return low
	}
	if input[low] <= input[mid] && input[mid] < input[high] {
		return low
	}
	if input[mid+1] < input[mid] {
		return mid + 1
	}
	if input[mid] < input[mid-1] {
		return mid
	}
	if input[high] > input[mid] {
		return findPivot(input, low, mid-1)
	}
	return findPivot(input, mid+1, high)
}

// Problem 3
func findMissingNoFromArray(input []int) int {
	maxLength := len(input)
	var arr []int
	xorSum := 0
	for i := 1; i <= maxLength+1; i++ {
		arr = append(arr, i)
	}
	for _, v := range input {
		xorSum ^= v
	}
	for _, v := range arr {
		xorSum ^= v
	}
	return xorSum
}

// Problem 1 & 2
func getMinMaxFromArray(input []int) (min int, secondMin int, max int, secondMax int) {
	min = math.MaxInt
	secondMin = math.MaxInt
	max = math.MinInt
	secondMax = math.MaxInt
	for _, v := range input {
		min, secondMin = getMinimums(min, v, secondMin)
		max, secondMax = getMaximums(max, v, secondMax)
	}
	return
}

func getMaximums(max int, v int, secondMax int) (int, int) {
	if max < v {
		secondMax = max
		max = v
	} else if secondMax < v {
		secondMax = v
	}
	return max, secondMax
}

func getMinimums(min int, v int, secondMin int) (int, int) {
	if min > v {
		secondMin = min
		min = v
	} else if secondMin > v {
		secondMin = v
	}
	return min, secondMin
}