Categories
Data Structure and Algorithm

Slice of Slice

https://play.golang.org/p/3HpTAxoPC6l

// in Go Data Structures and algorithms book
package main

// importing fmt package
import (
	"fmt"
)

// main method
func main() {
	var rows int
	var cols int
	rows = 7
	cols = 9
	
	// rows := 7
	// cols := 9
	
 	var twodslices = make([][]int, rows)
	var i int
	for i = range twodslices {
		twodslices[i] = make([]int, cols)
	}
	fmt.Println(twodslices)
}
Categories
Data Structure and Algorithm

Create and Print a 2D Slice

https://play.golang.org/p/F5MTsF_Z1J1

// in Go Data Structures and algorithms book
package main

// importing fmt package
import (
	"fmt"
)

// main method
func main() {
	var TwoDArray [8][8]int
	TwoDArray[3][6] = 18
	TwoDArray[7][4] = 3
	fmt.Println(TwoDArray)
}
Categories
Data Structure and Algorithm Linear My Go Tutorial

Linked List

Linked lists are linear data structures that hold data in individual objects called nodes. These nodes hold both the data and a reference to the next node in the list. Linked lists are often used because of their efficient insertion and deletion. They can be used to implement stacks, queues, and other abstract data types

Categories
Data Structure and Algorithm My Go Tutorial

Big-O Chart Comparision

Credits to the contributors from biocheatsheet.com

Categories
Data Structure and Algorithm Functions_Closures My Go Tutorial

Factorial (both not recursive and recursive)

package main

import (
	"fmt"
)
// n! = n * (n-1) * (n-2)...* 2 * 1
// code limited to return value based
// int type interger range
func factorial(num int) int {
        if num == 0 {
            return 1
        }
	f := num
	for i:=num; i>=3; i-- {
		f = f * (i - 1)
	}
	return f
}

func main() {
	// Dn't used value beyond int type integer range
	fmt.Println("Factorial:",factorial(20))
}
package main

import "fmt"

// n! = n * (n-1) * (n-2)...* 2 * 1
// code limited to return value based
// int type interger range
// Recursive function
func fact(n int) int {
// terminate the loop with return
	if n == 0 {
		return 1
	}
// return call fact() function is recursively repeteatly 
	return n * fact(n - 1)
}

func main() {
	fmt.Println(fact(5))
}
Categories
Data Structure and Algorithm Mini-Programs

FizzBuzz

For numbers which are divisible of both 3 and 5, print “FizzBuzz” instead of the number. Divisible by 3 print “Fizz” and divisible by 5 print “Buzz”

package main

import (
	"fmt"
)

func fizzBuzz(num int) {
	for v := 1; v <= num; v++ {
		if  v % 15 == 0  {
			fmt.Println("v:", v, "FizzBuzz")
		} else if v % 5 == 0 {
				fmt.Println("v:", v, "Buzz")
			} else if v % 3 == 0 {
				fmt.Println("v:", v, "Fizz")
			} else {
			fmt.Println("v:", v)
		}
	}
}

func main() {
	fizzBuzz(20)
}
Categories
Data Structure and Algorithm Linear My Go Tutorial

Binary Search

The time complexity of this algorithm is in the order of O(log n).

The binary search algorithm compares the input value to the middle element of the sorted collection.

// Binary Search 
package main

// importing sort package
import (
  "fmt"
  "sort"
)

// main method
func main() {
  var elements []int
  elements = []int{1, 3, 16, 10, 28, 31, 36, 45, 75}
  var element int
  element = 36

  var i int

  i = sort.Search(len(elements), func(i int) bool { return elements[i] >= element })
  if i < len(elements) && elements[i] == element {
    fmt.Printf("found element %d at index %d in %v\n", element, i, elements)
  } else {
    fmt.Printf("element %d not found in %v\n", element, elements)
  }
}
func Search(n int, f func(int) bool) int

Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) == true implies f(i+1) == true.

When shifting right with a logical right shift ( >> ), the least-significant bit is lost and a 0 is inserted on the other end. For positive numbers, a single logical right shift divides a number by 2, throwing out any remainders.

func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}

https://golang.org/pkg/sort/#pkg-overview

Categories
Data Structure and Algorithm Linear

Linear Search

The time complexity of the linear search algorithm is O(n). This means that the running time increases at most linearly with the size of the input.

// Linear Search 
package main

import (
  "fmt"
)

// Linear Search function
func LinearSearch(elements []int, findElement int) bool {
  var element int
  for _, element = range elements {
    if element == findElement {
      return true
    }
  }
  return false
}
func main() {
  var elements []int
  elements = []int{15, 48, 26, 18, 41, 86, 29, 51, 20}
  fmt.Println(LinearSearch(elements, 48))
}
Categories
Data Structure and Algorithm My Go Tutorial

Sorting: Bubble

The bubble sort algorithm is a sorting algorithm that compares a pair of neighboring elements and swaps them if they are in the wrong order

package main

import (
  "fmt"
)

//bubble Sorter 
func bubbleSorter(integers [11]int) {

    isSwapped := true
    for isSwapped {
   
    isSwapped = false
    for i := 1; i < len(integers); i++ {
      if integers[i-1] > integers[i] {
	// swap routine
	temp := integers[i]
        integers[i] = integers[i-1]
        integers[i-1] = temp
        isSwapped = true
      }
    }
  }
  fmt.Println(integers)
}

func main() {
  // integers := [11]int{31, 13, 12, 4, 18, 16, 7, 2, 3, 0, 10} short form
  var integers = [11]int{31, 13, 12, 4, 18, 16, 7, 2, 3, 0, 10}
 
  fmt.Println("Bubble Sorter")
  bubbleSorter(integers)

}

https://play.golang.org/p/1ob1N-sZKmp

Note: No nested loop used help in reducing the unnecessary looping of all element even a single pair of the unsorted list.

Categories
Data Structure and Algorithm My Go Tutorial

Slice, for, len(), cap(), append, copy

Shortcoming of Go array is address by Go slice. It can be appended to elements after the capacity has reached its size. Slices are dynamic and can double the current capacity in order to add more elements.

var slice = []int{1,3,5,6}
fmt.Println("Capacity", cap(slice))
fmt.Println("Length", len(slice))
slice = append(slice, 8)
fmt.Println(“Capacity”, cap(slice))
fmt.Println(“Length”, len(slice))

https://play.golang.org/p/_8fqAbg2cUJ

Slice and Functions ( call by reference)

package main

import "fmt"

//twiceValue method given slice of int type
func twiceValue(slice []int) {
	for i, value := range slice {
		slice[i] = 2 * value
	}
}

func main() {
	var slice = []int{1, 3, 5, 6}
	// pass by reference when twiceValue function called
	twiceValue(slice)

	for i := 0; i < len(slice); i++ {
		// Original slice value modified by twiceValue function
		fmt.Println("new slice value", slice[i])
	}
}

https://play.golang.org/p/Sc2yD7rXpRl