How to Cancel a Goroutine in Go

The example below shows how to cancel a goroutine while is in the middle of executing a long-running task.

package main

import (
    "context"
    "fmt"
    "time"
)

func main() {
    busyChan := make(chan bool)

    ctx, cancel := context.WithCancel(context.Background())
    go func(ctx context.Context) {
        for {
            select {
            case <-busyChan:
                fmt.Println("Pretending to be very busy")
                time.Sleep(5000 * time.Second)
            case <-ctx.Done():
                return
            }
        }
    }(ctx)
    busyChan <- true
    fmt.Println("Doing some other things")
    time.Sleep(3 * time.Second)
    fmt.Println("Stopping the goroutine")
    cancel()
}

Output:

Prentending to be very busy
Doing some other things
Stopping the goroutine

How to Use Vendoring in Go

Vendoring is a way to put dependencies in a Go project without having to mess with the GOPATH. The idea is simple, that is to put the dependencies in a directory called "vendor".

awesomego/
|-- foo (this directory contains a library, i.e. non-main package)
|   `-- foo.go
|-- main.go (this is the main program)
`-- vendor (this is where the third-party libs live)
    `-- goini
        |-- goini.go
        |-- goini_test.go
        |-- LICENSE
        |-- README.md
        `-- testdata
            |-- test_expected.ini
            `-- test.ini

The project structure above has the following benefits.

1. It can be used to build a library.
2. It can be used to build an executable.
3. It is go-gettable.

This is an example of using it in a standard Go workspace.

go-workspace/
`-- src
    `-- awesomego
        |-- foo
        |   `-- foo.go
        |-- main.go
        `-- vendor
            `-- goini
                |-- goini.go
                |-- goini_test.go
                |-- LICENSE
                |-- README.md
                `-- testdata
                    |-- test_expected.ini
                    `-- test.ini

To build it as a library:

GOPATH=`pwd` go install awesomego/foo

To build it as an executable:

GOPATH=`pwd` go install awesomego

Compile-Time Enum in Go

Unlike other languages, Go does not support enum. However, it is pretty straightforward to create something that behaves similar to enum. There are a lot of articles on the internet on how to create an enum in Go, which pretty much looks like below.

package main

import (
    "fmt"
)

type myType string

const (
    Foo myType = "foo"
    Bar myType = "bar"
)

func doSomething(t myType) {
    fmt.Println(t)
}

func main() {
    // baz := "baz"
    // This will result in compilation error:
    // "cannot use baz (type string) as type myType in argument to doSomething"
    // doSomething(baz)

    // However, this is allowed.
    doSomething("baz")
}

As you can see in the code above, calling doSomething("baz") does not result in a compilation error. To fix that, we can change the code to look like below.

package main

import (
    "fmt"
)

type myType string

const (
    Foo myType = "foo"
    Bar myType = "bar"
)

func doSomething(t *myType) {
    fmt.Println(*t)
}

func main() {
    // This will now result in a compilation error.
    // doSomething("baz")

    baz := myType("baz")
    doSomething(&baz)
}

How to Create a Command Line Spinner in Go

package main

import "fmt"
import "time"

func main() {
    chars := "|/-\\"
    i := 0
    for {
        i++
        char := chars[i%len(chars)]
        fmt.Printf("\rDownloading: %c", char)
        time.Sleep(100 * time.Millisecond)
    }
}

How to Organize a Go Project

The official has a good information on how to structure your Go code. In this blog, I am going to explain a little bit more about it. Let's say we want to create a Go project containing a command and a package.

workspace1/
|-- build.sh
`-- src
    `-- mylib
        |-- hello
        |   `-- hello.go (package)
        `-- main.go (command)

hello.go

package hello

import "fmt"

func SayHello() {
    fmt.Println("Hello")
}

main.go

package main

import "mylib/hello"

func main() {
    hello.SayHello()
}

build.sh

#!/bin/bash

export GOPATH=`pwd`
go install mylib/hello
go install mylib

Calling build.sh will create this structure.

workspace1/
|-- bin
|   `-- mylib (executable)
|-- build.sh
|-- pkg
|   `-- linux_amd64
|       `-- mylib
|           `-- hello.a (library)
`-- src
    `-- mylib
        |-- hello
        |   `-- hello.go (package)
        `-- main.go (command)

In order to make mylib project go-gettable, let's make it into a Git project. Take a note that we will be creating a Git project in the mylib directory and not in the workspace1 directory.

