CareerCup

Using Radix sort on the value and the rank of each element, O(n) seems to be possible if we assume fixed (4 byte) int data type. For arbitrary length data type, this claim is invalid. It's obvious no comparison based approach can get an O(n) solution here.

A work through example to demonstrate the ranking computation.

A = [12, 2, 6, 14, 5, 9, 11]

consider rightmost bit LSB1
12, 2, 6, 14 => LSB1=0, so each with rank = 0
5, 9, 11 => LSB1=1, so each gets rank = 4 (size of element with LSB1=0)
so, after processing rightmost bit,
B = [0, 0, 0, 0, 4, 4, 4]

Next, consider 2nd rightmost bit LSB2
12, 5, 9 = > LSB2=0
   use radix sort on the rank of these elements
   current rank of 12 is 0, so it remains 0
   current rank of 5,9 is 4, so both rank is assigned 1
2, 6, 14, 11 => LSB2 = 1
   use radix sort on the rank of these elements
   current rank of 2, 6, 14 is 0, so each assigned to rank 3
   current rank of 11 is 4, so rank is assigned 6
so, after processing 2nd rightmost bit,
B = [0, 3, 3, 3, 1, 1, 6]

Next, consider 3nd rightmost bit LSB3
2, 9, 11 => LSB3 = 0
   use radix sort on the rank of these elements
   current rank of  9 is 1, so assigned to rank 0
   current rank of  2 is 3, so assigned to rank 1
   current rank of 11 is 6, so assigned to rank 2
12, 6, 14, 5 => LSB3 = 1
   use radix sort on the rank of these elements
   current rank of 12 is 0, so assigned to rank 3
   current rank of  5 is 1, so assigned to rank 4
   current rank of  6,14 is 3, so each assigned to rank 5
so, after processing 3rd rightmost bit,
B = [3, 1, 5, 5, 4, 0, 2]

Finally, consider 4th rightmost bit LSB4
2, 6, 5 => LSB4 = 0
   use radix sort on the rank of these elements
   current rank of 2 is 1, so assigned to rank 0
   current rank of 5 is 4, so assigned to rank 1
   current rank of 6 is 5, so assigned to rank 2
12, 14, 9, 11 => LSB4 = 1
   use radix sort on the rank of these elements
   current rank of  9 is 0, so assigned to rank 3
   current rank of 11 is 2, so assigned to rank 4
   current rank of 12 is 3, so assigned to rank 5
   current rank of 14 is 5, so assigned to rank 6
so, after processing 3rd rightmost bit,
B = [5, 0, 2, 6, 1, 3, 4]

I don't think the problem can be solved in O(n). Suppose the problem can be solved in O(n), then we can easily obtain the sorted array from the ranking result in O(n). Thus the sorting only takes O(n). It's impossible.

Without sorting? What does that even mean? Can I sort n-10 elements?

Anyway, a Theta(n^2) solution

// numbers: whose rank we need. Assumption: numbers are distinct (but code might still work)
// rank: the array in which to store ranks
// n: length of numbers (and rank) arrays.
void ComputeRank(int *numbers, int * rank, int n) {
    
    for(int i = 0; i < n; i++) {
        int curRank = 0;
        
        // We assume the rank of a[0...i-1] is already computed.
        // Now if we add a[i] to list, we need to update the ranks.
        for (j = 0; j < i; j++) {
            
            if (a[i] > a[j]) { // Update rank of a[i]
                curRank++;
            } 
            else { // A number smaller than a[j] has appeared. Update rank of a[j]
                rank[j]++;
            }
        }
      
        rank[i] = curRank;
    }
}

n^2 solution is not acceptible... you can sort yhe array in n*log(n) and assign the rankings in n
n*log(n)+n = n log(n).

looks like they are expecting time n

Perhaps I don't get what it is by mean "ranking". We findMin( ) and the second past divide arr[i] with min and deduct 1 from it so as to have min down to rank 0. It should not be too easy if min is not rank 0. In this case we have to compute GCD of all data in the list which is O(nlogn) and it is O(n) required by the interviewer.

void rank(int *A, int n, int *rank){
    int i;
    int  min = A[0], max = min;
    for(i = 1; i < n; ++i)
    {
        if (A[i] < min)
             min = A[i];
        else if (A[i] > max)
            max = A[i];
    }
 
    // create a counting array, counts, with a member for 
    // each possible discrete value in the input.  
    // initialize all counts to 0.
    int distinct_element_count = max - min + 1;
    int *count = new int[distinct_element_count];
    int *cum = new int[distinct_element_count];  //accumulated sum


    for(i=0; i<distinct_element_count; ++i)
       count[i] = 0;
	for(i = 0; i < n; i++)
       ++count[A[i] - min];
   cum[0] = count[0];
   for(i=1; i<distinct_element_count; ++i)
	   cum[i] = cum[i-1] + count[i];
   
   for(i = 0; i < n; i++) {
	   rank[i] = cum[A[i]-min] - count[A[i]-min];
	   count[A[i]-min]--;
   }
   for(i = 0; i < n; i++) 
	   cout<< rank[i];

}

Maybe the interviewer just had count sort in his head. Provided n is small we can do something similar to count sort to get this ranking done in O(n). If we resort to comparisons then it is impossible to get the ranking in O(n), because if we can rank in O(n) with comparisons then we can as well make another pass on that ranked order and sort the array in O(n), which we all know cannot be true.

Following is the step we can do:

