I have two lists: one list (list) contains elements of AnyType and one list (index) contains integers. The integers (in index) are sorted in ascending order!


To print out the elements in list 'list' @ index given by list 'index'.


list = {I, really, love, to, hate, you}
index = {0, 1, 4, 5}

printPartial(list, index) will produce the output:

"I really hate you"

The catch:

1. This must work for "all" lists that implements the List interface.
2. This has to be done in O(N) regardless of which type of List (i.e. ArrayList or LinkedList).


Both lists are of the same type.

public class PartialList<E> {

	public static <E> void printList(List<E> list, List<Integer> index) {
		if( list.size() < index.size() )
			System.out.println("meh, error or something...");

		if(list instanceof ArrayList<?>) {
			for(int i=0; i<index.size(); i++)
				System.out.println( list.get( index.get( i ) ) );
		else {	 
			Iterator<Integer> itr = index.iterator();
				System.out.println( list.get( ) );

For ArrayList, get() is O(1) and since I use a while-loop the program will be O(N) for ArrayLists.


Getting O(N) for LinkedLists.

If I'm not mistaken is O(1), so this doesn't pose a problem

However, list.get() is O(N) and the for-loop is O(N) for a total of O(N2)(squared).

How do I solve this? Or is it already solved since the integer-list (index) is sorted?


just iterate through the list and print the value when you have reached the index that is to be printed.

i = 0
n = 0
for each value in list
if i == index[n]
print list
n = n+1
i = i+1

this should work since the index list is sorted and should take O(N) w.r.t. list, not index.