1. cd workspace1/src/mylib
2. git init
3. git add .
4. git commit -m "Initial commit"
5. Push this repository to the remote URL

Now let's create another project that uses mylib. This new project is a simple project that uses mylib.

workspace2/
|-- build.sh
`-- src
    `-- myapp
        `-- app
            `-- app.go (command)

1. cd workspace2
2. git init
3. git add submodule [mylib_git_url] src/mydomain/user/mylib (the src/mydomain/user is just a convention, you can also set the path to src/mylib)

After the submodule addition, we will have this structure.

workspace2/
|-- build.sh
`-- src
    |-- myapp
    |   `-- app
    |       `-- app.go (command)
    `-- mydomain
        `-- user
            `-- mylib
                |-- hello
                |   `-- hello.go (package)
                `-- main.go (command)

app.go

package main

import (
    "fmt"
    "mydomain/user/mylib/hello"
)

func main() {
    fmt.Println("Do something")
    hello.SayHello()
}

build.sh

#!/bin/bash

export GOPATH=`pwd`
go install mydomain/user/mylib/hello
go install myapp/app

Calling build.sh will create this structure.

workspace2/
|-- bin
|   `-- app (executable)
|-- build.sh
|-- pkg
|   `-- linux_amd64
|       `-- mydomain
|           `-- user
|               `-- mylib
|                   `-- hello.a (library)
`-- src
    |-- myapp
    |   `-- app
    |       `-- app.go (command)
    `-- mydomain
        `-- user
            `-- mylib
                |-- hello
                |   `-- hello.go (package)
                `-- main.go (command - not used)

How to Create a Simple REST Server in Go

Below is an example on how to create a simple REST server in Go.

package main

import (
    "encoding/json"
    "log"
    "net/http"
    "strconv"
)

type Hello struct {
    Message string `json:"message"`
}

func HelloServer(w http.ResponseWriter, req *http.Request) {
    log.Println("Received a request from ", req.RemoteAddr)
    w.Header().Set("Content-Type", "application/json")
    if req.Method == "GET" {
        encoder := json.NewEncoder(w)
        hello := Hello{"Hello World"}
        encoder.Encode(hello)
    }
}

func main() {
    port := 8080
    // serve static content
    http.Handle("/", http.FileServer(http.Dir("html")))
    http.HandleFunc("/hello/", HelloServer)
    log.Println("Starting HTTP server at", port)
    err := http.ListenAndServe(":"+strconv.Itoa(port), nil)
    if err != nil {
        log.Fatal("Unable to start the server: ", err)
    }
}

How to Cross Compile Go Programs

If you download the Go binary for a particular platform, most likely that go binary distribution does not come with support for cross-compiling.

cd myapp
GOOS=windows GOARCH=amd64 go build

go build runtime: windows/amd64 must be bootstrapped using make.bash

In order to add support for cross-compiling in your Go distribution, you need to do the following.

cd $GOROOT/src
GOOS=windows GOARCH=amd64 ./make.bash --no-clean

In this example I am adding cross-compile support to target Windows 64-bit.

cd myapp
GOOS=windows GOARCH=amd64 go build

Now you can easily build Windows 64-bit binaries on a Linux.

How to Solve Diagonal Print

Given a string and a number, and print the string diagonally filling in empty space with periods and going down as many lines as the given number. So "Peter piper picked a peck of pickled peppers" with n = 10 becomes

P.........r......... .........i.........p...
.e......... .........p.........c.........e..
..t.........p.........e.........k.........r.
...e.........i.........c.........l.........s
....r.........c.........k.........e.........
..... .........k......... .........d........
......P.........e.........o......... .......
.......i.........d.........f.........P...... 
........p......... ......... .........e.....
.........e.........a.........p.........p....

package main

import (
    "fmt"
    "os"
    "strconv"
)

func main() {
    str := os.Args[1]
    n, _ := strconv.Atoi(os.Args[2])
    for i := 0; i < n; i++ {
        for k := 0; k < i; k++ {
            fmt.Print(".")
        }
        for j := 0; j < len(str)-i; j++ {
            if (j % n == 0 && j+1 < len(str)) {
                fmt.Print(string(str[j+i]))
            } else {
                fmt.Print(".")
            }
        }
        fmt.Println()
    }
}

How to Convert a BST to a Doubly Linked List In-Place

