Arrays & Slices Flashcards
Append slice in 2D slice without replacing
ans = append(ans, append([]int{}, subset…))
Create 2D slice
var ans [][]int
ans = make([][]int, 0)
then each internal slice needs to be initialized as separate memory to avoid overriding.
Pass new empty slice to a function call
functionCall(A, 0, make([]int, 0))
or
functionCall(A, 0, []int{}) // seems more expensive here?
Passing slice by reference to function
slices are already pass by reference. Slices are passed by value, but their value is just a length and a pointer to an array
Create slice using make
ans := make([]int, len(array))
b := make([]int, 0, 5) // len(b)=0, cap(b)=5
initialize a map
dups := make(map[int]bool)
m := map[int]string{}
level order traversal iterative
func LevelOrder(root *BinaryTree) {
queue := []*BinaryTree{}
queue = append(queue, root)
res := []int{}
for level := 0; len(queue) > 0; level++ {
size := len(queue)
for i := 0; i < size; i++ {
curr := queue[0]
queue = queue[1:]
res = append(res, curr.Value)
if curr.Left != nil {
queue = append(queue, curr.Left)
}
if curr.Right != nil {
queue = append(queue, curr.Right)
}
} } }
Queues using slices
queue := make([]int, 0)
// Push to the queue
queue = append(queue, 1)
// Top (just get next element, don’t remove it)
x = queue[0]
// Discard top element
queue = queue[1:]
// Is empty ?
if len(queue) == 0 {
fmt.Println(“Queue is empty !”)
}
Stack using slices
type Stack []string
func (s *Stack) Push(str string) {
s = append(s, str)
}
func (s Stack) Pop() (string, bool) {
if len(s) == 0 { // is empty
return “”, false
} else {
index := len(s) - 1 // Get the index of the top most element.
element := (s)[index]
s = (s)[:index] // Remove it from the stack by slicing it off.
return element, true
}
}
Min and Max Values of Integers
math.MinInt, math.MaxInt
math.MinInt64, math.MaxInt64
math.Inf(1)
Absolute Value
func Abs(y float64) float64
math.Abs(-3)
Max and Min library functions
import “math”
func Max(a, b float64) float64
func Min(x, y float64) float64
Standard input sorting
import “sort”
str := []string{“c”, “a”, “b”}
sort.Strings(str)
ints := []int{7, 2, 4}
sort.Ints(ints)
Sort a string characters
word := “1BCagM9”
s := []rune(word)
sort.Slice(s, func(i int, j int) bool { return s[i] < s[j] })
fmt.Println(string(s))
Output: 19BCMag
TC: O(NlogN) , golang uses optimized version of quicksort
Check if input is already sorted
import “sort”
ints := []int{1,2,3}
check := sort.IntsAreSorted(ints)
fmt.Println(“Sorted: “, check)
Output:
Sorted: true
Sort reverse
sort.Ints is a convenient function to sort a couple of ints. Generally you need to implement the sort.Interface interface if you want to sort something and sort.Reverse just returns a different implementation of that interface that redefines the Less method.
Luckily the sort package contains a predefined type called IntSlice that implements sort.Interface:
keys := []int{3, 2, 8, 1}
sort.Sort(sort.Reverse(sort.IntSlice(keys)))
fmt.Println(keys)
OR
sort.Slice(example, func(a, b int) bool {
return example[b] < example[a]
})
Custom Sort
In order to sort by a custom function in Go, we need a corresponding type. Here we’ve created a byLength type that is just an alias for the builtin []string type.
We implement sort.Interface - Len, Less, and Swap - on our type so we can use the sort package’s generic Sort function. Len and Swap will usually be similar across types and Less will hold the actual custom sorting logic. In our case we want to sort in order of increasing string length, so we use len(s[i]) and len(s[j]) here.
package main
import (
“fmt”
“sort”
)
type byLength []string
func (s byLength) Len() int {
return len(s)
}
func (s byLength) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}
func (s byLength) Less(i, j int) bool {
return len(s[i]) < len(s[j])
}
/*With all of this in place, we can now implement our custom sort by converting the original fruits slice to byLength, and then use sort.Sort on that typed slice. */
func main() {
fruits := []string{“peach”, “banana”, “kiwi”}
sort.Sort(byLength(fruits))
fmt.Println(fruits)
}
Sort 2D slice
sort.Slice(ans, sortComparatorLessThan)
func sortComparatorLessThan(i, j int) bool {
//edge cases
if len(ans[i]) == 0 && len(ans[j]) == 0 {
return false // two empty slice so one is not less than other
}
// if len(ans[i]) == 0 || len(ans[j]) == 0 {
// return len(ans[i]) == 0 // empty slice is first in ascending
// }
// both slices len() > 0
for x := range ans[i] {
if x >= len(ans[j]) {
return false
}
if ans[i][x] == ans[j][x] {
continue
}
return ans[i][x] < ans[j][x]
}
// ans[i] is of smaller length
return true }
Reverse a string
This will work for normal cases. But will not work for combined character like emojis in UTF8 encoding.
rev := []rune(str)
for i,j := 0, len(str)-1; i < j; i,j = i+1, j-1 {
rev[i], rev[j] = rev[j], rev[i]
}
fmt.Println(reverse(“Hello, 世界!”))
unicode combining characters (characters that are intended to modify other characters, like an acute accent ´ + e = é) will not work with this code.
2# Very inefficient as Go strings are immutable.
func Reverse(s string) (result string) {
for _,v := range s {
result = string(v) + result
}
return
}
3#
//Reverse reverses string using strings.Builder. It’s about 3 times faster
//than the one with using a string concatenation
func Reverse(in string) string {
var sb strings.Builder # there’s sb.grow to improve efficiency ad well.
runes := []rune(in)
for i := len(runes) - 1; 0 <= i; i– {
sb.WriteRune(runes[i]) // or sb.WriteByte(s[i]) for byte
}
return sb.String()
}
Reverse String inplace
// in place reverse
func reverse(s string) string {
r := []rune(s)
for i, j := 0, len(r) - 1; i < j; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r) }
Runes in Golang
A rune can be multiple bytes long so iterating on string using range skips to next index of rune.
const nihongo = “日本語”
for index, runeValue := range nihongo {
fmt.Printf(“%#U starts at byte position %d\n”, runeValue, index)
}
Output:
U+65E5 ‘日’ starts at byte position 0
U+672C ‘本’ starts at byte position 3
U+8A9E ‘語’ starts at byte position 6
GOPATH, GOROOT and Go workspace
GOPATH points to your Go workspace. Go workspace needs to have bin, pkg and src folders.
GOROOT points to your binary installation of Go
string to int
int64 = strconv.ParseInt(str, base, bitsize)
base - 10, 2, 16
bitsize - 32, 64
append in slice
var sli []int
sli = append(sli, 1, 2, 3, 4)
Rune Digit to int type cast
intDigit := int(ch-‘0’)
Type assertion
A type assertion provides access to an interface value’s underlying concrete value.
t := ii.(T)
This statement asserts that the interface value i holds the concrete type T and assigns the underlying T value to the variable t.
t, ok := ii.(T)
var ii interface{} = “hello”
s, ok := ii.(string) fmt.Println(s, ok) f = ii.(float64) // panic
x = ii.(structName) // panic
