replica placement coding test

main.go

package main

import (
	"fmt"
	"strings"
)

// Build a list of replica sets from a list of hosts and the number of
// hosts per replica set provided as input.
//
// The input hostnames are in the form of abc-123 where abc is the rack
// and 123 is the position within the rack:
//
//    hostname
//  ┌───┴───┐
//  ▼       ▼
//  asa - 022
//  ▲ ▲   ▲ ▲
//  └┬┘   │ │
//   │    └─┴─┐
// rack   position
//
// There are a couple of rules about how replicasets should be built:
//   * Each replicaset can only have one host from a given rack
//     (only one `asa-###` host, for example)
//   * Each host can only be in one replicaset
//
// Example returned valid replica sets (from an optimal algorithm):
// rsets = [
//     ['add-223', 'asa-022', 'asz-101'],
//     ['asa-001', 'atb-381', 'asz-281'],
//     ...
// ]
// leftover = ['asa-024', 'asa-025', 'asa-026', 'asa-023', 'atc-311']
//
// Note that because we don't have evenly divisible numbers of machines from all our racks,
// there are going to be some left over, that's okay as long as we know what they are.

func determineReplicaSets(hosts []string, replicaFactor int) (replicaSets [][]string, leftover []string) {

	for hostIndex, host := range hosts {
		rack := strings.Split(host, "-")[0]

		if hostIndex == 0 {
			replicaSets = append(replicaSets, []string{host})
			continue
			// fmt.Println("first set")
		}

		noSetAvailableForRack := true
		for setIndex, set := range replicaSets {

			if len(set) == replicaFactor {
				// fmt.Println("factor reached")
				continue
			}

			setHasRack := false
			for _, setHost := range set {
				setRack := strings.Split(setHost, "-")[0]
				if setRack == rack {
					// fmt.Println(setRack, rack)
					setHasRack = true
				}
			}

			if setHasRack == false {
				replicaSets[setIndex] = append(replicaSets[setIndex], host)
				noSetAvailableForRack = false
			}
			break
		}

		if noSetAvailableForRack == true {
			fmt.Println("adding new set for " + host)
			replicaSets = append(replicaSets, []string{host})
		}
	}

	var finalReplicaSets [][]string
	for _, set := range replicaSets {
		if len(set) == replicaFactor {
			finalReplicaSets = append(finalReplicaSets, set)
		} else {
			leftover = append(leftover, set...)
		}
	}
	replicaSets = finalReplicaSets

	return replicaSets, leftover
}

func main() {
	hosts := []string{
		"asa-001", "asa-002", "asa-003", "asa-004", "asa-005", "asa-006",
		"asa-011", "asa-012", "asa-013", "asa-014", "asa-015", "asa-016",
		"asa-021", "asa-022", "asa-023", "asa-024", "asa-025", "asa-026",
		"asr-011", "asu-311", "asu-134", "asu-281", "asv-101", "asv-351",
		"asw-051", "asw-054", "asx-314", "asx-351", "asy-014", "asy-134",
		"asz-101", "asz-281", "asz-383", "ata-134", "ata-224", "ata-281",
		"ata-311", "atb-134", "atb-164", "atb-314", "atb-381", "atc-054",
		"atc-223", "atc-281", "atc-284", "atc-311", "add-223",
	}
	replicaFactor := 3

	fmt.Println(determineReplicaSets(hosts, replicaFactor))
}