median

Question  There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Solution Before going to solution what is the median. What is Median? Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. [Read More]

This pseudo-code holds for a Double Linked list: 1. init two pointers one at the start of the list(p1) and the other at the end (p2) 2. if p1=null or p2==null return NONE 3. At each iteration, visit node p1.next and p2.previous 4. if p1.next==p2.previous !=p1 || p2 then middle is obtained for an odd number of nodes. Return result 5. if p1.next==p2.previous=p1|| p2 then middle is for an even number of nodes. [Read More]

Problem Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. OR You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time) **OR ** [Read More]