1

We have to input integers into an array one bye one.While the process of input is going we can be asked to find the smallest numbers out of the top(greatest) 1/3rd of the the numbers,any number of times.

eg:

input 1

input 7 

input 9

tell the number

input 21

input 8

input 5

tell the number

input 11

tell the number

output should be:

9

9

11

Explanation:

  • till the first query the array would have numbers 1 7 9, so the top 1/3rd numbers would be 9.As their is only one number so its the smallest also.
  • when second query is made array would look like 1 7 9 21 8 5, so on sorting array would be:
    21 9 8 7 5 1, top 1/3rd numbers would be 21 and 9. smallest of those will be 9
  • in the final query array has 1 7 9 21 8 5 11, on sorting 21 11 9 8 7 5 1 top 1/3rd numbers would be 21 and 11. smallest of those is 11.

The total number of integers in the array can be 250000

My approach is to apply selection algorithm with partition but it is getting time limit exceeded.

amit
  • 175,853
  • 27
  • 231
  • 333
user1484638
  • 333
  • 1
  • 4
  • 11
  • Homework ? what's the question ? – Yochai Timmer Jul 09 '12 at 11:57
  • The problem is ill-posed. At the time of the third request a set contains 7 numbers, so it is ambiguous what is a third part of it. Seven ordered items could be partitioned into three as-much-as-possible-equal parts as 3+2+2 or 2+3+2 or 2+2+3, thus giving the 'top 1/3rd' either `21 11 9` or `21 11`, resulting in an answer `9` or `11`. The task description does dot define why it should be 11 and not 9. – CiaPan Dec 01 '15 at 09:15

3 Answers3

3

Why selection algorithm fails:
Note that using selection algorithm is linear in the #elements. Assuming #requests is linear in #elements - it will lead to a quadric solution, and this is why you get time limit exceeded.

An alternative approach: Maintain two heaps: a max heap H1 and a min heap H2

The max heap (H1) will hold the 2/3 lowest numbers while the min heap will gold the 1/3 highest numbers.

Now, for each element x you read, check if you need to increase the top 1/3 heap (H2), and if you do: you need to add max{x,H1.max()}. If you added H1.max() - you need to remove it from the heap, and insert x instead. If no addition is needed, check if x is bigger then H2.min(), if it is, remove the min form H2, insert it to H1, and add x to H1.


Note: the number you are looking for in this solution can be found in O(1) at any time, it is the minimum of the min heap (H2).

Total complexity if this solution is O(nlogn + k) - where n is the number of numbers, and k is the total number of "tell the number" requests.

Note: a simpler solution (though probably slower) will be to maintain the list sorted (in a BST or a skiplist for example), and use binary search to look for the relevant element.

Example:

init:
H1 = {}
H2 = {}

input1:
H1 = {1}
H2 = {}

input7:
H1={1,7}
H2 = {}

input 9: //need to add a max, in this case: x > H2.max() -> add x to H2.
H1 = {1,7}
H2 = {9}

tell the number
H2.min() = 9

input 21: // 21>9 -> remove H2.min() add it to H1, add x to H2
H1 = {1,7,9}
H2 = {21}

input 8:
H1 = {1,7,8,9}
H2 = {21}

input 5: //remove max from H1, add max to H2, add x to H1
H1 = {1,7,5,8}
H2 = {9,21}

tell the number
H2.min() = 9

input 11: //remove min from H2, add it to H1, add x to H2.
H1 = {1,7,5,8,9}
H2 = {11,21}
tell the number
H2.min() = 11
amit
  • 175,853
  • 27
  • 231
  • 333
0

(I assume this question is some sort of homework ("We have to") and accordingly I am not straightforwardly giving the answer.)

Reformulate your task: You are asked to find the 66th percentile with an online algorithm. There is already a SO question for the median, which is the 50th percentile, so you should be able to adapt from there. If that algorithm is no good, do some research on online median algorithms, most of which should also apply to your problem.

Community
  • 1
  • 1
thiton
  • 35,651
  • 4
  • 70
  • 100
  • The downside of using selection algorithms is that they are running in linear time relative to the input. Assuming #requests is linear with #elements, it will lead to a quadric solution, which is worse then maintaining the list sorted. This of course does not apply if #requests << #elements – amit Jul 09 '12 at 12:18
0

How about:

  1. Keep array in a sorted way, insertion cost = log(n)
  2. get smallest values out of 1/3 = O(1)
Rrr
  • 1,747
  • 3
  • 17
  • 22