All Tracks Algorithms Sorting Quick Sort Problem

Fredo and Modified Notifications System

Ad-Hoc, Data Structures, Easy-Medium, Sorting


Frustrated of getting notifications frequently on his mobile, Fredo decided to systemize it. He has N apps in his phone , each identified by its index (\(1 \le index \le N\)) and has some priority associated with it.The notification coming from an app has the same priority as the app.
He decides to read the notifications only when it is 1 o'clock , 2 o' clock and so on. That means, he would read the notifications maximum 24 times a day.
Between two consecutive hours (interval) , all the notifications that come from the apps are accumulated in a queue (an app can send multiple notifications). WIthin this time, he can also change the priority of few apps.
Fredo wants all notifications coming from an app to be merged into one notification , the position of this notification in the queue would be the position of the first notification coming from the app. All other notifications from that app are then removed from the queue.
When it is time for him to read the notifications, he wants all the notifications to be displayed according to their priority. If two notifications from different apps have same priority, he wants the app whose notification comes first in the queue to be displayed first.
He knows you are good at doing this stuff. So, he asks you to do this task for him .

The first line consists of an integer N, denoting the number of apps.
Next line consists of an array of priorities of apps. \(Priority[i]\) is the priority of app with index i.
Next line consists of an integer T, denoting the number of intervals for which the data is given.
In each interval,
The first line consists of two integers Q and U, denoting the number of notifications in the queue and number of priority updates respectively.
The next line consists of Q space separated integers denoting the queue for that interval.Let this queue be represented by array \(Queue\). \(Queue[i]\) is the app index from which notification is coming.
The next U lines consists of two integers J and P each, the first representing the app index and the second representing the new priority for that app.
Note : Any priority update in any interval will reflect in all the further intervals.

You have to print the order of display of the notifications after each interval in a new line. The display has to be done in non-increasing order of priority.

\(1 \le N \le 100\)
\(1 \le Priority[i] \le 100\); \(1 \le i \le N\)
\(1 \le T \le 24\)
\(0 \le Q \le 500\)
\(0 \le U \le 100\)
\(1 \le Queue[i] \le N\); \(1 \le i \le Q\)
\(1 \le J \le N\)
\(1 \le P \le 100\).

2 3 4 2 1 10 5 6 4 7
7 3
1 4 3 1 7 2 4
6 5
3 2
4 3
5 0
7 6 2 4 2
7 4 2 1 3 
7 6 2 4 

The given priority array is: [2,3,4,2,1,10,5,6,4,7]

In first interval,
The queue given is : [1,4,3,1,7,2,4] (These are the app indices)
Multiple notifications from app 4 will become one notification from 4, and similarly for 1. So, the queue after removing duplicates would like : [1,4,3,7,2]
After the updates, the priority array would like like: [2,3,2,3,1,5,5,6,4,7]

The highest priority is of app with index 7.
Apps 4 and 2 have same priority ,so, since 4 comes before 2 , it will remain first in the display also.
Next we display 1 and 3 , as they have same priority and 1 comes before 3 in the queue.

In second interval,
The priority array would remain same as after the first interval because there are no updates in this interval. So, the output array would be: 7,6,2,4

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

Honeywell iOS Hiring Challenge

View All Notifications