Топ 20 задач с собеседований по Go

Задача Реализовать алгоритм бинарного поиска. Также известен как метод деления пополам или дихотомия - классический алгоритм поиска элемента в отсортированном массиве (слайсе), использующий дробление массива (слайса) на половины. На входе может быть слайс вида []int{1, 3, 4, 6, 8, 10, 55, 56, 59, 70, 79, 81, 91, 10001} и нужно вернуть индекс числа 55 (результат будет 6 true). Решение Принцип алгоритма бинарного поиска очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым. Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится. Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую. Если же элемент совпадает с искомым, мы выходим из цикла. package main func BinarySearch(in []int, searchFor int) (int, bool) { if len(in) == 0 { return 0, false } var first, last = 0, len(in) - 1 for first <= last { var mid = ((last - first) / 2) + first if in[mid] == searchFor { return mid, true } else if in[mid] > searchFor { // нужно искать в "левой" части слайса last = mid - 1 } else if in[mid] < searchFor { // нужно искать в "правой" части слайса first = mid + 1 } } return 0, false } К слову, вместо цикла мы могли бы использовать рекурсию.

Задача Реализовать структуру данных "стек" с функциональностью pop, append и top. Решение Очень простая реализация с использованием слайсов. type Stack struct { items []int } Сначала мы определим тип Stack с полем items. Этот стек отвечает за хранение целых чисел, но здесь может быть любой другой необходимый тип данных. Два наиболее важных метода стека – push и pop. Помещение элемента в стек добавляет его в самую верхнюю позицию, а удаление из стека извлекает самый верхний элемент. func (s *Stack) Push(data int) { s.items = append(s.items, data) } func (s *Stack) Pop() { if s.IsEmpty() { return } s.items = s.items[:len(s.items)-1] } Эти методы работают с указателями на тип Stack. Push добавляет элемент в s.items. Pop удаляет самый верхний элемент. Определим еще три полезных метода. func (s *Stack) Top() (int, error) { if s.IsEmpty() { return 0, fmt.Errorf("stack is empty") } return s.items[len(s.items)-1], nil } func (s *Stack) IsEmpty() bool { if len(s.items) == 0 { return true } return false } func (s *Stack) Print() { for _, item := range s.items { fmt.Print(item, " ") } fmt.Println() } Top возвращает самый верхний элемент в стеке. Если стек пуст, он возвращает нулевое значение и ошибку, говорящую о том, что стек пуст. IsEmpty возвращает true, если стек пуст, и false в противном случае. Print итерируется по стеку и выводит элементы.

Задача Реализуйте функцию reverse, получающую срез целых чисел и разворачивающую его без использования временного среза. Решение package main import "fmt" func reverse(sw []int) { for a, b := 0, len(sw)-1; a < b; a, b = a+1, b-1 { sw[a], sw[b] = sw[b], sw[a] } } func main() { x := []int{3, 2, 1} reverse(x) fmt.Println(x) } Цикл меняет местами значения каждого элемента среза. Значения будут следовать слева направо, и в итоге все элементы будут развернуты.

Задача Реализовать функцию perm(), принимающую срез или строку и выводящую все возможные комбинации его (ее) символов. Решение package main import "fmt" // Perm вызывает f с каждой пермутацией a. func Perm(a []rune, f func([]rune)) { perm(a, f, 0) } // Пермутируем значения в индексе i на len(a)-1. func perm(a []rune, f func([]rune), i int) { if i > len(a) { f(a) return } perm(a, f, i+1) for j := i + 1; j < len(a); j++ { a[i], a[j] = a[j], a[i] perm(a, f, i+1) a[i], a[j] = a[j], a[i] } } func main() { Perm([]rune("abc"), func(a []rune) { fmt.Println(string(a)) }) } Мы используем типы rune для обработки и срезов, и строк. Runes являются кодовыми точками из Unicode, а значит могут парсить строки и срезы одинаково.

Палиндром — слово, предложение или последовательность символов, которая абсолютно одинаково читается как в привычном направлении, так и в обратном. К примеру, “Anna” — это палиндром, а “table” и “John” — нет. Задача Дана строка; нужно написать функцию, которая позволяет вернуть значение true, если строка является палиндромом, и false — если нет. Метод №1: Сравнение символов Один из самых простых способов проверки, является ли строка палиндромом, заключается в сравнении символов с начала и конца строки. Если все символы соответствуют, то строка является палиндромом. func IsPalindrome(str string) bool { for i := 0; i < len(str)/2; i++ { if str[i] != str[len(str)-i-1] { return false } } return true } Метод №2: Использование функций strings В Golang есть функция strings.Reverse, которая переворачивает строку в обратном порядке. Мы можем сравнить оригинальную строку с перевернутой строкой, чтобы узнать, является ли она палиндромом. import "strings" func IsPalindrome(str string) bool { reversedStr := strings.Builder{} for i := len(str) - 1; i >= 0; i-- { reversedStr.WriteByte(str[i]) } return str == reversedStr.String() } Метод №3: Использование пакета bytes В Golang есть пакет bytes, который предоставляет функцию bytes.Equal, которую мы можем использовать для сравнения двух срезов байтов. import "bytes" func IsPalindrome(str string) bool { reversedBytes := make([]byte, len(str)) for i := 0; i < len(str); i++ { reversedBytes[i] = str[len(str)-i-1] } return bytes.Equal([]byte(str), reversedBytes) } Метод №4: Рекурсия Еще один способ проверки, является ли строка палиндромом, - использование рекурсии. Если первый и последний символы строки равны, мы рекурсивно вызываем функцию IsPalindrome для подстроки без первого и последнего символов. func IsPalindrome(str string) bool { if len(str) <= 1 { return true } if str[0] != str[len(str)-1] { return false } return IsPalindrome(str[1 : len(str)-1]) } Метод №5: Использование пакета unicode Использование пакета unicode позволяет обрабатывать строки, содержащие символы Unicode. С помощью функции utf8.DecodeRuneInString можно получить первый символ строки. Затем, если строка является палиндромом, мы можем рекурсивно вызвать функцию IsPalindrome для подстроки без первого и последнего символов. import "unicode/utf8" func IsPalindrome(str string) bool { if len(str) <= 1 { return true } firstRune, _ := utf8.DecodeRuneInString(str) lastRune, _ := utf8.DecodeLastRuneInString(str) if firstRune != lastRune { return false } return IsPalindrome(str[utf8.RuneLen(firstRune):utf8.RuneCountInString(str)-utf8.RuneLen(lastRune)]) }

Так называют слово, которое содержит все буквы другого слова в том же количестве, но ином порядке. Задача Нужно написать функцию, которая проверяет, являются ли две строки анаграммами, //Пример 1 Input: source = "anagram", target = "nagaram" Output: true // Пример 2 Input: source = "below", target = "elbow" Output: true Решение через сортировку Вариант заключается в том, чтобы отсортировать обе данные строки и просто-напросто проверить, равны ли они после этого друг другу. Если да, то перед нами анаграмма. func CheckIfStringsAreAnagram(source string, target string) bool { if len(source) != len(target) { return false } sourceArray := []rune(source) sort.Slice(sourceArray, func(i, j int) bool { return sourceArray[i] < sourceArray[j] }) targetArray := []rune(target) sort.Slice(targetArray, func(i, j int) bool { return targetArray[i] < targetArray[j] }) for i := 0; i < len(sourceArray); i++ { if sourceArray[i] != targetArray[i] { return false } } return true } То же самое работает и с конвертацией в байты: func CheckIfStringsAreAnagram(s string, t string) bool { if len(s) != len(t) { return false } sourceArray := []byte(s) sort.Slice(sourceArray, func(i, j int) bool { return sourceArray[i] < sourceArray[j] }) targetArray := []byte(t) sort.Slice(targetArray, func(i, j int) bool { return targetArray[i] < targetArray[j] }) return bytes.Equal(sourceArray,targetArray) } Сложность алгоритма по времени составляет О(n), где n - длина строки. Сложность по памяти составляет О(1). Решение через хеш-таблицу func CheckIfStringsAreAnagram(s string, t string) bool { if len(s) != len(t) { return false } sourceMap := make(map[rune]int) targetMap := make(map[rune]int) for _, letter := range s { sourceMap[letter]++ } for _, letter := range t { targetMap[letter]++ } for letter, sourceCount := range sourceMap { if targetCount, ok := targetMap[letter]; !ok || sourceCount != targetCount { return false } } return true }

Задача Необходимо реализовать функцию, подсчитывающую количество гласных букв в строке. Решение func countVowels(s string) int { count := 0 for _, char := range s { switch char { case 'a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', 'U': count++ } } return count }

Классическая задача, которую можно встретить на собеседованиях самого разного уровня. Стоит напомнить, что последовательность Фибоначчи — это ряд чисел, где каждое последующее является суммой двух предыдущих. Так, первые десять чисел выглядят следующим образом: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Задача Нужно написать функцию, которая возвращает n-ную запись в определенной последовательности, причем n — число, которое передается в качестве аргумента функции. fibonacci(3) // --> 2 Решение Проще всего реализовать решение задачи через рекурсию: package main import "fmt" func fibonacci(n uint) uint { if n < 2 { return n } return fibonacci(n-1) + fibonacci(n-2) } func main() { fmt.Println(fibonacci(10)) } Это работает хорошо, но возникает проблема, когда параметр n имеет большое значение. Это происходит из-за того, что функция определяется рекурсивно: количество раз, когда функция должна вызывать саму себя, растет экспоненциально по мере увеличения n. Например, попробуйте выполнить fibonacci(100) и программа, вероятно, будет работать очень медленно или даже выйдет из строя, если только вы не запускаете ее на чрезвычайно высокопроизводительном компьютере. Для преодоления этой проблемы мы можем улучшить наш код так, чтобы функция брала уже вычисленные ранее значения из кэша. package main import "fmt" var ( fibonacciCache = make(map[uint]uint) ) func fibonacci(n uint) uint { if n < 2 { return n } if result, ok := fibonacciCache[n]; ok { return result } result := fibonacci(n-1) + fibonacci(n-2) fibonacciCache[n] = result return result } func main() { fmt.Println(fibonacci(1_000)) } Теперь функция способна "переварить" большие аргументы. А вот решение без рекурсии: package main import "fmt" func fibonacci(n uint) uint { if n < 2 { return n } var a, b uint b = 1 for n--; n > 0; n-- { a += b a, b = b, a } return b } func main() { fmt.Println(fibonacci(100)) } Мы улучшили производительность, но все еще есть предел тому, насколько высоко в последовательности Фибоначчи мы можем подняться. Проблема вызвана не тем, что нам не хватает вычислительной мощности или памяти. Это скорее потому, что числа Фибоначчи очень быстро становятся очень большими: даже если бы мы использовали uint64, мы бы вскоре переполнили тип данных. Тогда кажется очевидным, что нам нужно использовать другой тип возвращаемого значения в нашей функции Фибоначчи, который может содержать сколь угодно большие целые числа. package main import ( "fmt" "math/big" ) func fibonacci(n uint) *big.Int { if n < 2 { return big.NewInt(int64(n)) } a, b := big.NewInt(0), big.NewInt(1) for n--; n > 0; n-- { a.Add(a, b) a, b = b, a } return b } func main() { fmt.Println(fibonacci(5_000)) } Выше мы использовали пакет math/big из стандартной библиотеки Go, так что мы можем создавать чрезвычайно большие целые числа. Функция a.Add(a, b) выполняет сложение, используя свои два аргумента, а затем сохраняет результат в a. Теперь стало возможным получать огромные результаты, которые не смог бы вместить примитивный тип данных, например, где n равно 5000. Генерация последовательности Фибоначчи с использованием горутин и каналов До сих пор мы выводили только n-е число в последовательности Фибоначчи, но в следующем примере мы выведем каждое число в последовательности вплоть до n. Естественный способ сделать это в Golang - запустить подпрограмму, которая постоянно отправляет числа Фибоначчи в канал, и мы просто будем использовать их столько, сколько нам нужно. package main import ( "fmt" "math/big" ) func fibonacciGenerator(c chan<- *big.Int) { a, b := big.NewInt(0), big.NewInt(1) for { c <- a a, b = b, a a.Add(a, b) } } func main() { const n = 1000 c := make(chan *big.Int) go fibonacciGenerator(c) for i := 0; i < n; i++ { fmt.Println(<-c) } }