The intergalactic vote for confidence (a number from 0 to 100) in the supreme ch

Question

The intergalactic vote for confidence (a number from 0 to 100) in the supreme chancellor is tomorrow! If over 50% of the galaxies are not confident in the commander (ie, have a confidence score of 50 or higher) he will be cast out the airlock! As the newspaper reporter for the galaxy times, you want to keep track and analyze of the scores as they come from the far flung galaxies. How can you return the median in O(1) time and enter a new score in O(log n) time where n is the number of galaxies whose scores have already been entered. Reminder: The median of 10, 19,21 is 19. The median of 10, 30, 90, 99 is 30490. The median of 10,30, 50, 60, 90 is 50.

Explanation / Answer

import java.util.HashMap; import java.util.Map; public class Main { //Calculating the median in o(1) time // Maintian a hashmap that has number of galaxies as key and value as array of Numbers public static void main(String[] args) { final int confidence_lowerbound = 0; final int confidence_upperbound = 100; // Hashmap has get , put and lookup in O(1) time hence Map galaxy = new HashMap(); // Lets assume the scores from far flung galaxy is stored in this map int sample[] = {10,30,50,60,90}; int sample1[] = {10,30,50}; int sample2[] = {10,20}; galaxy.put(sample.length,sample); galaxy.put(sample1.length,sample1); galaxy.put(sample2.length,sample2); //Finding the median in O(1) time System.out.println("Enter the median you want to search"); int userentered = 2; if(userentered % 2 == 0){ int[] q = galaxy.get(userentered); int median = (q[userentered/2]+q[userentered/2-1])/2; System.out.println("Finding median here for even number of array length" + median); }else{ int[] oddq = galaxy.get(userentered); int median1 = oddq[(int) Math.ceil(userentered/2)]; System.out.println("Median found on O(1) time is here for odd number of array length " + median1); } } }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.