Собеседование на позицию программиста на языке Golang может быть довольно сложным, особенно если работодатель ищет кандидата, который обладает хорошими знаниями алгоритмов. В данной статье мы рассмотрим некоторые задачи по алгоритмам уровня medium, которые могут быть заданы на собеседовании, а также поделимся примерами кода решений этих задач.
1. Задача о нахождении наибольшей общей последовательности (LCS)
Даны две строки s1 и s2. Необходимо найти наибольшую общую последовательность символов в этих строках.
Пример:
s1 = "ABCDGH"
s2 = "AEDFHR"
Ответ: "ADH"
Решение:
Для решения этой задачи мы можем использовать динамическое программирование. Создадим двумерный массив dp, где dp[i][j] будет содержать длину наибольшей общей последовательности для подстрок s1[0:i] и s2[0:j]. Заполним этот массив следующим образом:
- dp[0][j] = 0 для всех j
- dp[i][0] = 0 для всех i
- Если s1[i-1] == s2[j-1], то dp[i][j] = dp[i-1][j-1] + 1
- Иначе, dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Наконец, наибольшая общая последовательность будет содержаться в dp[len(s1)][len(s2)].
Код:
func lcs(s1 string, s2 string) string {
dp := make([][]int, len(s1)+1)
for i := range dp {
dp[i] = make([]int, len(s2)+1)
}
for i := 0; i <= len(s1); i++ {
for j := 0; j <= len(s2); j++ {
if i == 0 || j == 0 {
dp[i][j] = 0
} else if s1[i-1] == s2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
result := ""
i, j := len(s1), len(s2)
for i > 0 && j > 0 {
if s1[i-1] == s2[j-1] {
result = string(s1[i-1]) + result
i--
j--
} else if dp[i-1][j] > dp[i][j-1] {
i--
} else {
j--
}
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2. Задача о нахождении k-го наименьшего элемента в неотсортированном массиве
Дан неотсортированный массив чисел и число k. Необходимо найти k-й наименьший элемент в этом массиве.
Пример:
arr = [3, 7, 2, 9, 4]
k = 3
Ответ: 4
Решение:
Для решения этой задачи мы можем использовать алгоритм QuickSelect, который является модификацией алгоритма QuickSort. Он позволяет найти k-й наименьший элемент в неотсортированном массиве за O(n) времени.
Алгоритм QuickSelect работает следующим образом:
- Выбираем случайный элемент из массива и называем его опорным.
- Разбиваем массив на две части: элементы, меньшие опорного, и элементы, большие опорного.
- Если количество элементов в первой части меньше k, то рекурсивно вызываем QuickSelect для второй части и ищем (k - количество элементов в первой части) -й наименьший элемент.
- Если количество элементов в первой части больше или равно k, то рекурсивно вызываем QuickSelect для первой части и ищем k-й наименьший элемент.
Код:
func quickSelect(arr []int, k int) int {
if len(arr) == 1 {
return arr[0]
}
pivot := arr[rand.Intn(len(arr))]
var left, right []int
for _, v := range arr {
if v < pivot {
left = append(left, v)
} else if v > pivot {
right = append(right, v)
}
}
if k <= len(left) {
return quickSelect(left, k)
} else if k > len(arr)-len(right) {
return quickSelect(right, k-(len(arr)-len(right)))
} else {
return pivot
}
}
3. Задача о нахождении наименьшего общего предка (LCA) в двоичном дереве
Дано двоичное дерево и два узла в нем. Необходимо найти наименьшего общего предка этих узлов.
Пример:
1
/ \
2 3
/ \ / \
4 5 6 7
Узлы 4 и 5 имеют наименьшего общего предка 2.
Решение:
Для решения этой задачи мы можем использовать рекурсивный алгоритм. Если текущий узел равен одному из заданных узлов, то мы возвращаем его. Иначе, мы вызываем рекурсивно функцию для левого и правого поддеревьев. Если обе функции вернули не nil, то текущий узел является наименьшим общим предком.
Код:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
} else if left != nil {
return left
} else {
return right
}
}
В заключение, на собеседовании по Golang могут быть заданы различные задачи по алгоритмам. В данной статье мы рассмотрели несколько примеров задач уровня medium и предложили свои решения с помощью языка Golang. Надеемся, что эта статья поможет вам подготовиться к собеседованию и успешно пройти его.