ArrayList, StringBuilder and Hash Tables
Implement an algorithm to determine if a string has all unique characters.
Method 1: bruteforce iteration O(n^2) time complexity (worst)
package main
import "fmt"
func isUnique(str string, index int, unique *bool) {
charAtIndex := string(str[index])
subStr := str[index+1:]
for _, char := range subStr {
if (charAtIndex == string(char)) {
*unique = false
break
}
}
if (*unique && index < len(str) - 1) {
isUnique(str, index+1, unique)
}
}
func main () {
str := "1"
unique := true
index := 0
isUnique(str, index, &unique)
fmt.Printf("%v string is has unique chars %v", str, unique)
}Method 2: memoization of count of chars in string and then iteration on count. gives O(n) (worst case)
package main
import "fmt"
func populateCounts(str string) map[string]int {
counts := make(map[string]int)
for _, rune := range str {
char := string(rune)
if (counts[char] >= 1) {
counts[char]++
} else {
counts[char] = 1
}
}
return counts
}
func isUnique(counts map[string]int) bool {
unique := true
for _, count := range counts {
if (count > 1) {
unique = false
break
}
}
return unique
}
func main () {
str := "wecdgfs"
counts := populateCounts(str)
fmt.Printf("%v string is has unique chars %v", str, isUnique(counts))
}Finding Permutations of a given string - can be applied where we have n!
Method 1: recursive method - O(n!)
package main
import "fmt"
func permute(ins []rune, c rune) (result []string){
for idx := 0; idx <= len(ins); idx++ {
result = append(result, string(ins[:idx])+string(c)+string(ins[idx:]))
}
return
}
func permutations(str string) []string {
var generate func (inputStr []rune, subString []string) []string
generate = func (inputStr []rune, subStrings []string) []string {
if len(inputStr) <= 0 {
return subStrings
} else {
result := [
]string{}
for _, e := range subStrings {
result = append(result, permute([]rune(e), inputStr[0])...)
}
return generate(inputStr[1:], result)
}
}
input := []rune(str)
return generate(input[1:], []string{string(input[0])})
}
func main () {
d := permutations("ABCD")
fmt.Print(d)
}Given two strings, write a method to decide if one is a permutation of the other
Method 1 - sorting both strings and comparing O(nlogn)
package main
import (
"fmt"
"sort"
"strings"
)
func compare(s1 string, s2 string) bool {
if len(s1) != len(s2) {
return false
}
s1Strings := strings.Split(s1, "")
s2Strings := strings.Split(s2, "")
sort.Strings(s1Strings)
sort.Strings(s2Strings)
return strings.Join(s1Strings, "") == strings.Join(s2Strings, "")
}
func main () {
s1 := "abcfvgffmff"
s2 := "abcffmffvgf"
fmt.Printf("%v is permutation of %v = %v", s2, s1, compare(s1, s2))
}Method 2 - memoization using a map - count all chars in string1 and compare it with string2 - O(n)
package main
import (
"fmt"
)
func compare(s1 string, s2 string) bool {
counts := make(map[rune]int)
if len(s1) != len(s2) {
return false
}
for _,rune := range s1 {
counts[rune]++
}
for _,rune := range s2 {
counts[rune]--
if (counts[rune] < 0) {
return false
}
}
return true
}
func main () {
s1 := "abcfvgffmff"
s2 := "abcffmffvgf"
fmt.Printf("%v is permutation of %v = %v", s2, s1, compare(s1, s2))
}Urlify: Write a method to replace all spaces in a string with “%20” - urlify
you are given true lenght of string and some spaces are padded at end to accomodate additional characters
package main
import (
"fmt"
)
func urlify(str string, length int) string {
newstr := []rune(str)
spaces := 0
for i := 0; i < length; i++ {
if newstr[i] == ' ' {
spaces++
}
}
index := length + spaces*2
fmt.Println(spaces*2)
for i := length - 1; i >= 0; i-- {
if newstr[i] == ' ' {
newstr[index-1] = '0'
newstr[index-2] = '2'
newstr[index-3] = '%'
index = index - 3
} else {
newstr[index - 1] = newstr[i]
index--
}
}
return string(newstr)
}
func main () {
str := "Mr John Smith "
length := 13
fmt.Printf("%v string urlify = %v", str, urlify(str, length))
}Palindrome Permutation: Give a string write a function to check if it a permutation of a palindrome.
A palindrome is a word or phrase which is same forwards and backwards example: Tact Coa - “taco cat”, “atco cta”
Method 1: using the palindrome concept we will check for char counts in string which should have event count except that atmost one can have odd count in case of a string whose length is odd
package main
import (
"fmt"
"regexp"
"strings"
)
func palindromePerm(str string) bool {
counts := make(map[rune]int)
foundOdd := false
reg,_ := regexp.Compile("[^a-zA-Z]+")
newstr := strings.ToLower(reg.ReplaceAllString(str, ""))
for _,rune := range newstr {
counts[rune]++
}
for _,count := range counts {
fmt.Println(count)
if count%2 == 1 {
if foundOdd == true {
return false
}
foundOdd = true
}
}
return true
}
func main () {
str := "Tact Coa"
fmt.Printf("%v is paindrome permutation = %v", str, palindromePerm(str))
}Rotate a Matrix by 90 degrees
Layer by Layer - we will rotate from out layer to inner layer O(R*C) clockwise
left layer -> top layer -> right layer -> bottom layer -> left layer
package main
import (
"fmt"
)
// rotateMatrix90Anticlockwise ...
func rotateMatrix90clockwise(matrix [][]int) {
n := len(matrix)
for layer := 0; layer < n/2; layer++ {
start := layer
last := n - 1 - start
for i := start; i < last; i++ {
offset := i - start
temp := matrix[start][i]
matrix[start][i] = matrix[last - offset][start]
matrix[last-offset][start] = matrix[last][last - offset]
matrix[last][last - offset] = matrix[i][last]
matrix[i][last] = temp
}
}
}
// main ...
func main() {
matrix := [][]int{[]int{3,4,5},[]int{5,6,9},[]int{3,6,5}}
fmt.Println("matrix", matrix)
rotateMatrix90clockwise(matrix)
fmt.Println("matrix", matrix)
}inplace rotation - transpose matrix -> reverse columns O(R*C) anticlockwise - for clockwise reverse rows
package main
import (
"fmt"
)
// transposeMatrix ...
func transposeMatrix(matrix [][]int) {
for i := 0; i < len(matrix); i++ {
for j := i+1; j < len(matrix[0]); j++ {
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
}
}
}
// reverseColumns ...
func reverseColumns(matrix [][]int) {
columns := len(matrix[0])
for i := 0; i < columns; i++ {
for j, k := 0, columns - 1; j < k; j++ {
matrix[j][i], matrix[k][i] = matrix[k][i], matrix[j][i]
k--
}
}
}
func main() {
matrix := [][]int{[]int{3,4,5},[]int{5,6,9},[]int{3,6,5}}
fmt.Println("matrix", matrix)
transposeMatrix(matrix)
fmt.Println("transpose matrix", matrix)
reverseColumns(matrix)
fmt.Println("90 degree rotated matrix", matrix)
}Write an algorithm such that if an element in M*N matrix is 0, it’s entire row and column is made 0
we will iterate over matrix and keep map of row and column where 0 occurred. Then iterate over map and make entries of those rows and columns 0
package main
import (
"fmt"
)
// zeroMatrix ...
func zeroMatrix(matrix [][]int) {
rows, columns := make(map[int]bool), make(map[int]bool)
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == 0 {
rows[i] = true
columns[j] = true
}
}
}
for key,_ := range rows {
for i := 0; i < len(matrix[key]); i++ {
matrix[key][i] = 0
}
}
for key, _ := range columns {
for i := 0; i < len(matrix); i++ {
matrix[i][key] = 0
}
}
}
// main ...
func main() {
matrix := [][]int{[]int{1,0,2},[]int{2,0,5},[]int{0,2,5},[]int{1,2,3}}
fmt.Println("matrix", matrix)
zeroMatrix(matrix)
fmt.Println("matrix", matrix)
}Assume you have a method isSubstring which checks if one word is substring of another. Given two strings, s1 and s2, write code to check if s2 is rotation of s1 using only one call to isSubstring
example - “waterbottle” is a rotation of “erbottlewat”
package main
import (
"fmt"
"strings"
)
// stringRotation ...
func stringRotation(s1 string, s2 string) bool {
if len(s1) != len(s2) {
return false
}
return strings.Contains(s1+s1, s2)
}
// main ...
func main() {
s1 := "waterbottle"
s2 := "erbottlewat"
fmt.Println("%v is rotation of %v = %v", s2, s1, stringRotation(s1, s2))
}