Module assignment: Live task queue and latency monitor

What you will build

This assignment brings the module together. You will write one C++ program that runs a small live service. The service keeps a queue of waiting tasks, where the most urgent task is served first. It also keeps a stream of latency samples, and it must report the median of those samples at any time. Commands arrive one per line from the input, and the program prints an answer for some of them.

The assignment uses five ideas from the module. You will use a min-heap through priority_queue with a custom order, which is the core of the task queue. You will use lazy deletion, which is the technique for cancelling a task that is already inside a heap. You will answer a top-K query without losing any task. You will keep a running median with two heaps, a max-heap for the lower half and a min-heap for the upper half. And you will read and check the program's behaviour on empty inputs, which is where most heap bugs hide.

You do not need new theory. Every part is a direct use of something from lessons 1 to 5. The hard part is combining them so the commands stay correct in any order. Read the whole specification before you write any code, and plan which heap holds which data.

The specification

The first line of input holds a number n, the count of commands that follow. Each of the next n lines is one command. The program reads the commands in order and prints one output line for each command that asks a question. Commands that only change state print nothing.

Task names are words made of lowercase letters, with no spaces. Each task name is used by only one ADD in the whole input. A task that is added is waiting until one of three things happens: it is run by NEXT, it is cancelled by CANCEL, or the input ends. A task has a priority, which is a whole number from 0 to 1000. A smaller priority number means the task is more urgent. Two waiting tasks with the same priority are ordered by name, with the alphabetically smaller name first.

Sample values are whole numbers from 0 to 1000000.

These are the commands:

• ADD name priority makes name a waiting task with the given priority. It prints nothing.
• NEXT removes the most urgent waiting task and prints its name. If no task is waiting, it prints none.
• CANCEL name removes name from the waiting tasks, if it is waiting. If it is not waiting, for example because it was never added, already ran or was already cancelled, it does nothing and prints nothing.
• TOPK k prints the names of the k most urgent waiting tasks, most urgent first, separated by single spaces. It does not change the waiting tasks. If fewer than k tasks are waiting, print all of them. If no task is waiting, print none. You may assume k is at least 1.
• SAMPLE x adds the latency sample x. It prints nothing.
• MEDIAN prints the median of all samples so far, in the same format as the course: a whole number, or a whole number followed by .5 when the median is halfway between two integers. If no sample has been added, it prints none.

Here are three examples. Each one shows the input, then the exact output.

Example 1. The TOPK 2 query comes before NEXT, and the cancelled task never runs.

11
ADD write 3
ADD buy 1
ADD call 1
TOPK 2
NEXT
CANCEL call
ADD rest 5
TOPK 5
SAMPLE 10
SAMPLE 4
MEDIAN

buy call
buy
write rest
7

Look at the order buy then call. Both have priority 1, so the name decides, and buy is first. The TOPK 2 line shows both of them without removing anything, so NEXT still returns buy. After call is cancelled, it cannot appear in the next TOPK. The median of 10 and 4 is (4 + 10) / 2 = 7.

Example 2. The empty cases and cancelling an unknown task.

9
NEXT
TOPK 3
MEDIAN
ADD a 2
ADD b 2
CANCEL zed
TOPK 3
NEXT
NEXT

none
none
none
a b
a
b

Every query before the first ADD returns none. The CANCEL zed line prints nothing, because zed was never added.

Example 3. The median changes between an odd and an even count.

6
SAMPLE 5
MEDIAN
SAMPLE 8
MEDIAN
SAMPLE 1
MEDIAN

5
6.5
5

After 5 and 8 the median is 6.5, which is the course format for a median halfway between two whole numbers.

Requirements checklist

Before you submit, check each item. Each one is a behaviour the grader tests.

