Lessons from a Swift Interview

A while back, Apple reached out to me about a position on the SwiftUI Mac frameworks team. Having worked with SwiftUI since its release, I was really excited about this opportunity. But after years as an indie developer, this was my first real technical interview in a while.

Spoiler alert: I didn't get the job. But I did learn something about Swift algorithm design and how to approach technical interviews.

The Assignment

For the interview assignment, I was asked to implement a function called coalescingAdjacentDuplicates() as if it were being added to the Swift Standard Library, with emphasis on generality, performance, and safety.

The solution had to support being used like this:

let x = [1, 2, 2, 3, 3, 3, 1]
for element in x.coalescingAdjacentDuplicates() {
    print(element)
}
// Prints "1", "2", "3", "1"
 
for element in x.coalescingAdjacentDuplicates().reversed().prefix(2) {
    print(element)
}
// Prints "1", "3"

My Solution

Before starting, I gathered a few references from Swift Algorithms: AsyncRemoveDuplicatesSequence.swift, Chunked.swift, and Unique.swift. I decided to model my implementation after UniquedSequence. I created a thin wrapper struct that conforms to Sequence and uses an iterator to skip adjacent duplicates:

public struct CoalescedAdjacentDuplicatesSequence<Base: Sequence>: Sequence {
    public struct Iterator: IteratorProtocol {
        var base: Base.Iterator
        var last: Base.Element?
 
        public mutating func next() -> Base.Element? {
            guard let last = last else {
                self.last = base.next()
                return self.last
            }
            while let element = base.next() {
                if element != last {
                    self.last = element
                    return element
                }
            }
            return nil
        }
    }
    // ...
}

This worked correctly. The adapter is created in O(1), and elements are processed lazily as you iterate. I was pretty happy with my solution.

The Follow-Up Question

The interviewer then asked about the performance implications of this code:

let x = sequence(first: 1, next: { $0 < 10e100 ? $0 + 2 : nil })
for element in x.coalescingAdjacentDuplicates().reversed().prefix(2) {
    print(element)
}

My answer:

The code snippet will struggle to evaluate mainly due to the application of reverse() on the UnfoldFirstSequence stored in x. This will force the evaluation of the whole sequence, which was probably intended to be lazy. As far as I can tell, there is no way to efficiently get to the last elements of an UnfoldSequence since it has to evaluate itself forward until it reaches the end condition. Furthermore, there doesn't seem to be a way to apply reverse() in a lazy manner unless the operation is specifically on a collection with bidirectional indices.

Everything here is correct. What tripped me up is that the example uses sequence(first:next:), which returns an UnfoldFirstSequence. There's no way for a generic algorithm to make that particular example efficient. I also knew that uniqued() would have the same issue. So it felt like an inherent limitation, not something my design could have avoided. This left me a bit uncertain as to whether the interviewer was testing my ability to analyze performance, or probing for a flaw in my design.

Turns out it was the latter. I missed the key insight: my implementation could have been a BidirectionalCollection.

The Key Insight: Sequence vs Collection

I had modeled my solution after UniquedSequence, which only conforms to Sequence. But there's a reason for that design choice, and it didn't apply to my algorithm.

Why uniqued() is Sequence-only

The uniqued() algorithm tracks all previously seen elements in a Set:

internal var seen: Set<Subject> = []

This accumulated state makes Collection conformance impractical. To implement index(before:) for backward traversal, you'd need to know the "seen" set at every position, which would require traversing from the start.

Why coalescingAdjacentDuplicates can be a Collection

My algorithm only compares adjecent elements. No accumulated state required:

• At any index, just look at base[i] vs base[i+1]
• Going backwards: look at base[i] vs base[i-1]
• No history, no Set, just local comparisons

This is structurally identical to ChunkedByCollection from Swift Algorithms, which does conform to Collection and BidirectionalCollection.

The Performance Difference

With BidirectionalCollection conformance, reversed() returns a lazy ReversedCollection wrapper. The big win is no O(n) allocation, though traversal cost depends on the data (each step may scan through runs of duplicates).

What I Should Have Done

If the base type is a Collection, my wrapper should also be a Collection. If it's a BidirectionalCollection, mine should be too:

extension CoalescedAdjacentDuplicatesCollection: Collection
  where Base: Collection
{
    // Custom Index type, startIndex, endIndex, index(after:), subscript
}
 
extension CoalescedAdjacentDuplicatesCollection: BidirectionalCollection
  where Base: BidirectionalCollection
{
    func index(before i: Index) -> Index {
        // Walk backwards, skipping duplicates
    }
}

The iterator-based Sequence implementation still works for arbitrary sequences. But for collections, the additional conformances enable lazy composition with operations like reversed().

Lessons Learned

1. Understand why similar algorithms have different designs. uniqued() and coalescingAdjacentDuplicates() look similar but have fundamentally different state requirements. I had Chunked.swift in my folder of references, which showed exactly the pattern I needed, but I zoned in on Uniqued.swift instead, probably cause of the naming differences.

2. Trust first principles over references. I've designed plenty of APIs for my own projects, but nothing at the level of the Swift Standard Library. So I leaned heavily on existing solutions as a guide. I should have focused on what my problem actually required rather than assuming uniqued() was the right template.

3. Think hard about composition. Standard Library design isn't just about the algorithm itself, it's about how it composes with other operations like reversed(), prefix(), lazy, etc. This way of thinking was pretty new to me, coming from a background of building apps, not low-level APIs.

4. Interview questions often have layers. The follow-up questions weren't really about identifying performance issues, they were asking "how could your design have avoided this?". While I could sense that I was missing something obvious, the pressure of the interview got to me and I didn't do a good enough job at recognizing the implicit question in the moment.

5. Do more interviews. I was given ample opportunity to reason my way out of the flaw during the interview, but I locked up once I realized something was wrong. This was my first technical interview in many years, and my nerves got the better of me.

The Corrected Implementation

I've published the corrected implementation as an open-source package: CoalescingAdjacentDuplicates.

It includes both the original Sequence-only version and the corrected Collection-conforming version, along with tests demonstrating the lazy behavior of reversed().