Wayne Bishop
Dec 20, 2018 · 3 min read

Recently I had the chance to help a student in the iOS Interview Program prepare for a significant technical interview at a company most individuals would recognize. Overall, my courses blend a mix of code challenges and live whiteboarding sessions that test one’s ability to implement syntax, design patterns and algorithms in Swift.

The Challenge

Occasionally I hear back from folks about their interview experiences. Sometimes, a certain type of question takes developers by surprise. If you recognize the challenge — fabulous! For the rest of us, here’s the summary:

// 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

The Analysis

What’s interesting about the challenge is the number of things it measures. This includes one’s general technical background, understanding of Swift, as well as computer science principles. As a new or experienced iOS developer, we are accustomed to working with native Swift types like Array’s & Dictionaries. As such, it’s easy to iterate through these list of elements. We can use fast enumeration to traverse an Array in linear time — 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
}

For our challenge, the difficulty is that a tree-based structure isn’t one-dimensional. As a result, the technique of fast enumeration can’t be applied. To solve the question we need to come up with an alternate method to account for the values below the root node (e.g., 1). This idea can be thought of as the tree’s depth. Consider this more detailed view:

The Implementation

To satisfy our criteria, we can apply the technique of Breadth-First Search (BFS). Unlike typical interview questions that involve counting, sorting or string manipulation, BFS has a specific purpose which would be quite difficult to replicate otherwise. When it comes to traversals, the advantage is that BFS is based on discovery. This procedure creates flexibility when traversing complex, open-ended systems like Graphs and Trees. Consider the following:

//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..")

}

Shown above, the code is implemented through the use of a Queue. Scheduling items with a Queue is ideal because it ensures objects get traversed in a First-In/First-Out manner. It’s this process that allows us to print the elements in our challenge in sequential order. Also, since the model is based on discovery, the algorithm continues to search for new items until the Queue is empty. In this example, the BFS algorithm makes use of a custom Queue. However, similar queueing functionality could be achieved through the use of an Array.


Liked this essay? Read and discover my Swift Algorithms Book on Medium.

Swift Algorithms Extras

Code challenges, ideas and essays based on the Swift Algorithms Book.

Wayne Bishop

Written by

I write about Swift Development & Computer Science. Get more tips on technical interview preparation at — www.waynewbishop.com

Swift Algorithms Extras

Code challenges, ideas and essays based on the Swift Algorithms Book.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade