Which operations are fast in NSSet vs NSArray?
Essence
The difference is the data structure, not "iteration speed".
NSArray— an ordered list. Index accessobjectAtIndex:— O(1); iteration — O(n); searchcontainsObject:/indexOfObject:— O(n), because every element receivesisEqual:. Insert/remove in the middle of anNSMutableArray— O(n) (shifting elements).NSSet— a hash table with no order and no duplicates.containsObject:,addObject:,removeObject:— O(1) on average given correcthashandisEqual:. Iteration — also O(n), but the order is not guaranteed. Set operations (intersectSet:,minusSet:,isSubsetOfSet:) — O(n).
Iterating an array is usually slightly faster in practice (contiguous storage, cache locality), but asymptotically it is the same, and the interviewer wants "search in an array is linear, in a set it is constant".
The rest of this answer, with code and interview follow-ups, is in the DevPrep app.
Read the full answer in DevPrep