Problem:
Convert a BST to a doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

package main

import (
    "fmt"
)

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

type LinkedList struct {
    Front *Node
    Back  *Node
}

// this is the actual algorithm that converts a BSt into a doubly linked list
// the rest of the code is just to make unit testing easier
func (l *LinkedList) ToLinkedList(node *Node) {
    if node == nil {
        return
    }
    l.ToLinkedList(node.Left)
    node.Left = l.Back
    if l.Back != nil {
        l.Back.Right = node
    } else {
        l.Front = node
    }
    l.Back = node
    l.ToLinkedList(node.Right)
}

type BST struct {
    Root *Node
}

func (b *BST) Add(value int) {
    b.Root = b.add(b.Root, value)
}

func (b *BST) add(node *Node, value int) *Node {
    if node == nil {
        return &Node{value, nil, nil}
    }
    if node.Value > value {
        node.Left = b.add(node.Left, value)
    } else if node.Value < value {
        node.Right = b.add(node.Right, value)
    }
    return node
}

func main() {
    values := []int{8, 3, 10, 1, 6, 14, 4, 7, 13}
    bst := BST{}
    for _, v := range values {
        bst.Add(v)
    }
    ll := LinkedList{}
    ll.ToLinkedList(bst.Root)
    for n := ll.Front; n != nil; n = n.Right {
        fmt.Print(n.Value, " ")
    }
    fmt.Println()
    for n := ll.Back; n != nil; n = n.Left {
        fmt.Print(n.Value, " ")
    }
    fmt.Println()
}

Output:

1 3 4 6 7 8 10 13 14 
14 13 10 8 7 6 4 3 1

How to Solve Max Volume Problem

My solution for max volume problem.

package main

import (
    "fmt"
)

func maxVolume(a []int) int {
    left := 0
    right := len(a) - 1
    volume := 0
    total := 0
    for left != right {
        if a[left] <= a[right] {
            for i := left + 1; i < len(a); i++ {
                if a[left] > a[i] {
                    volume += a[left] - a[i]
                } else {
                    left = i
                    total += volume
                    volume = 0
                    break
                }
            }
        } else {
            for i := right - 1; i >= left; i-- {
                if a[right] > a[i] {
                    volume += a[right] - a[i]
                } else {
                    right = i
                    total += volume
                    volume = 0
                    break
                }
            }
        }
    }
    return total
}

func main() {
    fmt.Println(maxVolume([]int{2, 5, 1, 2, 3, 4, 7, 7, 6}) == 10)
    fmt.Println(maxVolume([]int{2, 5, 1, 3, 1, 2, 1, 7, 7, 6}) == 17)
    fmt.Println(maxVolume([]int{2, 3, 1, 2, 3, 1, 3}) == 5)
    fmt.Println(maxVolume([]int{1, 2, 3, 4, 5, 6, 7, 8, 9}) == 0)
    fmt.Println(maxVolume([]int{9, 8, 7, 6, 5, 4, 3, 2, 1}) == 0)
    fmt.Println(maxVolume([]int{1, 1, 1, 1, 1}) == 0)
    fmt.Println(maxVolume([]int{1, 0, 1}) == 1)
    fmt.Println(maxVolume([]int{5, 0, 5}) == 5)
    fmt.Println(maxVolume([]int{5, 0, 4}) == 4)
    fmt.Println(maxVolume([]int{4, 0, 5}) == 4)
    fmt.Println(maxVolume([]int{4, 0, 5, 0, 2}) == 6)
    fmt.Println(maxVolume([]int{0, 1, 0, 1, 0}) == 1)
    fmt.Println(maxVolume([]int{0, 1, 0, 0, 1, 0}) == 2)
    fmt.Println(maxVolume([]int{4, 2, 2, 1, 1, 1, 3}) == 8)
    fmt.Println(maxVolume([]int{0, 3, 2, 1, 4}) == 3)
    fmt.Println(maxVolume([]int{1, 0, 1, 0}) == 1)
    fmt.Println(maxVolume([]int{1, 0, 1, 2, 0, 2}) == 3)
    fmt.Println(maxVolume([]int{2, 5, 1, 2, 3, 4, 7, 7, 6}) == 10)
    fmt.Println(maxVolume([]int{5, 1, 0, 1}) == 1)
    fmt.Println(maxVolume([]int{2, 5, 1, 2, 3, 4, 7, 7, 6, 3, 5}) == 12)
    fmt.Println(maxVolume([]int{3, 0, 1, 0, 2}) == 5)
}

