Топ 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 }