Irbisa · Шпаргалка
Live coding на Kotlin
Хеширование, два указателя, скользящее окно, стек, бинарный поиск, кучи, графы и задачи на корутины вроде ограничения параллелизма
Что такое нотация Big-O и сколько стоит
containsуList, уHashSetи у отсортированного списка сbinarySearch?fun main() { val ids = List(100_000) { it * 2 } // sorted: 0, 2, 4, ... val idSet = ids.toHashSet() // O(n) to build, once println(199_998 in ids) // O(n): compares element by element println(199_998 in idSet) // O(1) on average: hash, then one bucket…Дан
IntArrayи целевое число: верните индексы двух чисел, которые в сумме дают его. Как перейти от O(n²) к O(n)?// Brute force: every pair, O(n²) time, O(1) memoryfun twoSumSlow(nums: IntArray, target: Int): Pair<Int, Int>? { for (i in nums.indices) for (j in i + 1 until nums.size) { if (nums[i] + nums[j] == target) return i to j } return null…Проверьте, является ли строка палиндромом, без учёта регистра и всего, что не буква и не цифра, не создавая перевёрнутую копию.
fun isPalindrome(s: String): Boolean { var i = 0 var j = s.lastIndex while (i < j) { when { !s[i].isLetterOrDigit() -> i++ // skip spaces and punctuation…Проверьте, сбалансированы ли скобки
()[]{}в строке. Какую структуру данных вы возьмёте и сколько это стоит?private val opening = mapOf(')' to '(', ']' to '[', '}' to '{') fun isBalanced(s: String): Boolean { val stack = ArrayDeque<Char>() // kotlin.collections.ArrayDeque for (c in s) { when (c) {…Сожмите строку кодированием длин серий (RLE) за один проход, чтобы
AAABCCDпревратилась вA3BC2D.fun rle(s: String): String { if (s.isEmpty()) return s val out = StringBuilder() var count = 1 for (i in 1..s.length) { // one step past the end flushes the last run if (i < s.length && s[i] == s[i - 1]) {…Разверните односвязный список на месте. Напишите итеративную версию, затем скажите, во что обходится рекурсивная.
class Node(val value: Int, var next: Node? = null) // Iterative: O(n) time, O(1) extra memoryfun reverse(head: Node?): Node? { var prev: Node? = null var cur = head…Какова временная сложность этой функции и как довести её до O(n)?
data class Post(val id: Long, val tags: List<String>) // posts: 10,000 posts with 5 tags each; followed: 2,000 tagsfun followedTags(posts: List<Post>, followed: List<String>): List<String> { val result = mutableListOf<String>() for (post in posts) { for (tag in post.tags) { if (tag in followed && tag !in result) result.add(tag) } } return result}Сгруппируйте список слов по анаграммам. Что вы используете как ключ мапы и сколько стоит всё решение?
// Key = the sorted letters: O(n · k log k) for n words of length kfun groupAnagrams(words: List<String>): List<List<String>> = words.groupBy { word -> String(word.toCharArray().apply { sort() }) // "tea" and "eat" both give "aet" }.values.toList()…Найдите длину самой длинной подстроки без повторяющихся символов за O(n) и покажите, как движется скользящее окно.
fun longestUniqueRun(s: String): Int { val lastSeen = HashMap<Char, Int>() // character -> index where it was last seen var start = 0 // the window is s[start..end] var best = 0 for (end in s.indices) { val prev = lastSeen[s[end]]…Найдите непрерывный подмассив с максимальной суммой за O(n) и верните его границы, а не только сумму.
data class Best(val sum: Long, val from: Int, val to: Int) // to is inclusive fun maxSubarray(a: IntArray): Best { require(a.isNotEmpty()) { "an empty array has no subarray" } var best = Best(a[0].toLong(), 0, 0) var sum = 0L // Long: a million large Ints overflow an Int…Объедините пересекающиеся интервалы, например слоты бронирования
[1,3] [2,6] [8,10], и объясните, зачем сначала сортировать.fun merge(intervals: List<IntRange>): List<IntRange> { if (intervals.isEmpty()) return emptyList() val sorted = intervals.sortedBy { it.first } // O(n log n): overlaps become neighbours val result = mutableListOf(sorted[0]) for (i in 1 until sorted.size) { val next = sorted[i]…Найдите баг: этот бинарный поиск первого вхождения
targetна некоторых входных данных зависает навсегда.// Returns the index of the first `target` in a sorted array, or -1fun firstIndexOf(a: IntArray, target: Int): Int { var lo = 0 var hi = a.size - 1 while (lo < hi) { val mid = (lo + hi) / 2 if (a[mid] < target) lo = mid else hi = mid } return if (a.isNotEmpty() && a[lo] == target) lo else -1} // firstIndexOf(intArrayOf(1, 2, 2, 2, 5), 2) never returnsВерните
kсамых частых элементов массива. Когда использоватьPriorityQueue, а когда сортировку по корзинам (bucket sort)?// Heap: O(n + m log k) for m distinct valuesfun topKFrequent(nums: IntArray, k: Int): List<Int> { val counts = nums.asList().groupingBy { it }.eachCount() // value -> count, O(n) val heap = PriorityQueue<Map.Entry<Int, Int>>(compareBy { it.value }) // min-heap for (entry in counts.entries) { heap.add(entry)…Посчитайте острова в сетке из
0и1. BFS или DFS, и что ломается при глубокой рекурсии на большой сетке?private val steps = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1) fun countIslands(grid: Array<IntArray>): Int { val rows = grid.size val cols = grid.firstOrNull()?.size ?: return 0 val seen = Array(rows) { BooleanArray(cols) } // or flip 1 to 0 if the input may change…В каком порядке этот код печатает буквы от
AдоEи почемуAвыводится не первой?fun main() { runBlocking { launch { println("A") } println("B") coroutineScope { launch { delay(100) println("C") } println("D") } println("E") }}Скачайте 100 картинок так, чтобы одновременно выполнялось не больше 4 запросов. Напишите это на корутинах и верните результаты в порядке входного списка.
suspend fun <T> downloadAll( urls: List<String>, maxInFlight: Int = 4, load: suspend (String) -> T,): List<T> = coroutineScope { val permits = Semaphore(maxInFlight)…По списку Gradle-модулей и их зависимостей верните порядок сборки или сообщите о цикле, из-за которого собрать нельзя.
sealed interface BuildPlan { data class Order(val modules: List<String>) : BuildPlan data class Cycle(val path: List<String>) : BuildPlan} // deps: module -> the modules it depends on (they must be built first)…Запросите два зеркала параллельно, верните первый успешный ответ, отмените второй запрос и через 2 секунды откатитесь на кэш. Напишите это на корутинах.
// The first source that succeeds wins; null if every one of them failssuspend fun <T> firstSuccess(vararg sources: suspend () -> T): T? = channelFlow { for (source in sources) launch { try { send(source())…