• The program reads n, then exactly n command lines, and stops after the last command.
• ADD followed by NEXT returns tasks by priority, smaller first.
• Two tasks with the same priority come out in alphabetical order of name.
• NEXT on an empty set of waiting tasks prints none and does not crash.
• CANCEL removes a waiting task so that NEXT and TOPK no longer show it.
• CANCEL on a name that is not waiting prints nothing and changes nothing.
• TOPK k prints up to k names in urgency order and leaves the waiting tasks unchanged.
• TOPK prints none when no task is waiting.
• SAMPLE and MEDIAN agree with the median of all samples, for both odd and even counts.
• MEDIAN prints none before any sample is added.
• The program handles 200000 commands in a few seconds. Avoid copying the whole queue for each TOPK.
• The program has no undefined behaviour: it never reads top on an empty priority_queue, and it never reads past the end of a container.

Grading rubric

Your score depends on which behaviours work. The three levels below describe what each score looks like in practice.

60 percent: the core queue works. ADD and NEXT give the correct order for distinct priorities. NEXT prints none when empty. The program compiles and prints the answers for examples 1 and 2 when CANCEL and TOPK are removed from the input. A solution at this level usually has a plain priority_queue and no cancel support.

80 percent: the full queue and the top-K query work. Everything at 60 percent is correct, and CANCEL removes a waiting task so that it never runs. TOPK returns up to k live names in order, without losing any task from the queue. Equal priorities are sorted by name. Example 1 and example 2 print exactly the expected output.

100 percent: the median and the edge cases are correct too. Everything at 80 percent is correct, SAMPLE and MEDIAN print the course format for both odd and even counts, and the program passes examples 1 to 3 and a set of hidden tests with long streams. The code is clear enough that a reader can see where the heaps are, and it uses no undefined behaviour. A solution at this level passes the timing check with 200000 commands that include many TOPK queries.

Hidden tests check the same behaviours with different numbers. Expect cancelled tasks that were cancelled after they reached the top of the queue, TOPK after a cancel and before a NEXT, equal priorities with names that compare in different orders, and MEDIAN after many samples.

Planning the data

Before you write code, decide what each part of the program stores. A plan like this makes the code short and easy to check.

The waiting tasks need two things: the order in which they are served, and the answer to "is this name still waiting?". One priority_queue gives the order. A set of waiting names gives the second answer. A heap cannot remove a task from the middle, so cancelling a task marks it as gone, and the heap entry is skipped when it reaches the top. That is lazy deletion, and it is the technique you saw in lesson 3.

The samples need a running median. Use the two heaps from lesson 5. The lower heap is a max-heap, and the upper heap is a min-heap. Keep the sizes equal or one apart after each sample.

The reading loop needs a way to turn each command word into an action. An if chain on the command text is enough for six commands.

Write the plan on paper: one line for each part, and the name of the data structure. Then check it against the examples before you write the first line of code.

Hints

The hints below are hidden. Open each one only after you have tried the step on your own.

Testing your work

Run the program on each example and compare the output with the expected output, line by line. A good way to compare is to save your output to a file and use a text comparison tool, so that a missing space or a missing line stands out.

Then test the parts that most solutions get wrong. Try these by hand before you run them:

• A NEXT after every task was cancelled. It must print none, not a cancelled name.
• A TOPK 2 when only one task is waiting. It must print that one name, not two.
• Two CANCEL commands for the same name. The second must do nothing.
• A MEDIAN after a single sample. The answer is that sample.
• A MEDIAN after two samples that are equal. The answer is that value, with no .5.
• A TOPK followed by a NEXT. The NEXT must return the same name that TOPK listed first, which proves TOPK did not remove it.

If a test fails, check the heap entries first. Most wrong answers come from a cancelled entry that was returned by mistake, or a live entry that was dropped by TOPK.

Reference solution

Try the assignment before you open this section. The solution below passes the three examples, and it agrees with a simple model on 60 random command streams. Read it after you have a working version, and compare how it handles lazy deletion and TOPK.

#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
 
// Running median of the SAMPLE values, using a max-heap for the lower half
// and a min-heap for the upper half.
class RunningMedian {
public:
    void add(int x) {
        if (low.empty() || x <= low.top()) {
            low.push(x);
        } else {
            high.push(x);
        }
        if ((int)low.size() > (int)high.size() + 1) {
            high.push(low.top());
            low.pop();
        } else if ((int)high.size() > (int)low.size()) {
            low.push(high.top());
            high.pop();
        }
    }
 
