CareerCup

If K number does not have to be consecutive, just sort them and added up the last ones.. But I think it has to be consecutive, else there is no point. Well then raghu.slp will need to be more clear before just posting. =)

find top k elements from the file using mean heap. Sum them up

A O(nlogk) solution is possible:

1. Built a balanced binary tree with the first k elements of the tree and store the least element in a separate variable.- O(klogk)
2. If new element greater than the least element, remove least element from tree and reorder the tree - O(logk)
3. Above step done for all n values - O(nlogk)
4.Sum up all the elements of the tree after the entire list is traversed - 0(k)

Total Complexity - O(nlogk+klogk+k)

With k being small the solution is O(nlogk)

same can be done using minheap:
Make minHeap using the first k integers. O(K)
Then for all the subsequent values compare them with the head. if head is small then the value then replace head and do proclateDown. Do the same for all the values.
At the end add all the elements of the array(heap).

Yup, maintain a min heap of k elements. O(nlogK)

if you dont want to use a max heap to save the O(k) space...you could use the quick select algorithm(finding Kth largest element algo) from CLRS..O(kn) time.

if you dont want to use a max heap to save the O(k) space...you could use the quick select algorithm(finding Kth largest element algo) from CLRS..O(kn) time.

Can't we use linear select to find Kth rank..

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[]{32,3,1,213,42,3,13,3};
int p = 0;
int r = a.length-1;
int k=4;
quickSort(a,p,r);
quickSelect(a,p,r,k);
for(in i=k;i<=r;i++)
System.out.println(a[i]);
}

private static int quickSelect(int[] a,int p,int r, int k)
{
if(p==r) return p;
int q=randomizedPartition(a, p, r);
int i=q-p+1;
if(i==k)
return q;
else if(k<i)
return quickSelect(a, p, q-1, k);
else
return quickSelect(a, q+1, r, k-i);
}

private static int randomizedPartition(int[] a, int p, int r) {
// TODO Auto-generated method stub
int n = (int)((r-p+1) * Math.random()) ;
n=n+p;
int x = a[n];
a[n]=a[r];
a[r]=x;
return partition(a,p,r);
}

private static int partition(int[] a, int p, int r) {
// TODO Auto-generated method stub
int x = a[r];
int i = p-1;
for(int j=p;j<r;j++)
{
if(a[j]<=x)
{
i=i+1;
int temp = a[j];
a[j]=a[i];
a[i]=temp;
}
}
int temp = a[r];
a[r]=a[i+1];
a[i+1]=temp;
return i+1;
}
}}}

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = new int[]{32,3,1,213,42,3,13,3};
		int p = 0;
		int r = a.length-1;
		int i=k; //here is k input
		quickSort(a,p,r);
		quickSelect(a,p,r,i);
                int sum=0;
		for(i=k;i<=r;i++)
			sum=sum+a[i];
	}
	
	private static void quickSort(int[] a,int p ,int r)
	{
		if(p>r)
			return;
		int q = randomizedPartition(a,p,r);
		quickSort(a,p,q-1);
		quickSort(a,q+1,r);
		
	}
	private static int quickSelect(int[] a,int p,int r, int i)
	{
		if(p==r) return p;
		int q=randomizedPartition(a, p, r);
		int k=q-p+1;
		if(i==k)
			return q;
		else if(i<k)
			return quickSelect(a, p, q-1, i);
		else
			return quickSelect(a, q+1, r, i-k);
	}

	private static int randomizedPartition(int[] a, int p, int r) {
		// TODO Auto-generated method stub
		int n = (int)((r-p+1) * Math.random())  ;
		n=n+p;
		int x = a[n];
		a[n]=a[r];
		a[r]=x;
		return partition(a,p,r);
	}

	private static int partition(int[] a, int p, int r) {
		// TODO Auto-generated method stub
		int x  = a[r];
		int i  = p-1;
		for(int j=p;j<r;j++)
		{
			if(a[j]<=x)
			{
				i=i+1;
				int temp = a[j];
				a[j]=a[i];
				a[i]=temp;
			}	
		}
		int temp = a[r];
		a[r]=a[i+1];
		a[i+1]=temp;
		return i+1;
	}

use a queue of size k
enqueue if scanner.nextInt() > q.front

at the end sum the elements in the queue

time comlexity = O(n)

Find (N-K)th largest element using meadian finding algorithms - O(n)
Now partition into elements with this element as pivot - O(n)
Sum up the largest K elements = O(K) = O(n)

Total is O(n)

I think Sriram solution is best.

1 Get kth largest number, by randomized select - O(n)
2 Partition around this number to get numbers larger than the kth largest number - O(n).
Total time = O(n) , k doesnt appear.