Programming Challenge: List Intersection

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, L_1, and L_2, of lengths n and m, respectively. Your task is to device an algorithm that computes the intersection of L_1 and L_2 in O(\min(n,m)), therefore excluding search-based solution (which would be at least O(\min(n,m)\lg\min(n,m)).

Bonus. Propose an algorithm in O(\max(n,m)) to compute the union (in a set-theoretic sense, that is, L_1 \cup L_2).

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

6 Responses to Programming Challenge: List Intersection

  1. 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… :)

  2. Graham says:

    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.

  3. Steven Pigeon says:

    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)

    • wuch says:

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

  4. wuch says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: