Categories
Go: Remainder Sorting
Date
Author
Implement a function that receives an array of strings and sorts them based on the following heuristics:
- The primary sort is by increasing remainder of the strings’ lengths, modulo 3.
- If multiple strings have the same remainder, they should be sorted in alphabetical order.
Example
strArr = [“Colorado”, “Utah”, “Wisconsin”, “Oregon”]
Their lengths are [8, 4, 9, 6]. The remainders, modulo 3, are [2, 1, 0, 0]. Oregon and Wisconsin have the same remainder and are further sorted alphabetically. Here is the sorted array showing (string, length, length modulo 3): [(‘Oregon’, 6, 0), (‘Wisconsin’, 9, 0), (‘Utah’, 4, 1), (‘Colorado’, 8, 2)]. Return the sorted array [“Oregon”, Wisconsin”, “Utah”, “Colorado”].
Function Description
Complete the function RemainderSorting in the editor below. The function return an array of strings.
RemainderSorting has the following parameter(s):
strArr [n]string: an array of strings
Constraints
- 1 ≤ length of strArr ≤ 700
- 1 ≤ length of each string ≤ 100
SOLUTION:
package main
import (
"bufio"
"fmt"
"io"
"os"
"sort"
"strconv"
"strings"
)
/*
* Complete the 'RemainderSorting' function below (and other code for sorting if needed).
*
* The function is expected to return a STRING_ARRAY.
* The function accepts STRING_ARRAY strArr as parameter.
*/
// Custom struct to hold string, length, and length modulo 3
type StringInfo struct {
Str string
Length int
Remain int
}
func RemainderSorting(strArr []string) []string {
// Create an array of StringInfo struct
strInfos := make([]StringInfo, len(strArr))
// Populate the array with string, length, and length modulo 3
for i, str := range strArr {
strInfos[i] = StringInfo{
Str: str,
Length: len(str),
Remain: len(str) % 3,
}
}
// Sort the array using custom comparator
sort.Slice(strInfos, func(i, j int) bool {
// Sort by remainder
if strInfos[i].Remain != strInfos[j].Remain {
return strInfos[i].Remain < strInfos[j].Remain
}
// Sort alphabetically if remainders are the same
return strInfos[i].Str < strInfos[j].Str
})
// Extract the sorted strings from the struct array
sortedStrArr := make([]string, len(strArr))
for i, strInfo := range strInfos {
sortedStrArr[i] = strInfo.Str
}
return sortedStrArr
}
func main() {
reader := bufio.NewReaderSize(os.Stdin, 16*1024*1024)
stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
checkError(err)
defer stdout.Close()
writer := bufio.NewWriterSize(stdout, 16*1024*1024)
strArrCount, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
checkError(err)
var strArr []string
for i := 0; i < int(strArrCount); i++ {
strArrItem := readLine(reader)
strArr = append(strArr, strArrItem)
}
result := RemainderSorting(strArr)
for i, resultItem := range result {
fmt.Fprintf(writer, "%s", resultItem)
if i != len(result)-1 {
fmt.Fprintf(writer, "\n")
}
}
fmt.Fprintf(writer, "\n")
writer.Flush()
}
func readLine(reader *bufio.Reader) string {
str, _, err := reader.ReadLine()
if err == io.EOF {
return ""
}
return strings.TrimRight(string(str), "\r\n")
}
func checkError(err error) {
if err != nil {
panic(err)
}
}