Алгоритмические задачи для собеседований Go-разработчиков
1. Бинарный поиск
Задача
Реализовать алгоритм бинарного поиска. Также известен как метод деления пополам или дихотомия - классический алгоритм поиска элемента в отсортированном массиве (слайсе), использующий дробление массива (слайса) на половины. На входе может быть слайс вида
[]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
}
К слову, вместо цикла мы могли бы использовать рекурсию.
2. Стек (LIFO)
Задача
Реализовать структуру данных "стек" с функциональностью 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
итерируется по стеку и выводит элементы.
3. Функция reverse()
Задача
Реализуйте функцию 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)
}
Цикл меняет местами значения каждого элемента среза. Значения будут следовать слева направо, и в итоге все элементы будут развернуты.
4. Все комбинации символов строки
Задача
Реализовать функцию 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, а значит могут парсить строки и срезы одинаково.
5. Палиндром
Палиндром — слово, предложение или последовательность символов, которая абсолютно одинаково читается как в привычном направлении, так и в обратном. К примеру, “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)])
}
6. Анаграмма
Так называют слово, которое содержит все буквы другого слова в том же количестве, но ином порядке.
Задача
Нужно написать функцию, которая проверяет, являются ли две строки анаграммами,
//Пример 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
}