How to Solve Spiral Problem

My solution for spiral problem.

package main

import (
    "fmt"
)

func spiral(height, width, row, col int) []int {
    a := createSlice(height, width)
    result := []int{}
    r := row - 1
    c := col - 1
    result = append(result, a[r][c])
    x := 1
    for z := 0; (height * width) != len(result); z++ {
        for i := 0; i < x; i++ {
            r, c = up(r, c)
            if !outOfBoundary(height, width, r, c) {
                result = append(result, a[r][c])
            }
        }
        for i := 0; i < x; i++ {
            r, c = left(r, c)
            if !outOfBoundary(height, width, r, c) {
                result = append(result, a[r][c])
            }
        }
        x += 1
        for i := 0; i < x; i++ {
            r, c = down(r, c)
            if !outOfBoundary(height, width, r, c) {
                result = append(result, a[r][c])
            }
        }
        for i := 0; i < x; i++ {
            r, c = right(r, c)
            if !outOfBoundary(height, width, r, c) {
                result = append(result, a[r][c])
            }
        }
        x += 1
    }
    return result
}

func outOfBoundary(height, width, row, col int) bool {
    return !((row >= 0 && row < height) && (col >= 0 && col < width))
}

func left(row, col int) (int, int) {
    return row, col - 1
}

func right(row, col int) (int, int) {
    return row, col + 1
}

func up(row, col int) (int, int) {
    return row - 1, col
}

func down(row, col int) (int, int) {
    return row + 1, col
}

func createSlice(height, width int) [][]int {
    a := make([][]int, height)
    n := 1
    for i := 0; i < height; i++ {
        a[i] = make([]int, width)
        for j := 0; j < width; j++ {
            a[i][j] = n
            n += 1
        }
    }
    return a
}

func main() {
    fmt.Println(spiral(5, 5, 3, 3))
    fmt.Println(spiral(2, 4, 1, 2))
    fmt.Println(spiral(5, 5, 4, 2))
}

How to Call C++ from Go

.
└── src
    └── cgotest
        ├── hello
        │   ├── cpp
        │   │   └── hellocpp.cpp
        │   ├── hello.go
        │   ├── include
        │   │   └── hellocpp.h
        │   └── lib
        │       └── libhellocpp.so
        └── main.go

hellocpp.h

#ifndef _HELLOCPP_H_
#define _HELLOCPP_H_

#ifdef __cplusplus
extern "C" {
#endif
    void SayHello();
#ifdef __cplusplus
}
#endif

#endif

hellocpp.cpp

#include <iostream>
#include "hellocpp.h"
using namespace std;

void SayHello() {
    cout << "Hello from C++" << endl;
}

Let's now create a C++ shared library.

cd $GOPATH/src/cgotest/hello
mkdir lib
g++ -Wall -shared -fpic cpp/hellocpp.cpp -Iinclude -o lib/hellocpp.so

hello.go

package hello

// #cgo CFLAGS: -Iinclude
// #cgo LDFLAGS: -Llib -lhellocpp
// #include "hellocpp.h"
import "C"

func HelloFromCpp() {
    C.SayHello()
}

main.go

package main

import "cgotest/hello"

func main() {
    hello.HelloFromCpp()
}

There seems to be a bug that makes setting relative paths in LDFLAGS not to work. The workaround is to set LIBRARY_PATH env variable using absolute path.

cd $GOPATH
export LIBRARY_PATH=$GOPATH/src/cgotest/hello/lib
export LD_LIBRARY_PATH=$LIBRARY_PATH
go build cgotest
./cgotest

Output:

Hello from C++

How to Solve Triangle Minimal Path in Go

Write a function which calculates the sum of the minimal path through a triangle. The triangle is represented as a collection of vectors. The path should start at the top of the triangle and move to an adjacent number on the next row until the bottom of the triangle is reached.

assert
f(  [[1]
    [2 4]
   [5 1 4]
  [2 3 4 5]] ) == 7 ; 1+2+1+3

assert
f(    [[3]
      [2 4]
     [1 9 3]
    [9 9 2 4]
   [4 6 6 7 8]
  [5 7 3 5 1 4]] ) == 20 ; 3+4+3+2+7+1

This is an iterative solution in Go.

package main

import (
    "fmt"
)