    bool empty() const { return low.empty(); }
 
    // Twice the median, so a .5 median stays a whole number.
    int twiceMedian() const {
        if ((int)low.size() > (int)high.size()) {
            return 2 * low.top();
        }
        return low.top() + high.top();
    }
 
private:
    priority_queue<int> low;
    priority_queue<int, vector<int>, greater<int>> high;
};
 
// Waiting tasks with lazy deletion. The heap holds (priority, name) pairs.
// A pair is live only while its name is still in the waiting set.
class TaskQueue {
public:
    void add(const string& name, int priority) {
        waiting.insert(name);
        heap.push(make_tuple(priority, name));
    }
 
    void cancel(const string& name) {
        waiting.erase(name);
    }
 
    // Removes and returns the most urgent live task, or "" when none is left.
    string next() {
        while (!heap.empty()) {
            auto item = heap.top();
            heap.pop();
            string name = get<1>(item);
            if (waiting.erase(name) > 0) {
                return name;
            }
        }
        return "";
    }
 
    // Returns up to k live task names in urgency order, without losing any task.
    vector<string> topK(size_t k) {
        vector<tuple<int, string>> taken;
        vector<string> names;
        while (!heap.empty() && names.size() < k) {
            auto item = heap.top();
            heap.pop();
            string name = get<1>(item);
            if (waiting.count(name) > 0) {
                names.push_back(name);
                taken.push_back(item);
            }
        }
        for (const auto& item : taken) {
            heap.push(item);
        }
        return names;
    }
 
private:
    set<string> waiting;
    priority_queue<tuple<int, string>, vector<tuple<int, string>>, greater<tuple<int, string>>> heap;
};
 
string formatTwice(int twice) {
    string s = to_string(twice / 2);
    if (twice % 2 != 0) {
        s += ".5";
    }
    return s;
}
 
int main() {
    int n;
    cin >> n;
    TaskQueue tasks;
    RunningMedian samples;
    for (int i = 0; i < n; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "ADD") {
            string name;
            int priority;
            cin >> name >> priority;
            tasks.add(name, priority);
        } else if (cmd == "NEXT") {
            string name = tasks.next();
            cout << (name.empty() ? "none" : name) << "\n";
        } else if (cmd == "CANCEL") {
            string name;
            cin >> name;
            tasks.cancel(name);
        } else if (cmd == "TOPK") {
            size_t k;
            cin >> k;
            vector<string> names = tasks.topK(k);
            if (names.empty()) {
                cout << "none\n";
            } else {
                for (size_t j = 0; j < names.size(); j++) {
                    if (j > 0) cout << " ";
                    cout << names[j];
                }
                cout << "\n";
            }
        } else if (cmd == "SAMPLE") {
            int x;
            cin >> x;
            samples.add(x);
        } else if (cmd == "MEDIAN") {
            if (samples.empty()) {
                cout << "none\n";
            } else {
                cout << formatTwice(samples.twiceMedian()) << "\n";
            }
        }
    }
    return 0;
}

Walk through the reference once by hand. For CANCEL call, the set loses call, but the heap entry (1, "call") stays. When TOPK 5 runs later, buy has already left, so it pops (1, "call") first. That name is no longer in the set, so the entry is dropped. Then it pops (3, "write") and (5, "rest"), which are live. The later TOPK never shows call, and no live task is lost.

Extension (optional)

If you finish early, add a MERGE command. It reads a number m, then m lines, each holding a sorted list of latency samples. Merge the lists with a min-heap of their current heads, as in lesson 4, and add each merged value as a sample, in order, with the same rules as SAMPLE. Test it on lists of different lengths and on an empty list, and check that MEDIAN still agrees with a sorted copy of all the samples.

What you practised

This assignment used every idea in the module: the heap shape and array layout from lesson 1, push and pop from lesson 2, priority_queue with a custom order from lesson 3, the top-K pattern from lesson 4, and the two-heap running median from lesson 5. It also asked you to combine those parts in one program and to check each command against the rules, which is the skill interviewers look for when they give a heap problem.