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.)

I think this would work (since they are sorted lists)

Get two pointers, one to the start of each list. A -> List1, B -> List2

If (A = B) then
insert into intersection list
Move both A & B to next item in respective lists
if (A < B) then
move A to next item in List 1
if no more items left, done
if (B < A) then
move B to next item in List 2
if no more items left, done

This should take O(min(n,m)) since you will only traverse until you reach the end of one of the lists (whichever is shorter).

This could be modified to do the union by simply inserting the items in the second and third if statements…

Of course, this is after only one cup of coffee… :)

I found your blog recently; it’s a great read!
For this challenge I used Scheme (even though I tend to work in Python) since it seemed to line up well with my thought process. My solution is available here.

I was going to withhold the answers to leave time for people to find the solutions by themselves, but they’re already in! (Clayton was the first to give his answer)

Let L1 = [1,2, …, n] and L2 = [ n ]. Assuming this is linked-list to access last element of L1 we must perform O(n) operations, so there don’t exist O(min(n,m)) algorithm.

Even with double-linked list with pointers to head, and tail it still impossible (ex. by placing only element of L2 in center of L1).

If algorithm would work in O(min(n, m)) then in my example it would be just O(1) which is clearly not achievable (we can’t decide if element of L2 is present in L1 without looking at all elements of L1, assuming it is big enough so we will not stop earlier).

I think this would work (since they are sorted lists)

Get two pointers, one to the start of each list. A -> List1, B -> List2

This should take O(min(n,m)) since you will only traverse until you reach the end of one of the lists (whichever is shorter).

This could be modified to do the union by simply inserting the items in the second and third if statements…

Of course, this is after only one cup of coffee… :)

I found your blog recently; it’s a great read!

For this challenge I used Scheme (even though I tend to work in Python) since it seemed to line up well with my thought process. My solution is available here.

I was going to withhold the answers to leave time for people to find the solutions by themselves, but they’re already in! (Clayton was the first to give his answer)

Let L1 = [1,2, …, n] and L2 = [ n ]. Assuming this is linked-list to access last element of L1 we must perform O(n) operations, so there don’t exist O(min(n,m)) algorithm.

Even with double-linked list with pointers to head, and tail it still impossible (ex. by placing only element of L2 in center of L1).

Not sure I understand what you’re saying?

If algorithm would work in O(min(n, m)) then in my example it would be just O(1) which is clearly not achievable (we can’t decide if element of L2 is present in L1 without looking at all elements of L1, assuming it is big enough so we will not stop earlier).

The best you can do is O(max(n,m))