Библиотека Go для собеса | вопросы с собеседований

💬 На вход подаются два неупорядоченных среза любой длины. Напишите функцию на Go, которая возвращает их пересечение.



Несколько способов, которыми можно решить эту задачу:



1. Использование мапы: наиболее эффективный способ, особенно для больших срезов. Алгоритм:



☑️ Итерируем по первому срезу и добавляем каждый элемент в мапу.

☑️ Итерируем по второму срезу, проверяя наличие элемента в мапе.

☑️ Если элемент найден, добавляем его в результат.



2. Поэлементное сравнение: менее эффективный метод, особенно для больших срезов, поскольку его сложность — O(n*m), где n и m — размеры срезов.



☑️ Двойной цикл для сравнения каждого элемента одного среза с каждым элементом другого среза.

☑️ Если найдено совпадение, добавляем элемент в результат.



3. Сортировка: метод эффективен, если срезы большие и их можно изменять.



☑️ Сначала сортируем оба среза.

☑️ Затем используем два указателя, чтобы итерировать оба среза и находить совпадающие элементы.



📌 Простой пример:

package main



import (

    "fmt"

)



func Intersection(slice1, slice2 []int) []int {

    // Создание мапы для хранения элементов первого среза

    elements := make(map[int]bool)

    for _, item := range slice1 {

        elements[item] = true

    }



    // Поиск пересечений

    var intersection []int

    for _, item := range slice2 {

        if _, found := elements[item]; found {

            intersection = append(intersection, item)

            // Чтобы избежать повторений в результате

            delete(elements, item)

        }

    }



    return intersection

}



func main() {

    slice1 := []int{1, 3, 5, 7, 9}

    slice2 := []int{3, 4, 5, 6, 7}

    fmt.Println(Intersection(slice1, slice2)) // [3 5 7]

}