Solution for Problem 1 of the Coinbase technical interview
Problem 1
Given an array of strings ("<clicks>,<subdomain>.<subdomain>.<tld>"), find the total number of clicks for each domain (e.g. <subdomain>, <subdomain>.<tld>, etc.).
Example:
[
"900,google.com",
"60,mail.yahoo.com",
"10,mobile.sports.yahoo.com",
"40,sports.yahoo.com",
"300,yahoo.com",
"10,stackoverflow.com",
"20,overflow.com",
"5,com.com",
"2,en.wikipedia.org",
"1,m.wikipedia.org",
"1,mobile.sports",
"1,google.co.uk"
]
Solution
Simple string manipulation and hash map problem. Split the string at the comma. For each substring in the string, update the subdomain in the hash map. The time complexity is O(n), where n is the total number of domains. The space complexity is O(m) where m is the number of unique domains.
package main
import (
"strconv"
"strings"
)
// getTotalClicksByDomain returns a map with the total number of clicks for
// each domain.
func getTotalClicksByDomain(arr []string) map[string]int {
m := make(map[string]int)
for _, elem := range arr {
// Parse the string into substrings.
// Ex: "900,google.com" -> ["900", "google.com"]
ss := strings.Split(elem, ",")
// Get the total number of clicks.
clicks, _ := strconv.Atoi(ss[0])
// Get all domain parts.
// Ex: "google.com" -> ["google", "com"]
parts := strings.Split(ss[1], ".")
// Add all domains with corresponding clicks to the hash map.
for i := len(parts) - 1; i >= 0; i-- {
subdomain := strings.Join(parts[i:], ".")
m[subdomain] += clicks
}
}
return m
}