I was thinking about an approval-style voting system that could end with a large number of ties, and ran into the problem of how to break ties in a provably-fair way that doesn’t depend on candidates trusting each other and won’t make voters’ eyes glaze over.
I think I found a solution which is provably-fair, but it might still cross over into eye-glazing territory. I don’t know if this is practical (or novel), but I’m writing it up in case anyone else finds it interesting.
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 to keep track of numbers (the most obvious solution) is the best solution in practice.
There’s a common programming interview question that asks you to find the single non-duplicated value in a list of duplicated integers. This can be done in O(n) time and O(1) space by XOR’ing the values, and doing so is almost always the wrong answer. A better solution when you can afford to do it is to use a hash table to count occurrences.
To make your data faster to lookup, you can either store it in an order that makes it easier to search, or add one or more indexes. For practical work, you can let your file system do this for you, or use a pre-built database (either relational or not). I’ll describe from the lowest-level to highest level so you can understand what I’m suggesting, but my real-world answer is that I would store most kinds of data in a relational database like PostgreSQL and put indexes on any column that I want to do lookups by.
In school this week, the idea of finding palindromes in Python came up, as a homework assignment in a class I took last semester. A friend asked me for some guidance in how to do this in Python, so I showed him my “simple” solution:
#!/usr/bin/env python3
from …