Sort & Search Algorithms

Question 1

Selection sort

Answer 1

Repeatedly select the smallest (or largest) element from the unsorted portion of the list and move it to the sorted portion of the list by swapping elements

O(n^2) time complexity; O(1) space complexity

func SelectionSort(array []int) []int {
var min_idx int
for i := 0; i < len(array) - 1; i++ {
min_idx = i
for j := i + 1; j < len(array); j ++ {
if array[j] < array[min_idx] {
min_idx = j
}
}
array[i], array[min_idx] = array[min_idx], array[i]
}
return array
}

Question 2

Bubble sort

Answer 2

The simplest sort. Repeatedly swap adjacent elements if they are in the wrong order

O(n^2) time complexity; O(1) space complexity

func BubbleSort(array []int) []int {
var swapped bool
for i := 0; i < len(array); i++ {
swapped = false
for j := 0; j < len(array) - 1 - i; j++{
if array[j] > array[j + 1] {
array[j], array[j + 1] = array[j + 1], array[j]
swapped = true
}
}
if swapped == false {
break
}
}
return array
}

Question 3

Insertion sort

Answer 3

Array is virtually split into a sorted and an unsorted part. Values from unsorted part are picked and placed at the correct position in the sorted part. Similar to sorting playing cards.

O(N^2) time complexity; O(1) space complexity

func InsertionSort(array []int) []int {
for i := range array {
for j := i; j > 0 && array[j] < array[j-1]; j– {
array[j], array[j-1] = array[j-1], array[j]
}
}
return array
}

Question 4

Interview strategies

Answer 4

1. Ask questions up front
2. Attempt the brute force solution first
3. Talk through and write out what you’re going to do
4. Code the solution
5. Be sure to manually walk through it afterwards to review
6. Try walking through what it is actually doing with mock inputs
7. Note the time and space complexity
8. Talk through and attempt to improve time and space complexity
9. Consider ways to refactor your code (eg pulling out logic into separate functions)

Question 5

Binary search

Answer 5

Used in a sorted array by repeatedly dividing the search interval in half

func BinarySearch(array []int, target int) int {
left := 0
right := len(array) - 1
for left <= right {
middle := (right + left) / 2
value := array[middle]
if value == target {
return middle
} else if target > value {
left = middle + 1
} else {
right = middle - 1
}
}
return -1
}

Question 6

Merge Sort

Answer 6

func MergeSort(array []int) []int {
if len(array) < 2 {
return array
}
partition := len(array) / 2
left := MergeSort(array[:partition])
right := MergeSort(array[partition:])
return merge(left, right)
}

func merge(left, right []int) []int {
i := 0
j := 0
array := []int{}
for i < len(left) && j < len(right) {
if left[i] < right[j] {
array = append(array, left[i])
i++
} else {
array = append(array, right[j])
j++
}
}
for i < len(left) {
array = append(array, left[i])
i++
}
for j < len(right) {
array = append(array, right[j])
j++
}
return array
}

Question 7

What is the time complexity of the best sorting algorithm?

Answer 7

n log(n)