1. Find the maximum element in the array. O(n)
2. Replace array element by subtracting all the element by max. O(n)
3. Make a variable count initialize it with count= N-1.
4. now replace all elements by (count - element). O(n)
5. Finally obtained array gives the rank.

Total time: O(n)+O(n)+O(n)=O(n).

Correct me if wrong....

thanks Jin for correcting :)

Can we just dump the entire list into a hash table O(n)?
I do not see and limitation on using extra space... :)

Input Array arr[6, 3, 9]
Find max element = 9
create another array tarr of size 9 all items initialized to -1;
Take rank counter int count = 0;
for(int i = 0; i < arr.Length; i++)
{
tarr[arr[i]] = count++;
}
for(int i = 0; i < tarr.length; i++)
{
if(tarr[i]!= -1)
{
print(tarr[i]);
}
}

This will print out the ranks.
Complexity O(n)

Input Array arr[6, 3, 9]
Find max element = 9
create another array tarr of size 9 all items initialized to -1;
Take rank counter int count = 0;
for(int i = 0; i < arr.Length; i++)
{
tarr[arr[i]] = count++;
}
for(int i = 0; i < tarr.length; i++)
{
if(tarr[i]!= -1)
{
print(tarr[i]);
}
}

This will print out the ranks.
Complexity O(n)

Input Array arr[6, 3, 9]
Find max element = 9
create another array tarr of size 9 all items initialized to -1;
Take rank counter int count = 0;
for(int i = 0; i < arr.Length; i++)
{
tarr[arr[i]] = count++;
}
for(int i = 0; i < tarr.length; i++)
{
if(tarr[i]!= -1)
{
print(tarr[i]);
}
}

This will print out the ranks.
Complexity O(n)

this is counting sort but instead of putting values in the final array, we would put positions in the intermediate array.

this is counting sort but instead of putting values in the final array, we would put positions in the intermediate array.

Too easy...
Just find the minimum value
int rank[n];
for i=0:n
rank[i] = a[i]-min;

Use "Indirect sort". Have a pointer to each of the elements in the list. Sort the pointers. To get the rank, just scan all the pointers

I have an ideea using hash table:
1) you add all the element in to a hash table.( and keep it sorted)
2) you go trough the table and for each row in the hash table you take the smallest number and the second one. then you go to the next row and until you find an element smaller then the second number you keep moving.

Basically you allways keep in track of the smallest 2 number and you go through the hash table over and over again to find all the element
I realy don't know how to estimate the complexity. O(N * K) where K is the size of the hash table ( that in the case that are all the same number or that all the number has the same module key value)

wouldn't creating a heap work fine? assign parent order+1, +1, +1 to each child in order of greatness and continue. O(n) because each node will only have 2 children, might fail with rep.

Use Order Statistic Tree which is ADT of RB tree.
Complexity to build OS tree is nlogn.
Then rank of each element can be found out in logn time.
So overall runtime in O(nlogn).
In my opinion, it's impossible to do better than that.

public static int[] rankWithoutSort(int[] list)
    {
	int[] rank = new int[list.length];

	for (int i=0;i<list.length;i++)
	{
	    int increment = 0;
	    for (int j=0;j<i;j++)
	    {
		if (list[j] > list[i])
		{
		    rank[j]++;
		    increment++;
		}
	    }
	    
	    rank[i] = i-increment;
	}
	
	return rank;
    }

without sorting, we can use the "tetris"
in every loop, minus 1 for all non-zero element, when ever a new zero appear, add the ranks of all other number by one

heap datastructure

You just have to follow the logic from counting sort

1. Find the maximum element (k) in the array A. O(n)
2. Create an array C[1...k] and initialize it to 0. O(n)
3. For each A(i), set C[A(i)] = C[A(i)] + 1. O(n)
4. For each C(i) {i = 2...k}, C(i) = C(i) + C(i-1). O(n)
5. Create the rank array where R(i) = C[A(i)]. O(n)

Example
A: 3 4 1 5 8 2 9
C: 1 1 1 1 1 0 0 1 1 (from step 3)
C: 1 2 3 4 5 5 5 6 7 (from step 4)
R: 3 4 1 5 6 2 7 (from step 5)

PS: I assumed that the numbers in the array A are unique.

if i have understood the question rightly then O(n) solution is there.
Make BST of the array. It will take O(N)
then traverse it Inorder and give every1 a rank. Again O(N)
now traverse in prefix order and get all the ranks you will get in the order the numbers were set in Array again O(N)

Over all O(N)

Heres what I could put together:



public class Rank {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int A[] = {6,3,7,4,1,0,2,5};
int B[] = new int[A.length];

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

int min = 1000000;
int setValue = 0;

for ( ; setValue < A.length; ) {
min = FindMinValue (A, B, setValue);
System.out.println( " Val: " + min + " " + setValue);

for(int i = 0; i < A.length; i++ ) {
if( (A[i] != min) && (B[i] == setValue) )
B[i]++;

}
setValue++;
}

System.out.println("Print Ranks");
for(int i = 0; i< B.length; i++) {
System.out.print(B[i] + " ");
}
}

private static int FindMinValue(int[] A, int[] B, int setValue) {
int min = 1000;
System.out.print( " Ranks: ");
for(int i = 0; i< A.length; i++) {
System.out.print( " " + B[i] + " ");
if( (min > A[i]) && (B[i] == setValue) )
min = A[i];
}
return min;
}

}