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