func min(m map[int][]int) int {
    r := m[0][0]
    for _, v := range m {
        for _, v1 := range v {
            if r > v1 {
                r = v1
            }
        }
    }
    return r
}

func triangleMinPath(input [][]int) int {
    result := map[int][]int{}
    result[0] = input[0]
    for i := 1; i < len(input); i++ {
        result = minPath(input[i], result)
    }
    return min(result)
}

func minPath(input []int, accu map[int][]int) map[int][]int {
    result := map[int][]int{}
    for i := 0; i < len(input); i++ {
        for j := 0; j < len(accu[i]); j++ {
            if _, ok := result[i]; !ok {
                result[i] = []int{}
            }
            result[i] = append(result[i], input[i]+accu[i][j])
            if _, ok := result[i+1]; !ok {
                result[i+1] = []int{}
            }
            result[i+1] = append(result[i+1], input[i+1]+accu[i][j])
        }
    }
    return result
}

func main() {
    fmt.Println(triangleMinPath([][]int{{1}, {2, 4}, {5, 1, 4}, {2, 3, 4, 5}})) // 7
    fmt.Println(triangleMinPath([][]int{{3}, {2, 4}, {1, 9, 3}, {9, 9, 2, 4}, {4, 6, 6, 7, 8}, {5, 7, 3, 5, 1, 4}})) // 20
    fmt.Println(triangleMinPath([][]int{{3}})) // 3
    fmt.Println(triangleMinPath([][]int{{3}, {1, 2}})) // 4
}

How to Rearrange an Array in Alternate Positive and Negative Position

Problem:
Given an array containing both positive and negative elements, arrange in such a manner; 1 positive number, then 1 negative,then 1 positive and so on. If there are more negative numbers, extra negative numbers should be kept at the end and vice versa. Note that the order of negative and positive elements should be same in the modified array and you are not allowed to use any extra space.

Sample inputs and outputs:

Input : [1 -2 3 4 -5 -6 7 8 -9 10 11]
Output: [1 -2 3 -5 4 -6 7 -9 8 10 11]

Input : [-1 2 3 4 -5 -6 7 8 -9 10 11]
Output: [-1 2 -5 3 -6 4 -9 7 8 10 11]

Input : [-1 2 -3 4 -5 6 -7 8 -9 10 11]
Output: [-1 2 -3 4 -5 6 -7 8 -9 10 11]

Input : [1 2 3 4 5 6 7 8 9 10 11]
Output: [1 2 3 4 5 6 7 8 9 10 11]

Input : [-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11]
Output: [-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11]

package main

import (
    "fmt"
)

func shiftAndSwap(a []int, fromIdx, toIdx int) {
    tmp := a[toIdx]
    for j := toIdx; j > fromIdx; j-- {
        a[j] = a[j-1]
    }
    a[fromIdx] = tmp
}

func arrange(a []int) {
    positive := false
    if a[0] < 0 {
        positive = true
    }
    fromIdx := 1
    for i := 1; i < len(a); i++ {
        if positive {
            if a[i] >= 0 {
                if fromIdx != i {
                    shiftAndSwap(a, fromIdx, i)
                    i = fromIdx
                }
                positive = false
                fromIdx = i + 1
            }
        } else { // negative
            if a[i] < 0 {
                if fromIdx != i {
                    shiftAndSwap(a, fromIdx, i)
                    i = fromIdx
                }
                positive = true
                fromIdx = i + 1
            }
        }
    }
}

func main() {
    a := []int{1, -2, 3, 4, -5, -6, 7, 8, -9, 10, 11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)

    a = []int{-1, 2, 3, 4, -5, -6, 7, 8, -9, 10, 11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)

    a = []int{-1, 2, -3, 4, -5, 6, -7, 8, -9, 10, 11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)
    
    a = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)

    a = []int{-1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)
}

How to Solve Maximum Sum of a Subsequence Problem

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Input: [3, 2, 7, 10]
Output: [3 10] 13

Input: [3, 2, 5, 10, 7]
Output: [3 5 7] 15

Input: [3, 20, 5, 10, 7]
Output: [20 10] 30

Input: [3, 10, 30, 100, 40]
Output: [10 100] 110

Input: [3, 10, 1, 2, 3, 30, 4, 40, 5, 6, 50]
Output: [10 2 30 40 50] 132

This solution is not an optimal solution.

package main

import (
    "fmt"
)

