Collections and data structures in OOP

Junior

Essence

Collections are abstractions for storing groups of values: array, set, dictionary. In OOP languages such as Java they form a hierarchy of classes (the Collection Framework). Swift collections are built differently, and that difference is what the interviewer expects to hear.

Collections in Swift

• Array, Set, Dictionary and String are value types (structs) that keep their data in a heap buffer and use copy-on-write: copying is O(1) until the first mutation; the buffer is duplicated only when several references to it exist (isKnownUniquelyReferenced).
• A protocol hierarchy instead of classes: Sequence → Collection → BidirectionalCollection → RandomAccessCollection; plus MutableCollection and RangeReplaceableCollection. Algorithms (map, filter, sorted, firstIndex) live in protocol extensions and are available to any conformer.
• Set/Dictionary require Hashable elements/keys; Equatable, Hashable and Codable are synthesized by the compiler.
• Laziness: array.lazy.map { } creates no intermediate arrays.

var a = [1, 2, 3]
var b = a            // no copy yet: both share one buffer (copy-on-write)
b.append(4)          // the buffer is copied here, `a` is untouched
print(a, b)          // [1, 2, 3] [1, 2, 3, 4]

// Any type can join the collection family by adopting the protocols.
struct Countdown: Sequence, IteratorProtocol {
    var count: Int
    mutating func next() -> Int? {
        guard count > 0 else { return nil }
        defer { count -= 1 }
        return count
    }
}
print(Array(Countdown(count: 3)))                   // [3, 2, 1]
print(Countdown(count: 5).filter { $0.isMultiple(of: 2) }) // [4, 2]

Operation complexity

• Array: index access O(1), append amortized O(1), insertion at the front O(n), contains O(n).
• Set/Dictionary: insert, lookup, delete O(1) on average (hash table).
• String is not random access: indices are String.Index, count is O(n) because of grapheme clusters.

What the interviewer looks for

• Why value semantics of collections helps concurrency: a copy shares no state, [Int] is Sendable.
• When ContiguousArray (no bridging to NSArray) and reserveCapacity are useful.
• That NSArray/NSMutableArray are reference types; semantics change when bridged from ObjC.