Interviewing with Facebook — Onsite Part 2
Getting into the technical with Swift Iterators
You are about 40 minutes into the first interview. As your interviewer wraps up the behavioral questions, they segue into a whiteboard coding challenge.
Your party is stunned. It’s…
Lol, during my interview, I thought a part of the wall was the whiteboard and I left some permanent marks on it. Oops.
In all likelihood, this question will take more time than you have.
You’ve got 20 minutes and a whiteboard, so you know you probably won’t get to write all of the code down by the time the interview is over. Just try your best to show your thought process and keep working the problem.
I had never directly used an iterator in my work. This, I believe, is more or less the downfall of my whiteboarding interview with Facebook (aside from the fact that I forgot to put on deodorant that day — true story).
Without further ado, the question I was asked
How would you make an iterator for a sequence where each element could be anything?
I’m pretty sure I remember that correctly. If any of you have interviewed with Facebook and had the same question, just let me know and I’ll change it.
Let’s break it down
- It involves an iterator. At the time, I was not yet aware that an iterator is an actual protocol defined in the Swift standard library. So I thought I was creating some new type.
- It involves a sequence for that iterator. Again, Sequence is a real protocol in Swift that is defined as part of the standard library.
What is an Iterator?
An iterator is a type that keeps track of the iteration process as the contents of a sequence are iterated over. It lets you know what the next element will be and where the sequence terminates.
Okay, that’s a mouthful so let’s slow down a little
Consider the sequence of integers: 1, 2, 3
You are used to representing this sequence as an array, but that doesn’t necessarily mean it has to be represented that way.
You could represent that sequence a few other ways. Some possible variations are listed shown below.
Each of those could be iterated over in a sequential fashion. They each contain enough information to determine how the iteration process might work. You just need to provide the rules to do so.
That’s more or less what an iterator does. It gives you a way to provide the rules for iterating over some representation of data in a sequential manner.
Iterating over arrays
You already know this one. You learned it in your first computer science class. You do something like this.
You might not be creating a proper Iterator here, but you are saying something about the rules for iterating through that array.
- The “keeping track” is accomplished with an index that starts at the first element in the array.
- The “Is there a next element or are we done here?” part is accomplished with the conditional at the top of the while loop. It’s done when the index would point to an element past the number of elements in the array.
Of course, in Swift, you would never need to do any of this because you can do the following and it’s much simpler.
But why, dear reader, do you get this delicious morsel of syntactical goodness?
I’ll tell you why.
Array conforms to Collection, which itself conforms to Sequence. That means the Array type has the ability to make an Iterator by definition. Having an iterator is what lets you iterate over a representation of data in this syntatically sugarful way.
As it turns out, you can give this behavior to any representation of data so long as you create a type that conforms to Swift’s IteratorProtocol.
What about the other two?
Since neither the UglyCountToThree nor the BetterCountToThree sequence representations (declared above) conform to Sequence or IteratorProtocol, the Swift compiler doesn’t yet have the rules for the process of iteration.
Conforming to IteratorProtocol is what gives the compiler those rules.
Let’s make UglyCountToThree conform to IteratorProtocol. There are two requirements.
- You must define an element type. In this case that type is Int because the sequence 1, 2, 3 is a sequence of Integers.
- You must define a next() method. Because Swift is awesome and has the concept of optionals baked in, the next() method tells you both whether there is a next element, and if so, what. It also advances the iteration process by one element.
Here’s a skeleton.
Looking good so far. Of course, since this is a terrible way to represent the sequence 1, 2, and 3, the next() method has a super ugly implementation.
I don’t recommend you do this in an actual app. I just wanted to show you how you could implement IteratorProtocol on a naive representation of a sequence.
Tada. Yeah. I know. 🤮
What magical abilities does that give us? Not many yet.
Well, I suppose you could do the following in a playground. It’s sort of a halfway point between having no syntactic for-loop sugar and getting the full on Tony the Tiger 🐯 Frosted For Loop Sugar Experience.
Okay that’s actually pretty cool. All of the iteration logic is abstracted away and can be called upon in a single line. When you get to the end of the sequence, and the next() method returns nil, you escape the while loop.
Of course it could be better. You just need to conform to Sequence. Thankfully, that’s really easy to do.
Yup, that’s really all there is to it. You just declare conformance to the Sequence Protocol.
Go ahead and paste that code into a playground and iterate through the UglyCountToThree sequence. You will notice you get that Tony the Tiger 🐯 diabeetus-inducing sugar you’ve been craving all along.
To recap, you just went through the following process.
- Create something containing data that could represent the sequence you want to model. In this case that’s our awkward struct.
- Conform to IteratorProtocol. This is what gives Swift the rules it needs to determine how to go from your representation of a sequence to something that can be iterated over.
- Conform to Sequence. For reasons I will soon discuss, conforming to sequence gives you the for-in syntactic sugar you’re used to with arrays. Under certain circumstances, you do not need to do anything else to conform.
Conforming to Sequence first
When I first did this, I was puzzled. Why is it so easy to conform to Sequence once you’ve already conformed to IteratorProtocol?
To find out, let’s transform the BetterCountToThree struct into a sequence that can be iterated over — just like we did with UglyCountToThree.
There’s just one catch. We are going to do it in reverse, conforming to Sequence first.
Do you remember BetterCountToThree? Here it is again.
First of all, why is this better? I would say it’s better because it’s just a touch more abstract. Instead of giving you a concrete set of values to iterate over, it gives you a start, an end, and part of a rule that you can use to generate the sequence.
An even better sequence might be one where the programmer can pass in a start and end, thus allowing for greater customization. But I’m not going to do that yet because I want to keep the example nice and simple for first time iterator aficionados.
Conforming to Sequence first
Okay, take the BetterCountToThree struct and make it conform to the Sequence protocol. Make sure you don’t try to conform to IteratorProtocol just yet. Remember, you are doing this in reverse.
You will get compiler errors asking you to add in the following.
- A typealias called Iterator for some other type that conforms to the IteratorProtocol. You don’t really have a sequence if you can’t iterate over its contents. Sequence needs to know what kind of Iterator to use.
- A method called makeIterator() that returns an Iterator, of that same type. You will need to either use some kind of out-of-box iterator type, or declare some external entity that conforms to IteratorProtocol and return it.
Here is what a conforming Sequence type looks like.
I made up SomeIterator. It’s a placeholder you need to fill in with a separate IteratorProtocol conforming type that you define.
With that nugget of knowledge, let’s go create a separate type that conforms to IteratorProtocol — just as before.
Paste this code into a file or a Swift playground.
Hey this is starting to look pretty familiar. You’ve already conformed to IteratorProtocol when working with the UglyCountToThree, so this should be much easier the second time around.
To implement the next() method, you need to do two things.
- Keep track of the current element. To do that, you will add a currentElement instance variable. It is of type Int.
- Create an initializer for the BetterCountToThreeIterator. Because the currentElement variable doesn’t have a default value, it needs to be passed in via an initializer.
- Change the increment to a ‘let’ constant of 1. There is no reason why you would ever use a different increment when counting 1, 2, 3.
Here is the updated BetterCountToThreeIterator.
That’s pretty straightforward. But why is currentElement setup this way?
- The starting point determines the current element.
- Since you want to include the first element in this sequence as it gets iterated over, the current element needs to start one increment behind the starting point.
With this in place, it is pretty easy to fill in the implementation details for the next() method.
Yaay! I didn’t throw up in my mouth. Lets walk through the logic.
- Because the next() method is supposed to advance the process of iteration, you are forced to add the increment to the currentElement value before returning it.
- That means the currentElement must always be smaller than the last value in the sequence (a.k.a. the end) . Once it is equal to the last value, the iteration process is finished.
Paste the BetterCountToThree iterator and the following code into a Swift Playground.
You should see the sequence 1, 2, and 3 get printed to the console. This is just like what you saw with the UglyCountToThree but with a more generic next() method implementation.
Completing the custom Sequence type
Now you just need to do some refactoring on your BetterCountToThree sequence type. To do that, you are going to replace SomeIterator with an instance of BetterCountToThreeIterator. You can also get rid of the increment variable since the Iterator manages it now.
Replace your previous BetterCountToThree with the following custom sequence type.
Excellent! Take that code, and put the following lines of code right after it. I ran mine from a playground.
Just as you saw with the UglyCountToThree, you can iterate over your sequence using Swift’s fancy for-in sugar.
Renaming your sequence iterator
Take another look at the BetterCountToThreeIterator. Does the name really match what it does? I don’t think so. After all, you can pass in any start or end value.
You could iterate from 1 to 1000. You could start at -4 and end at 42.
The iterator seems more generic than we’re giving it credit for.
What’s a better name? What does this iterator really do? I would say it is a closed range iterator.
The range of integers that it iterates over has a discrete start and end. It does not continue past the last number.
You need to rename BetterCountToThreeIterator, but if you call it ClosedRangeIterator, you will run into naming conflict. Guess what! A version of the iterator you just created already exists in the Foundation library.
As a matter of fact, whenever you iterate over a basic sequence of integers like the following, an instance of a ClosedRangedIterator is created.
See! You’ve been using iterators all along, and you might not have known it.
A sequence with better naming
Rename BetterCountToThreeIterator to PracticeClosedRangeIterator instead.
That also means you need to rename your iterator wherever it is used, so the BetterCountToThree sequence should now look like the following.
That makes more sense. The iterator’s name does a better job of describing what it does.
Creating a sequence that is its own iterator
Earlier, when you worked with the UglyCountToThree sequence, you only needed to declare conformance to the Sequence protocol once your type had already conformed to IteratorProtocol. Why is that?
Now that you have some more background, it’s easier to explain.
Since the Sequence protocol requires both an Iterator type and an instance method to make an iterator, makeIterator(), there must be some section of code in the Swift standard library that fulfills these requirements for you.
So I went digging. Here’s what I found.
The standard library gives you a default implementation for the makeIterator() requirement. So long as your Sequence also conforms to IteratorProtocol, the makeIterator() protocol requirement is fulfilled.
This explains why it is so easy to adopt the Sequence protocol once your type has already conformed to IteratorProtocol.
Wow, what a digression! Well, not really. This is the background that is required in order to even begin to approach the question that was asked.
Ha. Do you even remember the question? Here it is again.
How would you make an iterator for a sequence where each element could be anything?
You just spent all this time figuring out how to make a closed range iterator for a sequence of integers that starts at 1 and ends at 3. It’s instructive. You now know how iterators and sequences work in Swift 👊.
Also, a quick caveat. I know that my implementation for ClosedRangeIterator is not complete. There are some edge cases to consider.
For example, what happens when someone passes in a starting value that is greater than the ending value? Try it out! You’ll get a runtime error explaining how you can’t create a range where the upper bound is smaller than the lower bound.
Here’s one more thing to consider. The Foundation library uses a CountableClosedRange to represent both the starting and ending values in a ClosedRangeIterator.
What do you think it means for a closed range to be countable? What does it mean for a range to be closed instead of open?
You should know the answer to these questions. The deeper you go, the smarter you’ll look at your onsite interview.
In the next article of the series, you will finally attempt to solve the question that was asked.
I know that definitely took more than 20 minutes, but it’s cool.
Remember, the people interviewing you are smart. They want to see that you understand the why not just the what.