3 задачи с собеседований на iOS-инженера в компании Кремниевой Долины

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

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

Задача № 1

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

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

Решение:

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, т. к. натуральные), и мы можем по ходу перебора массива помечать изменением знака на «−» значения тех элементов, индекс которых равен встретившемуся при переборе числу.

Задача № 2

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

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

Решение:

    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.

Задача № 3

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

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

Решение:

    // 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) и получаем наиболее часто встречающееся число.

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