Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 Мои коллеги и приятели нередко проходят интервью в компании типа Facebook. Большинство разработчиков не ожидают, с чем столкнутся на техническом интервью: даже очень опытные разработчики "сыпались" на комбинаторике, структурах данных или битовых операциях.

2 В обычном продакшене программистам не приходится долго быть погруженными в тему алгоритмов и структур данных. Если на вопросы про iOS-платформу все отвечают хорошо, то такие проверки для mobile-инженеров становятся самой сложной частью. Я поделюсь тремя задачами с реальных собеседований в известные во всём мире IT-компании, на которые давалось 40-60 минут.

3 <h2>Задача № 1</h2>

4 Начнём с простой, но классической задачки, которая попадалась даже мне на собеседованиях в российские крупные IT-компании:

5 Условие: есть массив размера N. Он заполнен натуральными числами от 1 до N. Надо придумать алгоритм, который без использования дополнительных переменных найдет любое повторяющееся число в массиве, если оно там есть.

6 Решение:

7 var array = [1,8,9,5,9,6,4,7,5] // naturals numbers are > 0 let N = array.count print("Duplicates:") for i in 1..<N { if array[abs(array[i])-1] >= 0 { array[abs(array[i])-1] = -array[abs(array[i])-1] } else { print(abs(array[i])) } }Объяснение: у нас до N элементов (числа больше 0, т. к. натуральные), и мы можем по ходу перебора массива помечать изменением знака на "-" значения тех элементов, индекс которых равен встретившемуся при переборе числу.

8 <h2>Задача № 2</h2>

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

10 Условие: на входе подаётся Бинарное Дерево, надо определить, обычное ли это Бинарное Дерево или Бинарное Дерево Поиска?

11 Решение:

12 class Node { let value: Int var left: Node? var right: Node? init(_ value: Int) { self.value = value } } func checkIsBST(_ node: Node?, min: Int, max: Int) -> Bool { guard let n = node else { return true // Empty tree is BST } if min <= n.value && n.value < max { // Recursion check min/max constraints return checkIsBST(n.left, min: min, max: n.value) && checkIsBST(n.right, min: n.value, max: max) } return false // Violates the min/max constraints, so it's BT } func isBST(root: Node) -> Bool { return checkIsBST(root, min: Int.min, max: Int.max) } // Tests let treeBST = Node(5) treeBST.left = Node(2) treeBST.right = Node(10) treeBST.left?.left = Node(1) treeBST.left?.right = Node(3) treeBST.right?.left = Node(8) treeBST.right?.right = Node(12) print("isBST \(isBST(root: treeBST))") let treeBT = Node(5) treeBT.left = Node(6) treeBT.right = Node(10) treeBT.left?.left = Node(2) treeBT.left?.right = Node(8) treeBT.right?.left = Node(11) treeBT.right?.right = Node(12) print("isBST \(isBST(root: treeBT))")Объяснение: эффективность в нашем случае в отличие от обычной рекурсивной проверки (решение "в лоб") достигается тем, что мы создаём дополнительный метод checkIsBST и он рекурсивно проверяет каждый узел лишь единожды за счет наличия аргументов min и max.

13 <h2>Задача № 3</h2>

14 Третью задачку могу предложить решить псевдокодом на бумаге, но и в коде она не сильно объёмная. В решении я показываю сам принцип.

15 Условие: в массиве известной длины есть целое число, которое встречается больше 50% раз. Надо найти это число. Решить за один проход и минимальное использование памяти.

16 Решение:

17 // Utils for bit operations enum Bit { case zero, one func asInt() -> Int { self == .one ? 1 : 0} } // to bytes(UInt8) func bitsToBytes(bits: [Bit]) -> [UInt8] { let numBits = bits.count let numBytes = (numBits + 7)/8 var bytes = [UInt8](repeating: 0, count: numBytes) for (index, bit) in bits.enumerated() { if bit == .one { bytes[index / 8] += UInt8(1 << (7 - index % 8)) } } return bytes } // to bits extension BinaryInteger { var bits: Array<Bit> { var arr = [Bit](repeatElement(.zero, count: self.bitWidth)) var n = self for i in 1...self.bitWidth { if n & 1 == 1 { arr[self.bitWidth-i] = .one } n >>= 1 } return arr } } // Test data, generate numOfElements (most frequent integer is N) let N = 9873 // Most frequent number let numOfElements = 1001 // use odd numbers var ints = [Int]() for i in 1...numOfElements { i % 2 == 0 ? ints.append(Int.random(in: Int.min...Int.max)) : ints.append(N) } print("\(N) count \(ints.filter { $0 == N }.count)/\(numOfElements)") // Solution for most frequent(50%+) number var bit64Counter = [Int](repeatElement(0, count: 64)) // for 64-bit int for i in ints { let bits = i.bits bit64Counter = zip(bit64Counter, bits).map { $0.0 + $0.1.asInt() } } let bitsOfMostNum:[Bit] = bit64Counter.map { $0 > (Int(numOfElements/2)) ? .one : .zero } let bytesOfMostNum:[UInt8] = bitsToBytes(bits: bitsOfMostNum) let mostNum = UnsafeRawPointer(bytesOfMostNum).assumingMemoryBound(to: Int.self).pointee.bigEndian print("Most frequent number \(mostNum)")Объяснение: делаем счётчик на каждый бит (на 64 бита - 64 счетчика). Каждое число представляем в бинарном виде и считаем, сколько встречается единиц (1). После окончания работы цикла 64 счётчика превращаем в биты (если значение счётчика больше половины длины массива, то ставим 1, иначе - 0) и получаем наиболее часто встречающееся число.

18 На этом всё, успешных вам собеседований!