I do too. One pool of identical whites and one of blacks. Moves the matching problem from O(n) to O(1) and it's ok if you lose an odd one here or there.
Unlike Jobs, nobody notices.
Unlike Jobs, nobody notices.
And that with all identical pairs, I assert the solution is O(n), since there is a chance that you will have to iterate through all of your socks to find one with no holes/is clean. However, I think the latter case is Omega(1). Not quite so sure about the first one.
Now that I think of it, the mixed sock problem can actually be worse than O(n^2). For instance, if I decide that I want to wear my Marvin the Martian socks, and can only find one in the sock drawer, then it's a big problem. Look in the other drawers. Look under the bed. Look in the dryer. Repeat. Repeat. Until the other one is given up for lost.
Again, with ordering, searching drops to O(log n)
http://www.mail-archive.com/kragen-tol@canonical.org/msg0008...