CareerCup

Use the selection rank algorithm.

Pick a random element in the array and use it as a ‘pivot’. Move all elements smaller than that element to one side of the array, and all elements larger to the other side.
»»If there are exactly i elements on the right, then you just find the smallest element on that side.
»»Otherwise, if the right side is bigger than i, repeat the algorithm on the right. If the right side is smaller than i, repeat the algorithm on the left for i – right.size().

cc book problem

Technically, you could go through the array 1000 times and each time get the max value which is smaller than the previous max value you had already found. This is exactly This will almost require 2000(n) comparisons.

Another approach, with an extra O(n) space is this:
1) Build a Max-Heap in O(N) time and space (I guess will take around 3n swaps and compares).
2) Extract-Max 1000 time which takes at worst 2000 log(N) time.

use median of medians, O(n), to get 1000th largest
then scan array picking out all numbers >= the one you got from above
Runtime: O(n) worst case
------------------------
or you can use QuickSelect for 1000th largest (expected linear, but worst case with low probability to be quadratic)

Loop over the numbers and put them into an array of size 1000. Keep track of the index and value of the lowest number, when you need to replace it, loop over the array for the new lowest.

Should be 1001n or O(n) unless I'm missing something.

#include <iostream>     
#include <algorithm>
#include <vector>

using namespace std;

const int K = 1000;
const int N = 100000;

int main () {
    vector<int> v;

    for (int i = 0; i < K; i++) {
        int d = rand();
        v.push_back(d);
    }

    // create a min-heap with K elements
    make_heap (v.begin(),v.end(), greater<int>());

    for (int i = 0; i < N; i++) {
        int d = rand();

        // if the new number is greater than the min value of the heap
        // remove the min value from the heap, and add the new value in 
        // the heap
        if (d > v.front()) {
            pop_heap (v.begin(),v.end(), greater<int>()); 
            v.pop_back();

            v.push_back(d);
            push_heap (v.begin(),v.end(), greater<int>());
        }
    }

    sort_heap (v.begin(),v.end(), greater<int>());

    for (int i : v) cout << i << " "; 
    cout << endl;

    return 0;
}

Use Selection Rank algoritm

Pick a random element in the array and use it as a ‘pivot’. Move all elements smaller than that element to one side of the array, and all elements larger to the other side.
»»If there are exactly i elements on the right, then you just find the smallest element on that side.
»»Otherwise, if the right side is bigger than i, repeat the algorithm on the right. If the right side is smaller than i, repeat the algorithm on the left for i – right.size().

cc book problem

Define a special data structure backed by doubly linked list with support of following features
(1) Add(Element) which can add up to 1000 elements in the list
(2) An internal var SIZE to record correct element size and each Add function check SIZE
(3) An internal var currentMIN to store current smallest item
(4) An internal pointer points to Node storing the var for currentMin
(5) When doing add(Element) if element > currentMin, then we append this new element to head of the list and remove the node storing currentMin

After insertion to this list from item 0 to n, then we will get a list storing only the largest 1000 elements

Find 1001th smallest element in O(n) time using the Kth smallest logic. All the elements on less than this element is the answer.

max heap of 1000 size can work.as it take time complexity of n* log(1000) here log(1000) is constant,so time complexity is 0(n)

We have to use augmented data structure.
We have to create a balanced binary search tree.
Node structure will be like

Node
{
	Node Left;
	Node Right;
	int value;
	int NoOfChildNodes;
}

While adding each node we keep on updating "NoOfChildNodes" for all nodes who all will
be parent of new node.

After creating that tree we can find any ith Min/Max Node.

Now we have to find 1000th min node
we will start from root node and start traversing downwards.

If (node.NoOfChildNodes > 1000)
	// traverse on right child
else 
	// traverse on right child. We have to update the i value also.

Let node.NoOfChildNodes = 1200 and i = 1000
if node.Left.NoOfChildNodes = 700 and Node.right.NoOfChildNodes = 500

then we have to find 300th Min element in right sub tree. (1000-700).
Keep on traversing downward till we get desired node.

Complexity computation
Making Balanced Binary search tree(ex AVL tree) for n nodes is: O(nlog(n))
For searching element in BST : O(log n)

For very large n vale , log(n) is negligible
that is nlog(n)+log(n) ~= nlog(n)

Heap is always the best way to find 'k' min or max numbers.....

before you answer this question, you should ask
1) how big is the dataset, if it's huge and cannot fit in memory, you can use a minheap
2) otherwise, use selection algorithm.
3) can you change the data, since sort will change the array
4) how much extra space you can use
Ask these questions before you give a solution

How about this Divide the array into 1000 chunks and then run findMaxNumber in each parallely ?.