func sum(a []int) int {
    s := 0
    for _, v := range a {
        s += v
    }
    return s
}

func maxSumSubsequence(a []int) []int {
    result := [][]int{}
    // odd
    recurseMaxSumSub(a, 0, []int{}, &result)
    // even
    recurseMaxSumSub(a, 1, []int{}, &result)
    max := 0
    var maxSubsequence []int
    for _, v := range result {
        s := sum(v)
        if max == 0 {
            max = s
            maxSubsequence = v
        } else if max < s {
            max = s
            maxSubsequence = v
        }
    }
    return maxSubsequence
}

func recurseMaxSumSub(a []int, idx int, accu []int, result *[][]int) {
    if idx < len(a) {
        recurseMaxSumSub(a, idx+2, append(accu, a[idx]), result)
    } else {
        *result = append(*result, accu)
    }

    if idx+1 < len(a) {
        recurseMaxSumSub(a, idx+3, append(accu, a[idx+1]), result)
    } else {
        *result = append(*result, accu)
    }
}

func main() {
    out := maxSumSubsequence([]int{3, 2, 7, 10})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 2, 5, 10, 7})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 20, 5, 10, 7})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 10, 30, 100, 40})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 10, 1, 2, 3, 30, 4, 40, 5, 6, 50})
    fmt.Println(out, sum(out))
}

How to Solve Word Search Puzzle

Write a program that builds a 2D array from a given input string and search for some words from the input and then output the indices for every word found. The search can be horizontal, vertical, and diagonal.

Input:

String: SCALAALHPCUAMNJWAYDXBOSRVSTRVOYOAWKHUQZPJVUEOSNNPFOKLNTLMCEGULA
Number of column: 9
Words to search: RUBY, PYTHON, JAVA, HASKELL, GO, LUA, ML, AWK, JS, SCALA, CPP, RUST  

Output:

[S C A L A A L H P]
[C U A M N J W A Y]
[D X B O S R V S T]
[R V O Y O A W K H]
[U Q Z P J V U E O]
[S N N P F O K L N]
[T L M C E G U L A]

SCALA [{0 0} {0 1} {0 2} {0 3} {0 4}]
HASKELL [{0 7} {1 7} {2 7} {3 7} {4 7} {5 7} {6 7}]
PYTHON [{0 8} {1 8} {2 8} {3 8} {4 8} {5 8}]
ML [{1 3} {0 3}]
JS [{1 5} {2 4}]
RUST [{3 0} {4 0} {5 0} {6 0}]
AWK [{3 5} {3 6} {3 7}]
JAVA [{4 4} {3 5} {2 6} {1 7}]
LUA [{5 7} {4 6} {3 5}]
ML [{6 2} {6 1}]
CPP [{6 3} {5 3} {4 3}]
GO [{6 5} {5 5}]

package main

import (
    "fmt"
)

type index struct {
    row int
    col int
}

func create2DSlice(s string, nCol int) [][]string {
    nRow := len(s) / nCol
    slice := make([][]string, nRow, nRow)
    idx := 0
    for i := 0; i < nRow; i++ {
        slice[i] = make([]string, nCol, nCol)
        for j := 0; j < nCol; j++ {
            slice[i][j] = string(s[idx])
            idx++
        }
    }
    return slice
}

func isOutOfRange(nRow, nCol, fromRow, toRow, fromCol, toCol int) bool {
    if fromRow >= 0 && fromRow < nRow && fromCol >= 0 && fromCol < nCol &&
        toRow >= 0 && toRow < nRow && toCol >= 0 && toCol < nCol {
        return false
    }
    return true
}

func search(slice [][]string, word string, nRow, nCol, fromRow, toRow, fromCol, toCol int) {
    rowInc := 1
    if fromRow > toRow {
        rowInc = -1
    } else if fromRow == toRow {
        rowInc = 0
    }
    colInc := 1
    if fromCol > toCol {
        colInc = -1
    } else if fromCol == toCol {
        colInc = 0
    }
    if !isOutOfRange(nRow, nCol, fromRow, toRow, fromCol, toCol) {
        str := ""
        indices := []index{}
        for i, r, c := 0, fromRow, fromCol; i < len(word); i++ {
            indices = append(indices, index{r, c})
            str += slice[r][c]
            r = r + rowInc
            c = c + colInc
        }
        w := str
        if w == word {
            fmt.Println(word, indices)
        }
    }
}

