1910 просмотров
От 25 февраля

Алгоритмические задачи для собеседований Go-разработчиков

1. Реализуйте стек (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 итерируется по стеку и выводит элементы.

2. Реализуйте 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) } Цикл меняет местами значения каждого элемента среза. Значения будут следовать слева направо, и в итоге все элементы будут развернуты.

3. Реализуйте бинарный поиск

Задача Реализовать алгоритм бинарного поиска. Также известен как метод деления пополам или дихотомия - классический алгоритм поиска элемента в отсортированном массиве (слайсе), использующий дробление массива (слайса) на половины. На входе может быть слайс вида []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 } К слову, вместо цикла мы могли бы использовать рекурсию.

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. Проверка двух слов на анаграмму

Поддержи проект и получи доступ ко всему контенту всего за 290

7. Подсчитайте гласные в строке

Поддержи проект и получи доступ ко всему контенту всего за 290

8. Выведите последовательность Фибоначчи

Поддержи проект и получи доступ ко всему контенту всего за 290

9. Задача "FizzBuzz"

Поддержи проект и получи доступ ко всему контенту всего за 290

10. Реализуйте сортировку слиянием

Поддержи проект и получи доступ ко всему контенту всего за 290

11. Найдите пересечение двух слайсов

Поддержи проект и получи доступ ко всему контенту всего за 290

12. Реализуйте генератор случайных чисел

Поддержи проект и получи доступ ко всему контенту всего за 290

13. Объедините N каналов в один

Поддержи проект и получи доступ ко всему контенту всего за 290

14. Реализуйте конвейер чисел на каналах

Поддержи проект и получи доступ ко всему контенту всего за 290

15. Реализуйте WorkerPool с заданной функцией

Поддержи проект и получи доступ ко всему контенту всего за 290

16. Реализуйте waitGroup на семафоре

Поддержи проект и получи доступ ко всему контенту всего за 290

17. Реализуйте обход ссылок из файла

Поддержи проект и получи доступ ко всему контенту всего за 290

18. Реализуйте свап значений переменных без промежуточной

Поддержи проект и получи доступ ко всему контенту всего за 290

19. Найдите сумму квадратов чисел между 1 и N

Поддержи проект и получи доступ ко всему контенту всего за 290

20. Реализуйте функции min и max

Поддержи проект и получи доступ ко всему контенту всего за 290

21. Очистите строку от не-чисел

Поддержи проект и получи доступ ко всему контенту всего за 290
Хочешь стать частью сообщества Девстанции?
Вступай в наш чат в Telegram

Также в этой категории

Шпаргалка
  54 вопроса

Шпаргалка по вопросам о Go

Вопросы про Go на собеседовании

513 просмотров
От 30 января

Вам может быть интересно

Шпаргалка
  7 вопросов

Коллекция полезных команд для Docker

Большая шпаргалка по всем командам Docker

200 просмотров
От 12 октября 2023
Викторина
  20 вопросов

Викторина по Django - Junior/Middle

Базовые вопросы с собеседования по Django

15 просмотров
От 2 июня 2023
Задачник
  43 задачи

Топ 45 алгоритмических задач по Python

Разбор решений для задач с собеседований Python-разработчиков

3283 просмотра
От 15 февраля
Шпаргалка
  10 вопросов

Всё о репликации баз данных

Описание понятий и процессов репликации БД

178 просмотров
От 8 октября 2023
Шпаргалка
  60 вопросов

60 вопросов про базы данных и SQL

Вопросы и ответы с собеседования по базам данных и SQL

312 просмотров
От 20 февраля
Шпаргалка
  34 вопроса

Шпаргалка по вопросам о Python

Вопросы для собеседования Python-разработчика

562 просмотра
От 30 января

Топ тредов

Gravatar for 9tokio
Tokio:
то что раньше было бесплатным теперь платное - вот это я понимаю

Последнее сообщение:
Логотип Девстанции
Девстанция:
Спасибо за поддержку проекта :) Повышение качества контента - один из важнейших приоритетов. Этому м...
3 сообщения
213 просмотров

Логотип Девстанции
Девстанция:
Поиск людей для совместной разработки IT-стартапов

Последнее сообщение:
В этом треде пока нет сообщений
0 сообщений
107 просмотров

Логотип Девстанции
Девстанция:
Какой язык программирования выбрать в качестве первого?

Последнее сообщение:
Gravatar for 2kokke
Kokke:
Python или JS - универсально. Но по уму надо бы с чего-то строгого начинать и достаточно низкоуровне...
1 сообщение
139 просмотров

Все категории