using partition, till we pivot index is equal to 1000
public static int partition(int arr[], int left, int right) {
		int pivot = arr[(left+right)/2];
		int j = 0;
		int y = 0;
		int pivotIndex = (left+right)/2;

		for (j = left, y = right; j < y;) {
			if (arr[j] >= pivot && arr[y] <= pivot) {
				if (j == pivotIndex) {
					pivotIndex = y;

				} else if (y == pivotIndex) {
					pivotIndex = j;
				}
				int temp = arr[j];
				arr[j] = arr[y];
				arr[y] = temp;

			}

			if (arr[j] < pivot) {
				j++;
			}
			if (arr[y] > pivot) {
				y--;
			}

		}
		return pivotIndex;
	}
	
	
	public static void finKthIndex(int[] arr,int k)
	{
		 int pivotIndex =-1 ;
		int left =0;
		int right = arr.length-1;
		do
		{
			
			 pivotIndex = partition(arr, left, right);
			if(pivotIndex==k)
			{
				System.out.println("Got it");
			} else if(pivotIndex > k)
			{
				right = pivotIndex;
				
			} else
			{
				left = pivotIndex;
			}
			 
			 
		}
		while(pivotIndex!=k);
		
	}

i think one pass bubble sort will give us the max in O(n) time.

Use a min heap of size 1000 and compare every element of array with top of heap. If the element is bigger than insert it in the heap. When all the elements in the array are processed , you get the result in the heap.

Well use Median of Medians to find the 1000th Number. In theory MOM is fast but in practice it works better if we choose a random number as the pivot. The algorithm to find the 1000th largest number is O(n). Once we find the 1000th number in once scan(O(n)) we can find the 1000 largest numbers.

Use Bubble sort ,instead of running it n times run it 1000 times only.

Build a max heap from the unsorted array it will take O(n) time. Then extract 1000 elements from it which will be order of 1000log(n) . The overall complexity will be O(n) as 1000<n.

It can be solved using medians of medians algorithm. It only gurantees O(n) worst case time complexity in ranking an element in a unsorted array. Normal Ranking algo using random pivot takes O(n2) in worst case, average case is O(n).
It can be found in Introduction to Algorithms-Cormen book in Chapter medians and Order Statistics.

median of medians algorithm is the way to go. As dhruba.work rightly pointed CLRS book has a chapter on this.

Use a max-heap (array implementation). Insertion complexity is O(log N).
The 1st 1000 elements in this array are the 1000 largest numbers.

In questions like these, it is helpful to ask more about the nature of the dataset. For e.g. If it contains unique integers within a certain range, we can just use a bit-vector to represent those integers and read the bit vector from the beginning to give a sorted representation. This is O(N) time.

public class Largest1000NumberFromArrayUnknownLength {

	public static void main(String[] args) {

		Stack<Integer> s1 = new Stack<Integer>();
		Stack<Integer> s2 = new Stack<Integer>();

		int[] a = { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};

		for (int i = 0; i < a.length; i++) {
			s1.push(a[i]);
		}
		
		for (int i = 0; i < a.length; i++) {

				if (s1.peek() > a[i]) {
					s2.push(s1.pop());
				}
			 else {
				s1.push(a[i]);
			}
		}
		for (int i = 0; i < 5; i++) {
			System.out.println(s1.pop());
		}

	}
}

#define Swap(a,b)(a=b+a-(b=a))
#include<iostream>
using namespace std;
int a[1000000],n,k;
void place(int x,int y)//o(n) approx. by T.P TRIPATHY
{
    int pvt = (x+y)>>1;
    while(1){//O(n/k)
            bool l = false,r = false;
            for(int i = x;i< pvt;++i)
                if(a[i] > a[pvt]) {Swap(a[i],a[pvt]);pvt = i;l = true;break;}
            for(int i = y;i >pvt;--i)
                if(a[i] < a[pvt]) {Swap(a[i],a[pvt]);pvt = i;r = true;break;}
            if(!l && !r) break;
            }
    if(n-pvt+1 >= k) {for(int i=0;i<n;++i) if(i >= n-k) cout<<a[i]<<" ";return;}
    else  place(x,pvt-1);
}
int main()
{
    cin>>n>>k;//n = no of elements and k = no of bigger elements we want
    for(int i =0;i<n;++i) cin>>a[i];//given array
    place(0,n-1);//worst case O(n+ n/2 + n/4 + n/8..............) < O(2*n)
    return 0;
}

hash it using x%n function........initialize the hashing array above the size limit......then check whether a no. is present in the hashtable from end...i.e n-1....if present print and increment count..when count reaches 1000 break...
if wrong plz comment ur suggestions

I am thinking for using bitwise hash, suppose its integer then there is need of 2 ^ 27 integer array, if we use double hashing then this required size of continguous space can be reduced in range of 2^14 to 2 ^ 27. For each number first hash will decide right array and 2nd hash will place in that specific array bit as per its place in array.
Then scan numbers from maximum, first 1000 numbers will be maximum. To reduce complexity we can put number count with array so that don't need to scan array those are blank.

What about radix sort???