Недавно у меня была возможность помочь студенту, участвующему в Программе собеседований по iOS подготовиться к важному техническому собеседованию в компании, которую узнает большинство людей. В целом, мои курсы представляют собой сочетание задач по программированию и интерактивных сессий интерактивной доски, которые проверяют способность реализовывать синтаксис, шаблоны проектирования и алгоритмы в Swift.
Соревнование
Иногда я слышу от людей об их опыте собеседований. Иногда вопросы определенного типа застают разработчиков врасплох. Если вы признаете вызов - потрясающе! Для остальных из нас вот краткое изложение:
// Given the following tree: // 1 // 2 3 // 4 5 7 // 8 9 //implemented by this class: classBSNode
<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 valuesfor
numberin
list { if number == value {return
true } }return
false }
Для нашей задачи трудность состоит в том, что древовидная структура не одномерная. В результате невозможно применить технику быстрого перебора. Чтобы решить этот вопрос, нам нужно придумать альтернативный метод для учета значений ниже корневого узла (например, 1). Эту идею можно рассматривать как глубину дерева. Рассмотрим этот более подробный вид:
Реализация
Чтобы удовлетворить нашим критериям, мы можем применить метод поиска в ширину (BFS). В отличие от типичных вопросов на собеседовании, которые включают подсчет, сортировку или манипуляции со строками, BFS имеет конкретную цель, которую в противном случае было бы довольно сложно воспроизвести. Когда дело доходит до обходов, преимущество состоит в том, что BFS основан на обнаружении. Эта процедура обеспечивает гибкость при просмотре сложных открытых систем, таких как графики и деревья. Учтите следующее:
//breadth-first search - tree traversalfunc
BFSTraverse() -> () { //establish a queue let bsQueue = Queue<BSNode
<T>() //queue a starting node bsQueue.enQueue(self
)while
!bsQueue.isEmpty() { //traverse the next queued nodeguard
let bitem = bsQueue.deQueue()else
{ break }if
let left = bitem.left { bsQueue.enQueue
(left) }if
let right = bitem.right { bsQueue.enQueue
(right) } } //end while
Показанный выше код реализован с использованием очереди. Планирование элементов с помощью очереди идеально, потому что оно гарантирует, что объекты будут перемещаться в порядке очереди. Именно этот процесс позволяет нам последовательно печатать элементы нашей задачи. Кроме того, поскольку модель основана на обнаружении, алгоритм продолжает поиск новых элементов до тех пор, пока очередь не станет пустой. В этом примере алгоритм BFS использует настраиваемую очередь. Однако аналогичная функция организации очереди может быть достигнута за счет использования массива.
Понравилось это эссе? Прочтите и откройте для себя мою книгу по Swift Algorithms в разделе Средний.