Extracting elements from multiple sorted lists efficiently

Question

I was asked this interview question recently. I was able to come up with this which runs in \$O(k \log n)\$.

Given k <= n sorted arrays each of size n, there exists a data structure requiring \$O(kn)\$ preprocessing time and memory that answers iterated search queries in \$O(k + \log n)\$ time.

I have k sorted Lists, each of size \$n\$. I currently have hard-coded 5 sorted Lists each of size 3, but in general that can be a very high number.

I would like to search for a single element in each of the \$k\$ Lists. Obviously, I can binary search each array individually, which will result in \$O(k \log n)\$ where \$k\$ is number of sorted arrays.

Can I do it in \$O(k + \log n)\$ where \$k\$ is the number of sorted arrays? I think there might be some better way of doing it as we're doing the same searches \$k\$ times as of now.

private List<List<Integer>> dataInput;

public SearchItem(final List<List<Integer>> inputs) {
    dataInput = new ArrayList<List<Integer>>();
    for (List<Integer> input : inputs) {
        dataInput.add(new ArrayList<Integer>(input));
    }
}

public List<Integer> getItem(final Integer x) {
    List<Integer> outputs = new ArrayList<Integer>();
    for (List<Integer> data : dataInput) {
        int i = Collections.binarySearch(data, x); // binary searching the item
        if (i < 0)
            i = -(i + 1);
        outputs.add(i == data.size() ? null : data.get(i));
    }
    return outputs;
}

public static void main(String[] args) {
    List<List<Integer>> lists = new ArrayList<List<Integer>>();

    List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(3, 4, 6));
    List<Integer> list2 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
    List<Integer> list3 = new ArrayList<Integer>(Arrays.asList(2, 3, 6));
    List<Integer> list4 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
    List<Integer> list5 = new ArrayList<Integer>(Arrays.asList(4, 8, 13));

    lists.add(list1);
    lists.add(list2);
    lists.add(list3);
    lists.add(list4);
    lists.add(list5);

    SearchItem search = new SearchItem(lists);
    System.out.println(dataInput);

    List<Integer> dataOuput = search.getItem(5);

    System.out.println(dataOuput);
}

Whatever output I am seeing with my above code approach should come with the new approach as well which should work in \$O(k + \log n)\$. Is this possible to achieve? Can anyone provide an example of how this would work based on my example?

Answer 1

This is sooo off-topic for CR... but, since it is related to a previous answer, and since I want to see a blown mind ....:

consider the following code:

class Value<T> {
    private final T value;
    private final int[] arraypointers;
    private final int arraycursor = 0;

    Value(T value, int maxindex) {
        this.value = value;
        this.arraypointers = new int[maxindex];
    }

    public void addIndex(int pointer) {
        arraypointers[arraycursor++] = pointer;
    }

    ... some other stuff.
}

OK, the above class will be used as follows... consider the example data system, the value 4 appears in list1 and list5.

This would be stored as:

Value v = new Value(4, k);
v.addIndex(1);
v.addIndex(5);

Now, start with a LinkedList:

LinkedList<Value<Integer>> values = new LinkedList<>();

Then, iterator though each of your loops, and merge the values in to the linked list:

for (int datapointer = 0; datapointer < datalists.size(); datapointer++) {
    ListIterator<Value<Integer>> valit : values.listIterator();
    List<Integer> = datalists.get(datapointer);
    for (Integer addval : data) {
        boolean found = false;
        while (valit.hasNext()) {
            if (addval.compareTo(valit.next().value) >= 0) {
                found = true;
                Value<Integer> val = valit.previous();
                if (val.value.equals(addval) {
                    // update existing value
                    val.addIndex(datapointer);
                    // leave the iterator point backwards to 
                    // allow for dup values in the data.
                } else {
                    // add a new value
                    Value<Integer> val = new Value(addval, k);
                    val.addIndex(datapointer);
                    valit.add(val);
                    // leave the iterator pointing backwards.
                    // but need to move it back one.
                    valit.previous();
                }
            }
        }
        if (!found) {
            Value<Integer> val = new Value(addval, k);
            val.addIndex(datapointer);
            valit.add(val);
            valit.previous();
        }

    }
}

then, convert the LinkedList in to an ArrayList

List sortedvalues = new ArrayList<Value<Integer>>(values);

Right, here we now have a sorted list of Values<Integer>. Each Value has pointers back to the list(s) they came from.

The space complexity for this is \$O(kn)\$ and we got there by doing a complexity \$O(kn)\$ nested loop (the inside while loop does not count because it is on an iterator that is outside the for loop, and it is part of the same complexity as the inner for loop)...

OK, so that is the \$O(kn)\$ preprocessing.

The lookup is a case of doing a binary search on the ArrayList (\$O(\log n)\$) and then iterating over the index pointers (\$O(k)\$).

Thus, the search is \$O(k + log n)\$.

Voila!

---

Working solution

Right, putting all the pieces together in a working solution:

Value.java

import java.util.Arrays;

class Value<T extends Comparable<T>> implements Comparable<Value<T>> {

    private final T value;

    private final T[] indices;

    public Value(T value, T[] data) {
        super();
        this.value = value;
        this.indices = data;
    }


    public void setIndex(int index, T val) {
        if (indices[index] == null) {
            indices[index] = val;
        }
    }

    public T[] getIndices() {
        return Arrays.copyOf(indices, indices.length);
    }

    public int compareToValue(T o) {
        return value.compareTo(o);
    }

    @Override
    public int compareTo(Value<T> o) {
        return value.compareTo(o.value);
    }

    @Override
    public int hashCode() {
        return value.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Value && value.equals(((Value<?>)obj).value);
    }

    @Override
    public String toString() {
        return String.format("%s -> %s", value, Arrays.toString(indices));
    }
}

MultiListIndex.java

package listsearch;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class MultiListIndex<T extends Comparable<T>> {

    private final List<Value<T>> index;
    private final Class<T> clazz;
    private final int width;

    public MultiListIndex(Class<T> clazz, Collection<List<T>> data) {
        this.clazz = clazz;
        this.width = data.size();
        this.index = preprocess(new ArrayList<>(data));
    }

    private final List<Value<T>> preprocess(List<List<T>> data) {
        LinkedList<Value<T>> processed = new LinkedList<>();
        Value<T> target = null;
        for (int listid = 0; listid < data.size(); listid++) {
            ListIterator<Value<T>> valit = processed.listIterator();
            Iterator<T> datait = data.get(listid).iterator();
            while (datait.hasNext()) {
                final T toadd = datait.next();
                boolean found = false;
                while (valit.hasNext()) {
                    final int compare = (target = valit.next()).compareToValue(toadd);
                    if (compare >= 0) {
                        // we have a match, or gone past.
                        valit.previous();
                        found = true;
                        if (compare == 0) {
                            target.setIndex(listid, toadd);
                        } else {
                            Value<T> newtarget = new Value<>(toadd, Arrays.copyOf(target.getIndices(), width));
                            valit.add(newtarget);
                            newtarget.setIndex(listid, toadd);
                            if (newtarget != valit.previous()) {
                                throw new IllegalStateException("Bad math!");
                            }
                        }
                        break;
                    }
                    target.setIndex(listid, toadd);
                }
                if (!found) {
                    Value<T> newtarget = new Value<>(toadd, buildArray(clazz, width));
                    valit.add(newtarget);
                    newtarget.setIndex(listid, toadd);
                }
            }
        }
        return new ArrayList<>(processed);
    }


    @SuppressWarnings("unchecked")
    private static final <T> T[] buildArray(Class<T> clazz, int size) {
        return (T[])Array.newInstance(clazz, size);
    }

    public List<T> searchValues(T value) {
        Value<T> key = new Value<>(value, null);
        int pos = Collections.binarySearch(index, key);
        if (pos < 0) {
            pos = -pos - 1;
        }
        if (pos >= index.size()) {
            return Arrays.asList(buildArray(clazz, width));
        }
        return Arrays.asList(Arrays.copyOf(index.get(pos).getIndices(), width));
    }


}

MultiListMain.java

package listsearch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MultiListMain {

    public static void main(String[] args) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();

        List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(3, 4, 6));
        List<Integer> list2 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
        List<Integer> list3 = new ArrayList<Integer>(Arrays.asList(2, 3, 6));
        List<Integer> list4 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
        List<Integer> list5 = new ArrayList<Integer>(Arrays.asList(4, 8, 13));

        lists.add(list1);
        lists.add(list2);
        lists.add(list3);
        lists.add(list4);
        lists.add(list5);

        MultiListIndex<Integer> search = new MultiListIndex<Integer>(
                Integer.class, lists);
        // System.out.println(dataInput);

        System.out.println(search.searchValues(0));
        System.out.println(search.searchValues(1));
        System.out.println(search.searchValues(2));
        System.out.println(search.searchValues(5));

    }

}

Output

[3, 1, 2, 1, 4]
[3, 1, 2, 1, 4]
[3, 2, 2, 2, 4]
[6, null, 6, null, 8]

Answer 2

\$O(k + \log n)\$ seems highly suspect to me. For large values of \$n\$ this is equivalent to \$O(\log n)\$ while for small values it's equivalent to \$O(k)\$. That they specified \$O(kn)\$ up-front processing leads me to consider the use of a hash table, but I don't see a structure that would provide the "closest-neighbor" capability required by the problem statement.

Obviously, this doesn't answer your "How can I do this?" question, but I question that it's even possible given their requirements, assuming you captured them accurately.

At this point, someone will likely provide a perfectly valid solution to blow my mind. :)

Answer 3

Here is what I came across that could be a solution.

O(k*n) for preproccessing means that you touch every element in every array. I will assume that the arrays do not overlap in stored values (it is not stated in the example). If you touch all the elements of all the arrays you can create intervals for every array and that can be done in O(k*n). The intrvals can be kept in a list of touples.

After you have these k intervals you could sort them in O(k*log(k)). If k is about the same as n then O(k*n + k*logk) = O(n*n + n*logn) = O(n^2). The nlogn can be omitted in assymptotic math because assymptotically is smaller. If k is small then you would get using the same math to O(k*n) (k*logk is definitely asymptotically smaller so it can be omitted). So using these arguments you can say it was done in O(k*n) time.

When searching you can get O(logk + logn). logk is to find the right interval using binary search and logn searching the array itself.

If you dont use the sorting of interval then you need to search the intervals in O(k) time and then the array itself O(logn) = O(k + logn). If my reasoning is correct and I did not omit any important limitation you should have your answer for O(k + logn), or even faster O(logk + logn) ;)