Created
February 21, 2022 07:44
-
-
Save priyankshah217/1549c901010ff2e81cc62b799099f323 to your computer and use it in GitHub Desktop.
programming_solutions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment