{"id":"5a28c1e4-3361-44a2-95e1-e74b2cbe02b2","name":"Median Priority Queue","description":"1. You are required to complete the code of our MedianPriorityQueue class. The class should mimic the behaviour of a PriorityQueue and give highest priority to median of it's data.\r\n2. Here is the list of functions that you are supposed to complete\r\n2.1. add -> Should accept new data.\r\n2.2. remove -> Should remove and return median value, if available or print \"Underflow\" otherwise and return -1\r\n2.3. peek -> Should return median value, if available or print \"Underflow\" otherwise and return -1\r\n2.4. size -> Should return the number of elements available\r\n3. Input and Output is managed for you.\r\n\r\nNote -> If there are even number of elements in the MedianPriorityQueue, consider the smaller median as median value.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <queue>\nusing namespace std;\n\nclass MedianPriorityQueue {\n public:\n priority_queue <int> left;\n priority_queue <int, vector<int>, greater<int>> right;\n \n void push(int val) {\n //write your code here\n }\n \n int pop() {\n //write your code here\n }\n \n int top() {\n //write your code here \n }\n \n int size() {\n //write your code here\n }\n};\n\nint main() {\n MedianPriorityQueue pq;\n \n string str;\n cin >> str;\n while(str!=\"quit\"){\n if(str==\"add\"){\n int val;\n cin >> val;\n pq.push(val);\n }\n else if(str==\"remove\"){\n int val = pq.pop();\n if(val != -1) {\n cout<<val<<endl;\n }\n }\n else if(str==\"peek\"){\n int val = pq.top();\n if(val != -1) {\n cout<<val<<endl;\n }\n }\n else if(str==\"size\"){\n cout<<pq.size()<<endl;\n }\n cin >> str;\n }\n \n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static class MedianPriorityQueue {\r\n PriorityQueue<Integer> left;\r\n PriorityQueue<Integer> right;\r\n\r\n public MedianPriorityQueue() {\r\n left = new PriorityQueue<>(Collections.reverseOrder());\r\n right = new PriorityQueue<>();\r\n }\r\n\r\n public void add(int val) {\r\n // write your code here\r\n }\r\n\r\n public int remove() {\r\n // write your code here\r\n }\r\n\r\n public int peek() {\r\n // write your code here\r\n }\r\n\r\n public int size() {\r\n // write your code here\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n MedianPriorityQueue qu = new MedianPriorityQueue();\r\n\r\n String str = br.readLine();\r\n while (str.equals(\"quit\") == false) {\r\n if (str.startsWith(\"add\")) {\r\n int val = Integer.parseInt(str.split(\" \")[1]);\r\n qu.add(val);\r\n } else if (str.startsWith(\"remove\")) {\r\n int val = qu.remove();\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"peek\")) {\r\n int val = qu.peek();\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"size\")) {\r\n System.out.println(qu.size());\r\n }\r\n str = br.readLine();\r\n }\r\n }\r\n}"},"python":{"code":"class newPriorityQueue(object):\n def __init__(self):\n self.queue = []\n\n def __str__(self):\n return ' '.join([str(i) for i in self.queue])\n\n def isEmpty(self):\n return len(self.queue) == 0\n\n def insert(self, data):\n self.queue.append(data)\n\n def delete(self):\n try:\n max = 0\n for i in range(len(self.queue)):\n if self.queue[i] < self.queue[max]:\n max = i\n item = self.queue[max]\n del self.queue[max]\n return item\n except IndexError:\n print()\n exit()\n \n \n def sz(self):\n return len(self.queue)\n\n\n\nclass PriorityQueue(object):\n def __init__(self):\n self.queue = []\n\n def __str__(self):\n return ' '.join([str(i) for i in self.queue])\n\n def isEmpty(self):\n return len(self.queue) == 0\n \n def insert(self, data):\n self.queue.append(data)\n \n def delete(self):\n try:\n max = 0\n for i in range(len(self.queue)):\n if self.queue[i] > self.queue[max]:\n max = i\n item = self.queue[max]\n del self.queue[max]\n return item\n except IndexError:\n print()\n exit()\n \n def top(self): \n return max(self.queue)\n \n \n def sz(self):\n return len(self.queue)\n\n\ndef size():\n #write your code here\n\n\n\ndef add(val):\n #write your code here\n\n\n \ndef remove():\n #write your code here\n \n\n \ndef peek():\n #write your code here\n \n\n\n\n\n\nleft = PriorityQueue()\nright= newPriorityQueue()\n\n\nwhile(1):\n s=input()\n if s[0]=='a':\n num=s[4:]\n val=int(num)\n add(val)\n \n elif s[0]=='r':\n val=remove()\n if val!=-1:\n print(val,end=\"\\n\")\n \n elif s[0]=='p':\n val=peek()\n if val!=-1:\n print(val,end=\"\\n\")\n \n else:\n break"}},"points":10,"difficulty":"hard","sampleInput":"add 10\r\nadd 20\r\nadd 30\r\nadd 40\r\npeek\r\nadd 50\r\npeek\r\nremove\r\npeek\r\nremove\r\npeek\r\nremove\r\npeek\r\nremove\r\npeek\r\nquit","sampleOutput":"20\r\n30\r\n30\r\n20\r\n20\r\n40\r\n40\r\n10\r\n10\r\n50","questionVideo":"https://www.youtube.com/embed/3k7tAOLBhK0","hints":[],"associated":[{"id":"3e96591c-57cb-49b1-8330-47a3ac33e03c","name":"Which of the following type of Priority queues are we using in \"Median Priority Queue\" problem?","slug":"which-of-the-following-type-of-priority-queues-are-we-using-in-median-priority-queue-problem","type":4},{"id":"a119ab98-5185-4e5a-8d98-5665c93cb7b8","name":"What will be the size of MedianPriority Queue in \"Median Priority Queue\" problem?","slug":"what-will-be-the-size-of-medianpriority-queue-in-median-priority-queue-problem","type":4},{"id":"de084013-f61a-47b5-a2df-209cd81740e3","name":"How many Priority Queues are used in \"Median Priority Queue\" problem?","slug":"how-many-priority-queues-are-used-in-median-priority-queue-problem","type":4},{"id":"e6e392d0-6197-42f7-9002-b3bc1f2aa314","name":"What is the time complexity od add() function in \"Median Priority Queue\" question?","slug":"what-is-the-time-complexity-od-add-function-in-median-priority-queue-question","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1254d21e-2209-40bc-9e24-00d135ace68d","name":"Hashmap And Heap For Beginners","slug":"hashmap-and-heap-for-beginners","type":0},{"id":"32b98844-1b0c-4849-9c71-fc4553cc4fa7","name":"Median Priority Queue","slug":"median-priority-queue","type":1}],"next":{"id":"fb8928a4-b4cc-4c8e-8e00-2c098fcbda2f","name":"Median Priority Queue","type":3,"slug":"median-priority-queue"},"prev":{"id":"23f88451-cdac-4b06-8967-d849053c7d54","name":"Sort K-sorted Array","type":3,"slug":"sort-k-sorted-array"}}}

Median Priority Queue

1. You are required to complete the code of our MedianPriorityQueue class. The class should mimic the behaviour of a PriorityQueue and give highest priority to median of it's data. 2. Here is the list of functions that you are supposed to complete 2.1. add -> Should accept new data. 2.2. remove -> Should remove and return median value, if available or print "Underflow" otherwise and return -1 2.3. peek -> Should return median value, if available or print "Underflow" otherwise and return -1 2.4. size -> Should return the number of elements available 3. Input and Output is managed for you. Note -> If there are even number of elements in the MedianPriorityQueue, consider the smaller median as median value.

{"id":"5a28c1e4-3361-44a2-95e1-e74b2cbe02b2","name":"Median Priority Queue","description":"1. You are required to complete the code of our MedianPriorityQueue class. The class should mimic the behaviour of a PriorityQueue and give highest priority to median of it's data.\r\n2. Here is the list of functions that you are supposed to complete\r\n2.1. add -> Should accept new data.\r\n2.2. remove -> Should remove and return median value, if available or print \"Underflow\" otherwise and return -1\r\n2.3. peek -> Should return median value, if available or print \"Underflow\" otherwise and return -1\r\n2.4. size -> Should return the number of elements available\r\n3. Input and Output is managed for you.\r\n\r\nNote -> If there are even number of elements in the MedianPriorityQueue, consider the smaller median as median value.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <queue>\nusing namespace std;\n\nclass MedianPriorityQueue {\n public:\n priority_queue <int> left;\n priority_queue <int, vector<int>, greater<int>> right;\n \n void push(int val) {\n //write your code here\n }\n \n int pop() {\n //write your code here\n }\n \n int top() {\n //write your code here \n }\n \n int size() {\n //write your code here\n }\n};\n\nint main() {\n MedianPriorityQueue pq;\n \n string str;\n cin >> str;\n while(str!=\"quit\"){\n if(str==\"add\"){\n int val;\n cin >> val;\n pq.push(val);\n }\n else if(str==\"remove\"){\n int val = pq.pop();\n if(val != -1) {\n cout<<val<<endl;\n }\n }\n else if(str==\"peek\"){\n int val = pq.top();\n if(val != -1) {\n cout<<val<<endl;\n }\n }\n else if(str==\"size\"){\n cout<<pq.size()<<endl;\n }\n cin >> str;\n }\n \n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static class MedianPriorityQueue {\r\n PriorityQueue<Integer> left;\r\n PriorityQueue<Integer> right;\r\n\r\n public MedianPriorityQueue() {\r\n left = new PriorityQueue<>(Collections.reverseOrder());\r\n right = new PriorityQueue<>();\r\n }\r\n\r\n public void add(int val) {\r\n // write your code here\r\n }\r\n\r\n public int remove() {\r\n // write your code here\r\n }\r\n\r\n public int peek() {\r\n // write your code here\r\n }\r\n\r\n public int size() {\r\n // write your code here\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n MedianPriorityQueue qu = new MedianPriorityQueue();\r\n\r\n String str = br.readLine();\r\n while (str.equals(\"quit\") == false) {\r\n if (str.startsWith(\"add\")) {\r\n int val = Integer.parseInt(str.split(\" \")[1]);\r\n qu.add(val);\r\n } else if (str.startsWith(\"remove\")) {\r\n int val = qu.remove();\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"peek\")) {\r\n int val = qu.peek();\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"size\")) {\r\n System.out.println(qu.size());\r\n }\r\n str = br.readLine();\r\n }\r\n }\r\n}"},"python":{"code":"class newPriorityQueue(object):\n def __init__(self):\n self.queue = []\n\n def __str__(self):\n return ' '.join([str(i) for i in self.queue])\n\n def isEmpty(self):\n return len(self.queue) == 0\n\n def insert(self, data):\n self.queue.append(data)\n\n def delete(self):\n try:\n max = 0\n for i in range(len(self.queue)):\n if self.queue[i] < self.queue[max]:\n max = i\n item = self.queue[max]\n del self.queue[max]\n return item\n except IndexError:\n print()\n exit()\n \n \n def sz(self):\n return len(self.queue)\n\n\n\nclass PriorityQueue(object):\n def __init__(self):\n self.queue = []\n\n def __str__(self):\n return ' '.join([str(i) for i in self.queue])\n\n def isEmpty(self):\n return len(self.queue) == 0\n \n def insert(self, data):\n self.queue.append(data)\n \n def delete(self):\n try:\n max = 0\n for i in range(len(self.queue)):\n if self.queue[i] > self.queue[max]:\n max = i\n item = self.queue[max]\n del self.queue[max]\n return item\n except IndexError:\n print()\n exit()\n \n def top(self): \n return max(self.queue)\n \n \n def sz(self):\n return len(self.queue)\n\n\ndef size():\n #write your code here\n\n\n\ndef add(val):\n #write your code here\n\n\n \ndef remove():\n #write your code here\n \n\n \ndef peek():\n #write your code here\n \n\n\n\n\n\nleft = PriorityQueue()\nright= newPriorityQueue()\n\n\nwhile(1):\n s=input()\n if s[0]=='a':\n num=s[4:]\n val=int(num)\n add(val)\n \n elif s[0]=='r':\n val=remove()\n if val!=-1:\n print(val,end=\"\\n\")\n \n elif s[0]=='p':\n val=peek()\n if val!=-1:\n print(val,end=\"\\n\")\n \n else:\n break"}},"points":10,"difficulty":"hard","sampleInput":"add 10\r\nadd 20\r\nadd 30\r\nadd 40\r\npeek\r\nadd 50\r\npeek\r\nremove\r\npeek\r\nremove\r\npeek\r\nremove\r\npeek\r\nremove\r\npeek\r\nquit","sampleOutput":"20\r\n30\r\n30\r\n20\r\n20\r\n40\r\n40\r\n10\r\n10\r\n50","questionVideo":"https://www.youtube.com/embed/3k7tAOLBhK0","hints":[],"associated":[{"id":"3e96591c-57cb-49b1-8330-47a3ac33e03c","name":"Which of the following type of Priority queues are we using in \"Median Priority Queue\" problem?","slug":"which-of-the-following-type-of-priority-queues-are-we-using-in-median-priority-queue-problem","type":4},{"id":"a119ab98-5185-4e5a-8d98-5665c93cb7b8","name":"What will be the size of MedianPriority Queue in \"Median Priority Queue\" problem?","slug":"what-will-be-the-size-of-medianpriority-queue-in-median-priority-queue-problem","type":4},{"id":"de084013-f61a-47b5-a2df-209cd81740e3","name":"How many Priority Queues are used in \"Median Priority Queue\" problem?","slug":"how-many-priority-queues-are-used-in-median-priority-queue-problem","type":4},{"id":"e6e392d0-6197-42f7-9002-b3bc1f2aa314","name":"What is the time complexity od add() function in \"Median Priority Queue\" question?","slug":"what-is-the-time-complexity-od-add-function-in-median-priority-queue-question","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1254d21e-2209-40bc-9e24-00d135ace68d","name":"Hashmap And Heap For Beginners","slug":"hashmap-and-heap-for-beginners","type":0},{"id":"32b98844-1b0c-4849-9c71-fc4553cc4fa7","name":"Median Priority Queue","slug":"median-priority-queue","type":1}],"next":{"id":"fb8928a4-b4cc-4c8e-8e00-2c098fcbda2f","name":"Median Priority Queue","type":3,"slug":"median-priority-queue"},"prev":{"id":"23f88451-cdac-4b06-8967-d849053c7d54","name":"Sort K-sorted Array","type":3,"slug":"sort-k-sorted-array"}}}
plane

Editor

Loading...

Median Priority Queue

hard

1. You are required to complete the code of our MedianPriorityQueue class. The class should mimic the behaviour of a PriorityQueue and give highest priority to median of it's data. 2. Here is the list of functions that you are supposed to complete 2.1. add -> Should accept new data. 2.2. remove -> Should remove and return median value, if available or print "Underflow" otherwise and return -1 2.3. peek -> Should return median value, if available or print "Underflow" otherwise and return -1 2.4. size -> Should return the number of elements available 3. Input and Output is managed for you. Note -> If there are even number of elements in the MedianPriorityQueue, consider the smaller median as median value.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

add 10 add 20 add 30 add 40 peek add 50 peek remove peek remove peek remove peek remove peek quit

Sample Output

20 30 30 20 20 40 40 10 10 50

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode