Geek Problem

So before the movies I asked the guys how they would solve the following problem …. I am writing a programm that has to execute some tasks in a certain order, I want to configure the order and which tasks to execute via some properties.

task.1 = getName
task.2  = getSize
//task.3 = doTaskFoo
task.4 = fnord
//task.5 = yaTask

That’s what I decided my properties should look like. I want to be able to comment out some properties as shown without changing a lot. Now what I need in my programm is a list that contains { getName, getSize, fnord }. Seems trivial at first but here are the constraints:

– the number of tasks is known but not the maximum number of tasks!
– the largest index is unknown
– the indexes used are unknown
– the Properties (java) object returns the key-value pairs in arbitrary order
– I do not want to store the key after I got the value -> therefore no ‘later’ sorting possible
– my solution is O(n) where n is the max-index used (at least I believe that – prove me wrong)

I am probably forgetting some of the constraints. Anyone have a solution? I have one and will post it later ….. I am sure mine is not the ‘optimal’ solution but it took me some time to find it.

3 Replies to “Geek Problem”

  1. ArrayList result = new ArrayList();

    Object fnord = new Object();
    ArrayList fnords = new ArrayList();
    fnords.add(fnord);

    Iterator i= props.keySet().iterator();
    while (i.hasNext()) {
    String key= (String) i.next();
    String value= props.getProperty(key);
    key = key.substring(complete.length());
    if(key.indexOf(‘.’)>-1)
    key = key.substring(0,key.indexOf(‘.’));
    int position = new Integer(key).intValue();

    while(position>result.size()-1)
    result.add(fnord);

    result.set(position,value);

    }

    result.removeAll(fnords);

    To those who might say that the nested loop will make this O(n*n) instead of O(n): of course fnords only will be inserted to a maximum of the largest index n that is used, once! If the list size is already sufficiently large to insert the current task the loop will not be executed. The removing of fnords should also be at least O(n). The best sorting algorithms perform at O(n*log n) which is a worst case estimate whereas this solution always needs n. And it is more space efficient since the numbers do not need to be stored!

    Someone suggested using a TreeSet to sort the tasks, if the TreeSet somehow encodes the numbers as the position of the ArrayList does and increases in size automatically you could save the insertion of fnords but still this makes it O(n) and no better because you will have to take a look at each task once!

Comments are closed.