CareerCup

My gut feeling tells me that: Do a bubble sort and then traverse it.
Is this correct?

Correct! but not optimize

Its good to use merger/heap sort rather then bubbel sort.
Improvement:
O(n*n) ===>> O(n*log(n))

But still there is a scope of improvement.

SUGGESTION-1
Use the red-black tree.
By this the retreval complexity get reduced to log(n).

SUGGESTION-2
We can try hashing to optimize the retreval complexity.
Inesrt the values in hash table in sorted order.
Use the key as sorted position and values as their actual value.

-There is a algorithm with running time O(n+klogn)
-However, there is also algo with O(n) time

Im missing why you would use a RB tree. What is the cost of populating a RB tree of size n? Since insertion takes 0(log(n)), wouldn't the cost of populating the tree be 0(nlog(n))? After you have the tree populated, how would you retrieve the xth largest value? I believe you would have to traverse the RB tree to find this value, which would be a worst case of 0(n). RB trees are great for searching for particular values, not for finding the xth largest value.

My gut tells me to sort using merge sort and then retrieve the xth value (IE array[x-1]).

How about using quick sort, which performs in the order of nlg(n). We can choose the median element to be the partition element and then perform quick sort recursively. Finding median from the array takes O(n) and quick sort O(nlg(n)). Now the ith largest number will be at the (n-i) position in the array.
Complexity id O(nlg(n))

Don't do sort. Sorting is too slow in this case. You don't need to sort everything to get the nth maximum. Use "Partition" algorithm, you will get theta(n).

1). Construct a heap with k elements. (Can be done in O(k).
2). For each of the remaining (n-k) elements,
a). If it's smaller than the root, discard it.
b). Otherwise, insert into the heap. ( O(logk) ).
3). When all the elements are finished, the root node is the kth largest.

Running time: O(k+(n-k)logk).

Use Median of Medians algorithm to find the k-th largest number.
O(n) time complexity.

The question should be:
Given a array of n integers we need to find the second largest number in it. And generalized to find kth largest number, where k << n.

As simple as it is, we can just keep scaning the array, storing the largest number and the second largest number and their indice.

if a[0] > a[1
1stLGNo = a[0]; 1stLGInd= 0; 2ndLGNo = a[1]; 1stLGInd= 1;
else
1stLGNo = a[1]; 1stLGInd= 1; 2ndLGNo = a[0]; 1stLGInd= 0;

for (i-2, i< n; i++)
{
Update(a[2], 1stLGNo,1stLGInd, 2ndLGNo,1stLGInd);
}
out put 2ndLGNo and 2ndLGInd.

This is a plain and simple O(n) algorithm. It is good for k < lg(n).
If k is close to n, we can use l = n - k << n to find the lth smallest number.
However, when k is close to lg(n), sorting algorithm becomes attractive.

The question should be:
Given a array of n integers we need to find the second largest number in it. And generalized to find kth largest number, where k << n.

As simple as it is, we can just keep scaning the array, storing the largest number and the second largest number and their indice.

if a[0] > a[1
1stLGNo = a[0]; 1stLGInd= 0; 2ndLGNo = a[1]; 1stLGInd= 1;
else
1stLGNo = a[1]; 1stLGInd= 1; 2ndLGNo = a[0]; 1stLGInd= 0;

for (i-2, i< n; i++)
{
Update(a[2], 1stLGNo,1stLGInd, 2ndLGNo,1stLGInd);
}
out put 2ndLGNo and 2ndLGInd.

This is a plain and simple O(n) algorithm. It is good for k < lg(n).
If k is close to n, we can use l = n - k << n to find the lth smallest number.
However, when k is close to lg(n), sorting algorithm becomes attractive.

Sorry for the errors:

if a[0] > a[1
1stLGNo = a[0]; 1stLGInd= 0; 2ndLGNo = a[1]; 2ndLGInd= 1;
else
1stLGNo = a[1]; 1stLGInd= 1; 2ndLGNo = a[0]; 2ndLGInd= 0;

int Bubble_Sort(input[], target_position)
{
int iterations = target_position - input.length + 1;
return bubble_sort_scan(input, iterations);
/* each bubble sort scan places 1 element to its final position in the array.
starting from the largest element. complexity will be O(n) for largest element.
O(2n) for 2nd largest
}

Use a loser tree. Extra space O(n) and time for initialization is O(n). Any subsequent retrieval is O(log n).


This way, for the second largest element, the complexity will be n + 2 log n which is of order O(n). Again, for the kth smallest element, the complexity is O(n + k * log n).

Correct me if I am wrong!!

-VJ

Using C++

int findKthLargest(vector<int> v,int k)
{
	partial_sort(v.begin(),v.begin() + k, v.end());
	return v.at(v.size () - k-1);


}
int findKthSmallest(vector<int> v,int k)
{
	
	partial_sort(v.begin(),v.begin()+k ,v.end ());
	
	return v.at(k-1);
	
}

Find the largest number of the array in one pass -> O(n)
in the next pass of the array find the number which is just less than largest -> O(n)
Total time: O(n)+O(n)=O(n)

public void FindSec()
{
int[] arr = { 1,2,0,-1,8,26,1,26};
int high, secHigh, temp, i;

high = secHigh = arr[0];

for (i = 1; i < arr.Length; ++i)
{
temp = arr[i];
if(temp > high)
{
secHigh = high;
high = temp;
}
else if(temp >secHigh && temp != high)
{
secHigh = temp;
}
}

Question belongs to Order statistics Coreman 9th or 8th Chapter.
Finding the k th rank in array User Randomize-select average case complexity theta(n).
Use linear select guaranteed O(n)

Randomize-select(a,p,r,k)
{
if p==r
return a[p]
q=randomize-partition(a,p,r) //quick sort partition which gives pivot index
i = q-p+1
if(k==i)
return a[i]
else if(k<i)
return Randomize-select(a,p,r,k)
else
return Randomize-select(a,p,r,k-i)
}
randomize-partition(a,p,r)
{
n = rand(1...sizeof(a))
swap(a[n] <-> a[r])
partition(a,p,r)
}
partition(a,p,r)
{
x=a[r]
i=p-1;
for j=p to r-1 j++
{
if(a[j]<=x)
{
i++
a[i]<->a[j] //swap
}
}
a[i+1]<->a[r] //swap
}


call Randomize-select(a,1,10,k)

Recurrence Equation = T(n) = T(9n/10) + o(n) // say each time it divide in 9/10 and 1/10 and we are unlucky and each time we have to solve 9/10 problem.
solve using mater theorem case 3.. T(n) = o(n)

you can make guanteed o(n) by linear select .

Sort the sequence using BST sort o(nlogn)descending order
Put it in linked list
now run a loop n-1 times to remove the first element and add it to last of the linked list
now get the first element from the linked list.

How abt this one

Int getLarge(int[] a, int n){
int max = 0;
for(int i = 0; i< a.length; i++){
if(a[i]>max) max = a[i];
}

if(n == 1)return max;
else {
for(int i = 0; i< a.length; i++){
if(a[i]==max) a[i] = -65535;
}
return getLarge(a,n-1);
}
}

use a part of quick sort. Select the pivot element which is at position of K ( we have to find kth largest element) now swap all the elements smaller than k on left side to all the elements larger than k on right side till both pointers meet.
at the end of first iteration, kth position would have the correct element placed

Its the standard selection algorithm... O(n)

-Quick sort and hash elements as they are being sorted to remove multiples
-Pull (n-1)th element from your sorted array

There might be a cleaner or faster solution, but this works fairly neatly, I believe