The problem of computing luminance was rather of a bit-twiddling nature (and some of my readers came up with very creative solutions—far better than my own), and the problem of the Martian calendar was a bit more deductive (and still not solved, though some of the readers came close to a solution); and for the third programming challenge, I propose something a bit more algorithmic/basic data structure in tone.
The problem I propose in this challenge arises in a variety of settings, such in (simple) search engines, but performing it efficiently is not always trivial.
For our immediate needs, let us suppose we have two sorted lists, , and , of lengths and , respectively. Your task is to device an algorithm that computes the intersection of and in , therefore excluding search-based solution (which would be at least .
Bonus. Propose an algorithm in to compute the union (in a set-theoretic sense, that is, ).
Bonus. What if the lists aren’t sorted? What’s your lower bounds in complexity and (extra) memory?
(Of course, needless to say that you’re not to propose a solution using the features of the language that does the operation automagically, such as in Mathematica, Matlab, etc.)