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

Соревнование

Иногда я слышу от людей об их опыте собеседований. Иногда вопросы определенного типа застают разработчиков врасплох. Если вы признаете вызов - потрясающе! Для остальных из нас вот краткое изложение:

// Given the following tree:
//     1
//   2   3
// 4  5    7
//       8   9


//implemented by this class:
class BSNode<T> {
    
    var key: T?
    var left: BSNode?
    var right: BSNode?
    var height: Int
    
    init() {
        self.height = -1
    }
}

// use the below function to get the following output:
// expected output:
// 1
// 2 3
// 4 5 7
// 8 9

// results: 1 2 3 4 5 7 8 9

Анализ

Что интересно в задаче, так это количество измеряемых параметров. Сюда входят общие технические знания, понимание Swift, а также принципы информатики. Как новый или опытный разработчик iOS, мы привыкли работать с собственными типами Swift, такими как Array’s & Dictionaries. Таким образом, легко перебирать этот список элементов. Мы можем использовать быстрое перечисление для обхода массива за линейное время - O (n):

let sequence : Array<Int> = [1, 2, 3, 4, 5, 6, 7]

//linear time - O(n)
func linearSearch(for value: Int, list: Array<Int>) -> Bool {
    
    //traverse through the range of values
    for number in list {
        if number == value {
            return true
        }
    }
    
    return false
}

Для нашей задачи трудность состоит в том, что древовидная структура не одномерная. В результате невозможно применить технику быстрого перебора. Чтобы решить этот вопрос, нам нужно придумать альтернативный метод для учета значений ниже корневого узла (например, 1). Эту идею можно рассматривать как глубину дерева. Рассмотрим этот более подробный вид:

Реализация

Чтобы удовлетворить нашим критериям, мы можем применить метод поиска в ширину (BFS). В отличие от типичных вопросов на собеседовании, которые включают подсчет, сортировку или манипуляции со строками, BFS имеет конкретную цель, которую в противном случае было бы довольно сложно воспроизвести. Когда дело доходит до обходов, преимущество состоит в том, что BFS основан на обнаружении. Эта процедура обеспечивает гибкость при просмотре сложных открытых систем, таких как графики и деревья. Учтите следующее:

//breadth-first search - tree traversal
    
    func BFSTraverse() -> () {
                
        //establish a queue
        let bsQueue = Queue<BSNode<T>()
        
        //queue a starting node
        bsQueue.enQueue(self)
        
        while !bsQueue.isEmpty() {
            
            //traverse the next queued node
            guard let bitem = bsQueue.deQueue() else {
                break
            }
            
            print("now traversing item: \(bitem.key!)")
            
            //add decendants to the queue
            if let left = bitem.left {
                bsQueue.enQueue(left)
            }
            
            if let right = bitem.right {
                bsQueue.enQueue(right)
            }

            
        } //end while
        
        print(bfs traversal complete..")
        
    }

Показанный выше код реализован с использованием очереди. Планирование элементов с помощью очереди идеально, потому что оно гарантирует, что объекты будут перемещаться в порядке очереди. Именно этот процесс позволяет нам последовательно печатать элементы нашей задачи. Кроме того, поскольку модель основана на обнаружении, алгоритм продолжает поиск новых элементов до тех пор, пока очередь не станет пустой. В этом примере алгоритм BFS использует настраиваемую очередь. Однако аналогичная функция организации очереди может быть достигнута за счет использования массива.

Понравилось это эссе? Прочтите и откройте для себя мою книгу по Swift Algorithms в разделе Средний.