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