Why struct is important?

The struct data type offers a way to represent the concept of abstraction, helping us create software that is both understandable and less prone to errors.

For example, we can use two arrays to represent people’s name and phone number.

func main() {
    people := [3]string{"Andy", "Ben", "Cindy"}
    phoneNumber := [3]string{"0911-111-111", "0922-222-222", "0933-333-333"}
	fmt.Printf("%s's number is %s\n", people[0], phoneNumber[0])
}

This code is highly prone to errors, such as the possibility of a typo mistake leading to an incorrect assignment of phone numbers. For instance, if Andy’s phone number is 0922-222-222 and Ben’s number is 0911-111-111, a simple typo could result in incorrect data.

Let us try to use struct to fix this issue.

type Person struct {
	Name        string
	PhoneNumber string
}

func main() {
	people := [3]Person{
		Person{
			Name:        "Andy",
			PhoneNumber: "0911-111-111",
		},
		Person{
			Name:        "Ben",
			PhoneNumber: "0922-222-222",
		},
		Person{
			Name:        "Cindy",
			PhoneNumber: "0933-333-333",
		},
	}

	fmt.Printf("%s's number is %s\n", people[0].Name, people[0].PhoneNumber)

}

We have established a new struct named “Person.” Within the “Person” struct, there are two attributes: “name” and “phone.” Note that when utilizing the printf function, we access the data using people[0].Name and people[0].PhoneNumber. We employ the struct to encapsulate our data, making our program more comprehensible and less prone to errors.

Recursion

The definition of a recursive function is one that, as part of its execution, invokes itself.

Every recursive function has two cases that could apply, given any input

  • The base case, which when triggered will terminate the recursive process.

  • The recursive case, which is where the recursion will actually occur.

Example: Factorial function

func calculateFactorial(num int) int {
	// base case
	if num == 1 {
		return 1
	} else {
		// recursive case
		return num * calculateFactorial(num-1)
	}
}

Binary Search

func binarySearch(want int, numbers []int) bool {

	if len(numbers) == 1 && numbers[0] != want {
		return false
	}

	middle := (len(numbers) - 1) / 2
	actual := numbers[middle]
	if actual == want {
		return true
	}

	if actual > want {
		return binarySearch(want, numbers[:middle])
	} else {
		return binarySearch(want, numbers[middle:])
	}
}

func binarySearch2(want int, nums []int) bool {

	start := 0
	end := len(nums) - 1

	for start <= end {
		middle := (start + end) / 2
		if nums[middle] == want {
			return true
		}

		if nums[middle] > want {
			end = middle - 1
		} else {
			start = middle + 1
		}
	}
	return false
}

The time complexity of the first solution for binary search

  • Best-case: O(1)

  • Worst-case: O(log N) What is log?

    • Why

      • Because in binary search we divide array in half at each step to do the search.

The space complexity of the first solution for binary search

  • the space complexity is O(log n).

    • Each recursive call creates a new stack frame that holds its local variables, so the number of stack frames equals the depth of the recursion, which is log n in this case.

The time complexity of the second approach of binary search remains unchanged, while the space complexity differs. The space complexity, in this case, would be O(1).

Sort

Select sort

/*
For i from 0 to n-1
  Find smallest number between numbers[i] and numbers[n-1]
  Swap smallest number with numbers[i]
*/

func selectionSort(nums []int) []int {
	for i := 0; i < len(nums)-1; i++ {
		minIndex := i
		for j := i + 1; j < len(nums); j++ {
			if nums[j] < nums[i] {
				minIndex = j
			}
		}
		if minIndex != i {
			nums[i], nums[minIndex] = nums[minIndex], nums[i]
		}
	}
	return nums
}

The time complexity of the select sort is:

  • Best-case: O(N^2)

  • Worst-case: O(N^2)

Bubble sort

/*
Repeat until the swap counter is 0:
  Reset swap counter to 0
  Look at each adjacent pair
    if two adjacent elements are not in order, swap them and add one the swap counter
*/

func bubbleSort(nums []int) []int {
	if len(nums) == 1 {
		return nums
	}
	swap := true
	for swap {
		swap = false
		for i := 0; i < len(nums)-2; i++ {
			j := i + 1
			if nums[i] > nums[j] {
				nums[i], nums[j] = nums[j], nums[i]
				swap = true
			}
		}
	}
	return nums
}

The time complexity of the bubble sort is:

  • Best-case: O(N)

  • Worst-case: O(N^2)

The space complexity is O(1). for the swap variable.

Merge sort

/*
If only one number
  Quit
Else 
  Sort left half of number
  Sort right half of numbers
  Merge sorted halves

*/

func mergeSort(nums []int) []int {

	if len(nums) == 1 {
		return nums
	}

	middle := len(nums) / 2
	left := mergeSort(nums[:middle])
	right := mergeSort(nums[middle:])
	return merge(left, right)

}

func merge(left, right []int) []int {

	var out []int

	leftIndex := 0
	rightIndex := 0
	for leftIndex < len(left) && rightIndex < len(right) {
		if left[leftIndex] < right[rightIndex] {
			out = append(out, left[leftIndex])
			leftIndex++
		} else {
			out = append(out, right[rightIndex])
			rightIndex++
		}
	}

	for ; rightIndex < len(right); rightIndex++ {
		out = append(out, right[rightIndex])
	}

	for ; leftIndex < len(left); leftIndex++ {
		out = append(out, left[leftIndex])
	}

	return out

}

The time complexity is:

  • Best-case and Worst-case is: O(N logN)

  • Why?

    • Because we divide the input number slice in two parts in each recursive step(this happens log n times, as we can divide n elements log n times until 1 element remains). After dividing, we start merging our sub-slice, each merging operation takes liner time.