Kotlin for Interviews - Часть 5: Часто используемые фрагменты кода

Это часть 5 Kotlin for Interviews, серии, в которой я рассматриваю функции Kotlin и фрагменты кода, которые часто возникали во время подготовки к собеседованию с Android. Я также составил шпаргалку по всем 5 частям этой серии, которую вы можете найти здесь.

Вы можете найти Часть 1: Общие типы данных здесь, Часть 2: Функции сбора здесь, Часть 3: Числа и математику здесь и Часть 4: Итерацию здесь.

Эта часть охватывает:

• Создание графов в виде списка смежности
• Поиск в ширину
• Поиск в глубину
• Обход дерева
• Динамическое программирование / мемоизация

Мы рассмотрим блоки кода, которые я часто использую для решения множества различных задач. Например, многие задачи собеседования сводятся к поиску в глубину, и для их решения я использовал варианты базового фрагмента кода поиска в глубину.

Создание графиков в форме списка смежности

Для многих задач с графами вам будет предоставлен список пар узлов, где второй узел зависит от первого узла (или наоборот, в зависимости от вашего интервьюера). Например, пара, которая выглядит как [0, 1], означает, что для посещения узла 1 вы должны сначала посетить 0. Однако для большинства алгоритмов графа требуется представление списка смежности, поэтому вот алгоритм, который принимает список пар узлов и преобразует его в список смежности.

Учитывая этот пример ввода:

[[1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [3, 6], [4, 3], [4,6], [4, 7], [5, 4], [5, 7], [7, 6]]

Что представляет собой этот график:

Мы хотим создать следующий список смежности:

[[1: [2, 4, 3]], [2: [4, 5]], [3: [6]], [4: [6, 7, 3]], [5: [4, 7]], [7: [6]]]

fun createAdjacencyList(pairs: Array<IntArray>) {
    val graph: HashMap<Int, MutableList<Int>> = hashMapOf()
    pairs.forEach { pair ->
        if (!graph.containsKey(pair[0])) {
            // If the current node isn't in the adjacency list yet, 
            // add it and create its dependency list starting with 
            // pair[1]
            graph[pair[0]] = mutableListOf(pair[1])
        } else {
            // Otherwise, append pair[1] to its existing dependency  
            // list.
            val dependencies = graph[pair[0]]                 
            dependencies.add(pair[1])
            graph[pair[0]] = dependencies
        }
    }
}

Обратите внимание, что этот алгоритм предназначен для ориентированных графов. Если вам сказали, что граф неориентирован - это означает, что пара [0, 1] просто означает, что 0 и 1 имеют ребро между ними - просто повторите код в цикле forEach() с заменой pair[0] и pair[1], чтобы MutableLists в графе представляют все смежные узлы, а не только направленные зависимости.

Поиск в ширину

Многие задачи собеседования требуют обхода графов - от поиска узла до проверки циклов и определения длины пути между двумя узлами. Один из способов сделать это - поиск в ширину. Алгоритм начинается с некоторого узла графа и с помощью очереди исследует все соседние узлы на текущей глубине, прежде чем перейти к узлам на следующем уровне глубины.

Вот базовая версия, которая проходит через все узлы, доступные с первого. Вы можете изменить его в зависимости от решаемой задачи с графиком.

fun bfs(nodes: List<List<Int>>) {
    val visited = BooleanArray(nodes.size) { false }
    // Create a queue and add 0 to represent the index of the 
    // first node
    val queue: MutableList<Int> = mutableListOf(0)
    while (queue.isNotEmpty()) {
        // Dequeue a node from queue
        val node = queue.removeAt(0)
        // Add all of the node's unvisited neighbors to the queue
        if (!visited[node]) {
            nodes[node].forEach {
                queue.add(it)
            }
            // Mark the dequeued node as visited
            visited[node] = true
        }
    }
}

Поиск в глубину

Поиск в глубину также может использоваться для задач обхода графа. Алгоритм использует стек вместо очереди и исследует текущую ветвь узла, насколько это возможно, прежде чем будет вынужден вернуться и развернуться на другие узлы.

Вот рекурсивная версия, которая полагается на стек вызовов функции, а не на явную переменную стека. Вы также можете написать итеративную версию алгоритма, используя переменную стека.

fun dfs(nodes: List<List<Int>>) {
    val visited = BooleanArray(nodes.size) { false }
    helper(nodes, 0, visited)
}
 
fun helper(nodes: List<List<Int>>, node: Int, visited: BooleanArray){
    visited[node] = true
    nodes[node].forEach { 
        if (!visited[it]) {
            helper(nodes, it, visited)
        }
    }
}

Обход дерева

Проблемы с деревьями очень часто встречаются при собеседовании. Некоторые примеры включают поиск наименьшего общего предка двух узлов, суммирование значений всех узлов в дереве и т. Д.

Двоичное дерево

Двоичные деревья - это наиболее распространенное дерево, с которым вы столкнетесь на собеседовании. Узел двоичного дерева будет выглядеть примерно так:

class Node(
    var key: Int, 
    var left: Node? = null, 
    var right: Node? = null
)

Обратите внимание, что не все бинарные деревья являются бинарными деревьями поиска, и вы не должны предполагать, что вам дали BST, если ваш интервьюер не подтвердит это. Бинарное дерево является BST только в том случае, если оно также удовлетворяет следующим критериям:

• Левое поддерево узла содержит только узлы с ключами меньше ключа узла.
• Правое поддерево узла содержит только узлы с ключами больше ключа узла.
• Левое и правое поддерево также должны быть двоичным деревом поиска.

Давайте возьмем это дерево (которое не является BST!) В качестве примера:

Вы можете построить его, используя следующий код:

val node4 = Node(4)
val node7 = Node(7)
val node6 = Node(6, node4, node7)
val node11 = Node(11)
val node9 = Node(9, node6, node11)
val node2 = Node(2)
val node5 = Node(5)
val node12 = Node(12, node2, node5)
val node3 = Node(3, node12)
val node1 = Node(1, node9, node3)

Вот как будет выглядеть обход предварительного заказа:

fun preOrder(n: Node?) {
    n?.let { node ->
        print(node.key)
        preOrder(node.left)
        preOrder(node.right)
    }
}
preOrder(node1) // prints 1 9 6 4 7 11 3 12 2 5

Вот как будет выглядеть обход по порядку:

fun inOrder(n: Node?) {
    n?.let { node ->
        inOrder(node.left)
        print(node.key)
        inOrder(node.right)
    }
}
inOrder(node1) // prints 4 6 7 9 11 1 2 12 5 3

Вот как будет выглядеть обход пост-заказа:

fun postOrder(n: Node?) {
    n?.let { node ->
        postOrder(node.left)
        postOrder(node.right)
        print(node.key)
    }
}
postOrder(node1) // prints 4 7 6 11 9 2 5 12 3 1

Дерево с несколькими дочерними элементами

Вы также можете встретить деревья, у которых есть массив дочерних элементов, а не левый и правый узлы. Примером этой структуры данных может быть иерархия представлений Android, где каждое представление может иметь несколько дочерних элементов.

class Node(var value: Int) {
  val children: List<Node>
}

В этом случае вам придется рекурсивно вызывать свою функцию для всех дочерних элементов, и код будет выглядеть примерно так:

fun traverse(node: Node) {
    print(node.key)
    node.children.forEach {
        traverse(it)
    }
}

Динамическое программирование / мемоизация

Всякий раз, когда вы получаете рекурсивный алгоритм, который имеет повторяющиеся вызовы с одними и теми же входными данными, вы, вероятно, можете оптимизировать его с помощью динамического программирования. Идея состоит в том, чтобы сохранить результаты подзадач в таблице, чтобы нам не приходилось повторно вычислять их, когда это понадобится позже. Это снижает временную сложность от экспоненциальной до полиномиальной. Его можно реализовать с помощью итерации или рекурсии.

Итерация

Мы начинаем с самого маленького i и заполняем оттуда таблицу результатов. Каждая подзадача, которая нам нужна для текущей итерации, уже должна быть решена. На последней итерации мы решаем i=n и возвращаем этот результат.

fun fibonacci(n: Int): Int {
    // Initialize an array to keep track of results of subproblems
    // We'll use 0 as the placeholder initial value
    val results = Array(n + 1) { 0 }
    // Set the base cases
    results[1] = 1
    results[2] = 1
    for (i in 3..n) {
        results[i] = results[i-1] + results[i-2]
    }
    return results[n]
}

Рекурсия

Начнем с i = n. Если результаты подзадач, которые нам нужны для текущей итерации, уже существуют в таблице результатов, мы можем их использовать. В противном случае мы вызовем функцию рекурсивно, чтобы решить их и сохранить результаты.

fun fibonacci(n: Int): Int {
    // Initialize an array to keep track of results of subproblems
    // We'll use 0 as the placeholder initial value
    val results = Array(n + 1) { 0 } 
    // Set the base cases
    results[1] = 1
    results[2] = 1
    return helper(n, results)
}
// Write a helper function that takes in the results array as an 
// argument
fun helper(n: Int, results: Array<Int>): Int {
    // Check for the result of the subproblem you need in the 
    // results table first
    val nMinusOne: Int = if (results[n-1] != 0) {
        results[n-1]
    } else {
        // Only make the recursive call to the subproblem if it's 
        // not in the results table yet
        helper(n-1, results)
    }
    val nMinusTwo: Int = if (results[n-2] != 0) {
        results[n-2]
    } else {
        helper(n-2, results)
    }
    // Fill in the results table with the current results
    results[n] = nMinusOne + nMinusTwo
    return nMinusOne + nMinusTwo
}

И это конец серии "Котлин для интервью". Вот ссылка на шпаргалку, снова охватывающую все 5 частей. Удачи на собеседовании!

Щелкните 👏, чтобы сказать «спасибо!» и помогите другим найти эту статью.

Чтобы быть в курсе отличных новостей о Kt. Academy, подписывайтесь на рассылку новостей, следите за Twitter и следите за нами на Medium.

Если вам нужна мастерская Kotlin, узнайте, чем мы можем вам помочь: kt.academy.