Climbing the Leaderboard

I was going to say “What a week” but today is Sunday and in some calendars, the week starts today so technically last week is over.

Last Monday and Tuesday I had to deal with a water leakage issue generated by a new water meter installed by the city a couple weeks ago.

On Wednesday, our SUV popped the two right side tires in a set of potholes covered with water as I was entering Cedar Avenue also known as 77, on my way home from having an oil service at the dealership.

The worse thing happened to my wife starting Tuesday. Both heart pressures (systolic and diastolic) were dangerously low. After a battery of tests the culprit was low hemoglobin count which seems to be something women tend to experience more often than men. My wife ended up being hospitalized to receive emergency medical care, find the issue and obviously resolve it. Hopefully all will be done later today. I have been back and forth to Regions Hospital a dozen or more times. “What a seven day span”.

Earlier today I worked on the HakerRank challenge “Climbing the Leaderboard”. As is with most challenges, this was an interesting one.

The idea for the challenge is based on dense ranking. In a nutshell, when you have a set of rankings, multiple values may repeat. Such values share the same ranking. For example if you have 517 integer rankings in the range [0:100] some of them would be duplicated. All the duplicate values would share the same ranking.

To address the duplicate values I initially went the TreeMap class in Java. My code passed the sample tests. All seemed to be going well. When I submitted the solution, four test cases (6, 7, 8 and 9) timed out. I spent some time attempting to optimize the code at no avail.

I then did some research and decided to go with the IntStream class.

My code for the climbingLeaderboard() function follows:

   static int[] climbingLeaderboard(int[] scores, int[] alice) {

    	int count = alice.length;
    	
//    	System.out.println("count: " + count);

    	int[] rank 					= new int[count];

//    	TreeMap<Integer, Integer> map 	= new TreeMap<Integer, Integer>();
//
//    	// **** populate the tree with the scores ****
//    	for (int s : scores) {
//    		if (map.containsKey(s)){
//    			map.put(s, map.get(s) + 1);
//    		} else {
//    			map.put(s, 1);
//    		}
//    	}

//    	System.out.println("map: " + map.toString() + "\n");
    	
    	// **** remove duplicates and sort scores ****
    	scores = IntStream.of(scores).distinct().sorted().toArray();
//    	displayArray(scores);
    	
//    	alice = IntStream.of(alice).sorted().toArray();
//    	displayArray(alice);

    	
    	// **** loop adding Alice's scores to the tree and computing her rank ****
    	for (int i = 0; i < alice.length; i++) {
    		
//    		System.out.println("alice[i]: " + alice[i]);
    		
    		int j = Arrays.binarySearch(scores, alice[i]);
    		
//    		System.out.println("j: " + j);
    		
    		// **** ****
    		if (j < 0)
    			rank[i] = scores.length - Math.abs(j) + 2;
    		else
    			rank[i] = scores.length - j;
    		
//			System.out.println("rank[" + i + "]: " + rank[i]);
    	}

    	
//    	// **** loop adding Alice's scores to the tree and computing her rank ****
//    	int i = 0;						// rank index
//	   	int j = 0;						// map index
//    	for (int a : alice) {
//    		
////    		System.out.println("a: " + a);
//    		
//    		// **** add Alice's score to the map ****
//    		if (map.containsKey(a)) {
//    			map.put(a, map.get(a) + 1);
//    		} else {
//    			map.put(a, 1);
//    		}
//    		
////    	   	System.out.println("                map: " + map.toString());  
////    		System.out.println("map.entrySet().size: " + map.entrySet().size());
//
//    		// **** determine and save Alice's rank at this time ****
//    	  	for ( ; j < map.entrySet().size(); j++) {
//    	  		
//    	  		// **** get the grade at this index ****
//    	  		int g = (int)map.keySet().toArray()[j];
//    	  		
////    	  		System.out.println("g[" + j + "]: " + g);
//    	  		
//    	  		// **** if Alice's grade matches; then compute and save this rank ****
//    	  		if (a == g) {
//    	  			
//    	  			// **** compute and save Alice's rank ****
//    	  			rank[i] = map.size() - j;
//    	  			
////    	  			System.out.println("rank[" + i + "]: " + rank[i]);
//    	  			
//    	  			// **** increment indices ****
//    	  			i++;
//    	  			j++;
//    	  			break;
//    	  		} 
//    	  	}
//    	}

    	
    	// **** return Alice's rankings ****
    	return rank;
    }

The code is somewhat messy due to the fact that I decided to leave commented out what I wrote using the TreeMap class.

The output for the test cases follows:

7
100 100 50 40 40 20 10
4
5 25 50 120

6
4
2
1


6
100 90 90 80 75 60
5
50 65 77 90 102

6
5
4
2
1

If you are interested, my entire solution, which I wrote using the Eclipse IDE is in my GitHub repository.

Keep on reading and experimenting; it is the only way to learn.

If you have comments or questions regarding this or any other post in this blog, or if you wish to contact me regarding software development projects, please leave me a note bellow. The note will remain private.

Regards;

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.