Реализуй функцию для нахождения сервиса с наибольшим количеством логов в каждом namespace. Какова сложность алгоритмов для топ-1, топ-2, топ-10?

Для задачи нахождения сервиса с наибольшим количеством логов в каждом namespace можно использовать следующий подход:

1. Итерируемся по всем логам, группируем их по namespace и сервису, подсчитывая количество логов.
2. Для каждого namespace определяем сервис с максимальным количеством логов.

Пример реализации на Go:

type Log struct {
    Namespace string
    Service   string
}

func TopServicePerNamespace(logs []Log) map[string]string {
    counts := make(map[string]map[string]int)

    for _, log := range logs {
        if counts[log.Namespace] == nil {
            counts[log.Namespace] = make(map[string]int)
        }
        counts[log.Namespace][log.Service]++
    }

    result := make(map[string]string)
    for ns, svcCounts := range counts {
        maxCount := 0
        var topService string
        for svc, count := range svcCounts {
            if count > maxCount {
                maxCount = count
                topService = svc
            }
        }
        result[ns] = topService
    }

    return result
}

Сложность алгоритмов для топ-N

• Топ-1: как в примере выше — один проход по логам O(M), где M — количество логов, и затем проход по сервисам в каждом namespace. Если в среднем S сервисов на namespace и N namespace, итог — O(M + N*S).

• Топ-2, Топ-10: нужно для каждого namespace отсортировать сервисы по количеству логов или использовать структуру данных для поддержания топ-N.

  • Сортировка сервисов для каждого namespace: O(N * S log S)
  • Использование кучи (heap) для топ-N: O(N * S log N)

Если N и S малы, сортировка вполне приемлема. Если очень большие, лучше использовать кучу для оптимизации.