func wordSearch(s string, nCol int, words []string) {
    twoDSlice := create2DSlice(s, nCol)
    for i := 0; i < len(twoDSlice); i++ {
        fmt.Println(twoDSlice[i])
    }
    fmt.Println("========")
    fmt.Println("Solution")
    fmt.Println("========")
    for row := 0; row < len(twoDSlice); row++ {
        for col := 0; col < len(twoDSlice[row]); col++ {
            for _, word := range words {
                // up
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row-len(word)+1, col, col)
                // down
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row+len(word)-1, col, col)
                // left
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row, col, col-len(word)+1)
                // right
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row, col, col+len(word)-1)
                // upper left diagonal
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row-len(word)+1, col, col-len(word)+1)
                // upper right diagonal
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row-len(word)+1, col, col+len(word)-1)
                // lower left diagonal
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row+len(word)-1, col, col-len(word)+1)
                // lower right diagonal
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row+len(word)-1, col, col+len(word)-1)
            }
        }
    }
}

func main() {
    s := "SCALAALHPCUAMNJWAYDXBOSRVSTRVOYOAWKHUQZPJVUEOSNNPFOKLNTLMCEGULA"
    words := []string{"RUBY", "PYTHON", "JAVA", "HASKELL", "GO", "LUA", "ML",
        "AWK", "JS", "SCALA", "CPP", "RUST"}
    wordSearch(s, 9, words)
}

How to Solve Minimum Difference Problem

Given two arrays, sorted and exactly the same length, write a function that finds a pair of numbers, one from each of the arrays,such that the difference between both is as small as possible.

Input:
[0, 3, 5, 8, 10], [6, 9, 12, 13, 14]
Output:
[5, 6]

Input:
[7.12, 15, 20, 21], [1, 5, 9, 13, 17]
Output:
[12, 13]

Input:
[6, 10, 15, 18, 21], [16, 17, 18, 23, 27]
Output:
[8, 8]

package main

import (
    "fmt"
)

func diff(n int) int {
    if n < 0 {
        return n * -1
    }
    return n
}

func minDiff(a []int, b []int) (int, int) {
    min := -1
    var result1, result2 int
    for i, j := 0, 0; i < len(a) && j < len(b); {
        newMin := diff(a[i] - b[j])
        if min == -1 {
            min = newMin
            result1, result2 = a[i], b[j]
        } else {
            if newMin < min {
                min = newMin
                result1, result2 = a[i], b[j]
            }
        }
        if a[i] < b[j] {
            i++
        } else {
            j++
        }
    }
    return result1, result2
}

func main() {
    fmt.Println(minDiff([]int{0, 3, 5, 8, 10}, []int{6, 9, 12, 13, 14}))
    fmt.Println(minDiff([]int{7, 12, 15, 20, 21}, []int{1, 5, 9, 13, 17}))
    fmt.Println(minDiff([]int{6, 10, 15, 18, 21}, []int{16, 17, 18, 23, 27}))
}

How to Solve Balancing Arrays Problem

Given an array of numbers, return the index at which the array can be balanced by all numbers on the left side add up the sum of all numbers of the right side.

For example:
an array with [1,5,6,7,9,10] can be balanced by splitting the array at position 4
an array with [1, 5, 6, 7, 9, 10] can be balanced by splitting the array at position 4
an array with [3, 8, 4, 15] can be balanced by splitting the array at position 3
an array with [1, 8, 1, 2, 8]) can be balanced by splitting the array at position 3
an array with [1, 3, 5, 1, 2] can't be balanced, hence position -1

package main

import (
    "fmt"
)

func balancingArrays(slice []int) int {
    left := 0
    right := len(slice) - 1
    sumLeft := 0
    sumRight := 0
    for left <= right {
        if sumLeft < sumRight {
            sumLeft += slice[left]
            left++
        } else {
            sumRight += slice[right]
            right--
        }
    }
    if sumLeft == sumRight {
        return left
    }
    return -1
}

func main() {
    fmt.Println(balancingArrays([]int{1, 5, 6, 7, 9, 10})) // 4
    fmt.Println(balancingArrays([]int{3, 8, 4, 15}))       // 3
    fmt.Println(balancingArrays([]int{1, 8, 1, 2, 8}))     // 3
    fmt.Println(balancingArrays([]int{1, 3, 5, 1, 2}))     // -1
}

How to Solve the Longest Substring Problem

