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.
Fresh Fruit Tourism
As incomes have risen, it’s important for Americans to find new ways to spend ever-increasing amounts of money. I propose that we spend some of it traveling to pick and eat fresh fruit that doesn’t travel well.
Content Warning: Knowing how delicious fresh fruit can be is an infohazard for your wallet.
It’s worth it to use more memory
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.
HTTP “Timeout” header for requesting resources from the future
Background
I’ve been participating in MPEG’s DASH group, and currently a lot of work has been focused on reducing live streaming latency. The latency problem in DASH is that clients have to poll servers to check for new media segments. If they poll too slowly, it introduces latency, but if they poll too quickly, it increases server load. When MPD’s are dynamic, a client needs to poll the server until it finds a new MPD, then request newly available segments, then only after the segment has downloaded enough to start, it can continue playback.
My RSS Reader is Done
I posted a few months ago about vibe-coding an RSS reader. The mood on the internet seems to be that these apps are buggy and never get finished, so I figured it was worth posting an update. Another thousand commits later, Lion Reader supports every feature I care about, works reliably, has very good performance, and is open for public signups.
