3 задачи с собеседований на iOS-инженера в компании Кремниевой Долины | OTUS
🔥 Начинаем BLACK FRIDAY!
Максимальная скидка -25% на всё. Успейте начать обучение по самой выгодной цене.
Выбрать курс

Курсы

Программирование
iOS Developer. Basic
-25%
Python Developer. Professional
-25%
Разработчик на Spring Framework
-25%
Golang Developer. Professional
-25%
Python Developer. Basic
-25%
iOS Developer. Professional
-25%
Highload Architect
-25%
JavaScript Developer. Basic
-25%
Kotlin Backend Developer
-25%
JavaScript Developer. Professional
-25%
Android Developer. Basic
-25%
Unity Game Developer. Basic
-25%
Разработчик C#
-25%
Программист С Web-разработчик на Python Алгоритмы и структуры данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Vue.js разработчик VOIP инженер Программист 1С Flutter Mobile Developer Супер - интенсив по Kubernetes Symfony Framework Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-25%
DevOps практики и инструменты
-25%
Архитектор сетей
-25%
Инфраструктурная платформа на основе Kubernetes
-25%
Супер-интенсив «IaC Ansible»
-16%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-25%
Administrator Linux. Professional MS SQL Server Developer Безопасность Linux PostgreSQL Reverse-Engineering. Professional CI/CD VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Administrator Linux.Basic Супер-интенсив «ELK»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

iOS_Deep_21.4-5020-5412f9.png

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

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

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
2 комментария
0

Google давно отказался от головоломок на собеседованиях. "... we found that brainteasers are a complete waste of time "...

0

Задача №2 была у коллеги айосника в лондонский ФБ в середине 2019 года

Для комментирования необходимо авторизоваться
🎁 Максимальная скидка!
Черная пятница уже в OTUS! Скидка -25% на всё!