Find the longest sub-string of the given string that contains, at most, two unique characters. If you find multiple sub-strings that match the description, print the last sub-string (furthest to the right).

Inputs:

abbccc
abcabcabcabccc
qwertyytrewq
aaabaaabccbcccbde
abcde
aaaa
aabb

Outputs:

bbccc
bccc
tyyt
bccbcccb
de
aaaa
aabb

package main

import (
    "fmt"
)

type Substring struct {
    begin int
    end   int
}

func longestSubstring(str string) string {
    m := map[uint8]bool{}
    substrings := []Substring{}
    for i := 0; i < len(str); i++ {
        if _, ok := m[str[i]]; !ok {
            m[str[i]] = true
        }
        if len(m) == 3 {
            m = map[uint8]bool{}
            m[str[i-1]] = true
            m[str[i]] = true
            if len(substrings) == 0 {
                substrings = append(substrings, Substring{0, i - 1})
            } else {
                begin := substrings[len(substrings)-1].end
                c := str[begin]
                for j := begin; str[j] == c && j != 0; j-- {
                    begin--
                }
                substrings = append(substrings, Substring{begin + 1, i - 1})
            }
        }
    }
    if len(m) == 2 {
        if len(substrings) == 0 {
            substrings = append(substrings, Substring{0, len(str) - 1})
        } else {
            begin := substrings[len(substrings)-1].end
            c := str[begin]
            for j := begin; str[j] == c && j != 0; j-- {
                begin--
            }
            substrings = append(substrings, Substring{begin + 1, len(str) - 1})
        }
    } else {
        return str
    }
    var longest string
    for _, v := range substrings {
        substring := str[v.begin : v.end+1]
        if len(longest) <= len(substring) {
            longest = substring
        }
    }
    return longest
}

func main() {
    fmt.Println(longestSubstring("abbccc"))
    fmt.Println(longestSubstring("abcabcabcabccc"))
    fmt.Println(longestSubstring("qwertyytrewq"))
    fmt.Println(longestSubstring("aaabaaabccbcccbde"))
    fmt.Println(longestSubstring("abcde"))
    fmt.Println(longestSubstring("aaaa"))
    fmt.Println(longestSubstring("aabb"))
}

How to Solve On-Screen Keyboard Problem

Problem description:

Given the English alphabet, 'a' through 'z' (lowercase), and an imaginary onscreen keyboard with the letters laid out in 6 rows and 5 columns:

a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z

Using a remote control - (up - 'u', down 'd', left 'l', right 'r' and enter '!'), write a function that given a word will produce the sequence of key presses required to type out the word on the onscreen keyboard. The function should return the sequence string. The optimal solution will require the least keystrokes. There could be more than one optimal solutions. Assume the initial position is 'a'.

Input:

hello

Output:

drr!urr!ddlll!!rrr!

package main

import (
    "fmt"
)

func position(idx, ncols int) (int, int) {
    row := (idx - int('a')) / ncols
    col := (idx - int('a')) - (ncols * row)
    return row, col
}

func printKeyboard(ncols int) {
    m := [][]rune{}
    for i := 'a'; i <= 'z'; {
        chars := make([]rune, ncols)
        for j := 0; j < ncols; j++ {
            if i > 'z' {
                break
            }
            chars[j] = i
            i++
        }
        m = append(m, chars)
    }
    for i := range m {
        for j := range m[i] {
            fmt.Print(string(m[i][j]), " ")
        }
        fmt.Println()
    }
}

func showKeystrokes(word string, ncols int) {
    printKeyboard(ncols)
    fmt.Print(word + ": ")
    startRow, startCol := 0, 0
    for i := 0; i < len(word); i++ {
        nextRow, nextCol := position(int(word[i]), ncols)
        if startRow < nextRow {
            for step := 0; step < nextRow-startRow; step++ {
                fmt.Print("d")
            }
        } else if startRow > nextRow {
            for step := 0; step < startRow-nextRow; step++ {
                fmt.Print("u")
            }
        }

        if startCol < nextCol {
            for step := 0; step < nextCol-startCol; step++ {
                fmt.Print("r")
            }
        } else if startCol > nextCol {
            for step := 0; step < startCol-nextCol; step++ {
                fmt.Print("l")
            }
        }
        fmt.Print("!")
        startRow, startCol = nextRow, nextCol
    }
    fmt.Println()
}

func main() {
    showKeystrokes("hello", 5)
}