I've been subscribed to Interview Cake for years, and today they had a really interesting question: Given a list of n + 1 integers in the range 1...n, find one of the duplicates (there is guaranteed to be at least one) in O(n) time and O(1) additional space. The answer is really interesting, and I recommend trying it, but I don't think it makes sense to care about additional space rather than total space, and I still think using a set is the best solution in practice.
