Arrays & Slices

Question 1

Append slice in 2D slice without replacing

Answer 1

ans = append(ans, append([]int{}, subset…))

Question 2

Create 2D slice

Answer 2

var ans [][]int
ans = make([][]int, 0)

then each internal slice needs to be initialized as separate memory to avoid overriding.

Question 3

Pass new empty slice to a function call

Answer 3

functionCall(A, 0, make([]int, 0))
or
functionCall(A, 0, []int{}) // seems more expensive here?

Question 4

Passing slice by reference to function

Answer 4

slices are already pass by reference. Slices are passed by value, but their value is just a length and a pointer to an array

Question 5

Create slice using make

Answer 5

ans := make([]int, len(array))
b := make([]int, 0, 5) // len(b)=0, cap(b)=5

Question 6

initialize a map

Answer 6

dups := make(map[int]bool)
m := map[int]string{}

Question 7

level order traversal iterative

Answer 7

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)
    }
} } }

Question 8

Queues using slices

Answer 8

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 !”)
}

Question 9

Stack using slices

Answer 9

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
}
}

Question 10

Min and Max Values of Integers

Answer 10

math.MinInt, math.MaxInt
math.MinInt64, math.MaxInt64
math.Inf(1)

Question 11

Absolute Value

Answer 11

func Abs(y float64) float64
math.Abs(-3)

Question 12

Max and Min library functions

Answer 12

import “math”
func Max(a, b float64) float64
func Min(x, y float64) float64

Question 13

Standard input sorting

Answer 13

import “sort”
str := []string{“c”, “a”, “b”}
sort.Strings(str)

ints := []int{7, 2, 4}
sort.Ints(ints)

Question 14

Sort a string characters

Answer 14

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

Question 15

Check if input is already sorted

Answer 15

import “sort”

ints := []int{1,2,3}
check := sort.IntsAreSorted(ints)
fmt.Println(“Sorted: “, check)

Output:
Sorted: true

Question 16

Sort reverse

Answer 16

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]
})

Question 17

Custom Sort

Answer 17

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)
}

Question 18

Sort 2D slice

Answer 18

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 }

Question 19

Reverse a string

Answer 19

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()
}

Question 20

Reverse String inplace

Answer 20

// 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) }

Question 21

Runes in Golang

Answer 21

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

Question 22

GOPATH, GOROOT and Go workspace

Answer 22

GOPATH points to your Go workspace. Go workspace needs to have bin, pkg and src folders.
GOROOT points to your binary installation of Go

Question 23

string to int

Answer 23

int64 = strconv.ParseInt(str, base, bitsize)
base - 10, 2, 16
bitsize - 32, 64

Question 24

append in slice

Answer 24

var sli []int
sli = append(sli, 1, 2, 3, 4)

Question 25

Rune Digit to int type cast

Answer 25

intDigit := int(ch-‘0’)

Question 26

Type assertion

Answer 26

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