4

I have a system that stores a huge number of tasks. Each task has the following parameters:

Time t       
Priority p

Every task has a unique time. That means no 2 tasks can have the same Time parameter.
However, Priority is not unique. Multiple tasks can have the same priorities.

I need to design a system which can address four types of queries. The probability of each type of query is equally likely. Following are the types of queries:

  1. UpdateTask(t,p)
    This query wants the system to set the priority of task at time t to priority p. If the task does not exist in the system, a fresh task is created. If the task is present, its priority is updated.

  2. DeleteTask(t)
    This query wants the system to delete a task that is associated with time t. If such a task is not present in the system, then no action needs to be taken.

  3. GetMaximumPriority() and GetMinimumPriority()
    This query wants the system to print the minimum priority and maximum priority of the tasks available in the system.

  4. GetPriorityofTaskAtMaximumTime()
    This query wants the system to print the priority of the task that has the maximum value of parameter t (time)

I need to design the data structure for this system and implement algorithms for those data structures. I need to implement this in Java.

My approach: Created a HashMap with Key as Time and Value as Priority. The HashMap allows me to address the first two queries in constant time. But the last two queries have a time complexity of O(n).

Question: Is there a better time efficient and space efficient data structures and algorithms for this problem? I mainly need an approach to solve this. Fully implemented code is not necessary. Thanks.

DAle
  • 8,990
  • 2
  • 26
  • 45
Dhumil Agarwal
  • 856
  • 2
  • 11
  • 19
  • Why not try to come up with a structure yourself and then ask either here (if you have problems) or at [codereview] (if you want opinions)? This looks like you either need to learn something (and that's best done by trying it yourself) or it's your job (in which case it's you who gets the money for the effort, so show some first ;) ). – Thomas Aug 01 '17 at 10:15
  • What does your Time look like? Can you use it as key value in a `Map – deHaar Aug 01 '17 at 10:16
  • I think the hardest query is Q4, do you have more information on this query? like does it need to be done in real time or can you cache some queries and process them in batch mode? Or do you know the range of time? It can be done in O(lg n) time if you batch process all the queries at once, but it seems to be not easy if you want real time result – Petar Petrovic Aug 01 '17 at 10:36
  • All the queries will not be available in advance. The query has to be answered only when it is available, depending on the data stored at that instant. So, it is kind of real time. – Dhumil Agarwal Aug 01 '17 at 10:40
  • Look at Java `TreeMap`. These will take care of all the remaining queries in O(log(n)) time. You'd need one keyed on time and another on priority. Update and delete will have to do the same operations in the treemaps. These are also O(log(n)). Should be straightforward. The linear space provides a nice speedup. You might find improvements around the edges, but this combination of operations won't admit a solution that's O(1) for all. – Gene Aug 01 '17 at 22:28

3 Answers3

3

One possible way is to maintain two indices: one for the time, and one for the priority. Let's take two balanced search trees with a constant time firstKey() / lastKey() operations. I will use the interface of the TreeMap, but it should have an implementation similar to std::map from c++ (it just maintains the iterators to the first and last elements during updates).

First map would be Map<Time, Priority> tasks , second - Map<Priority, Integer> priorities. The second map for every existing priority value stores the number of tasks with this priority value. Thus, you can use tasks for the fourth query, and priorities for the third query.

  1. UpdateTask(t, p) 

    Priority oldp = tasks.put(t, p);
if (oldp != null) {
    decreasePriority(oldp);     
} 
increasePriority(p);

    Complexity: O(log(n))

  2. DeleteTask(t)

    if (tasks.containsKey(t)) {
    Priority oldp = tasks.get(t);
    tasks.remove(t);
    decreasePriority(oldp); 
}

    Complexity: O(log(n))

  3. GetMaximumPriority(), GetMinimumPriority()

    return priorities.lastKey();

return priorities.firstKey();

    Complexity: O(1) (with proper lastKey()/firstKey() implementation, O(log(n)) with a java.util.TreeMap).

  4. GetPriorityofTaskAtMaximumTime()

    return tasks.lastEntry().getValue();

    Complexity: O(1) (with proper lastEntry() implementation, O(log(n)) with a java.util.TreeMap)

    void increasePriority(p) {
        if (priorities.hasKey(p)) { 
            priorities.put(p, priorities.get(p) + 1);
        } else {
            priorities.put(p, 1); 
        }    
    }

    void decreasePriority(p) {
        int count = priorities.get(p);
        if (count > 1) {  
            priorities.put(p, count - 1);
        } else {
            priorities.remove(p);
        }   
    }

As a result, you will avoid linear complexities in operations.

DAle
  • 8,990
  • 2
  • 26
  • 45
1

General approcah - may change based on your data types, I think you can have a type of Map data type for your time and priority with time as the key. Whenever you want to delete the data, search in that map using time as key and delete, similarly you can update using the time as key.

Then you can have a list one each for time as well as priority and then you can sort the list as per your need.

deepakl
  • 172
  • 8
  • Thanks for your suggestion. When the Update and Delete queries come up, I will need to update the 2 lists for each such query. So, the time complexity of first 2 types of queries increases significantly. How to address this? – Dhumil Agarwal Aug 01 '17 at 10:29
  • Well that was a just a general idea to your query, you can use better data type like deHaar is suggesting to make the improvements you want. – deepakl Aug 01 '17 at 10:32
0

You can try a Heap or PriorityQueue, which is able to find min and max in O(1) as stated here.
They also delete and extract min and max in O(log n), but searching will stay at O(n). You may have to implement a Comparatorfor your Task class…

deHaar
  • 17,687
  • 10
  • 38
  • 51
  • Actually a Priority queue is able to extract either the min or max element in constant time(but not both) and also supports deleting either the min or max element in logarithmic time(but not both). You need a bit more complex structure to achieve that(e.g. a combination of hash and two heaps) – Ivaylo Strandjev Aug 01 '17 at 12:49