Problem #1:  

A stream of arbitrary integers appears in no particular order and without duplicates 

 the rank of each integer is determined by the number of smaller integers before and after it up to the current position 

 Write a method to get the rank of the current integer in an efficient way. 

 eg: 7, 1, 3, 9, 5, 8 

 

Solution:  

A max heap is used to keep track of the elements we have seen and to count those that are smaller 

 

using System; 

using System.Collections.Generic; 

using System.Linq; 

 

public class Test 

{ 

private static SortedList<int, int> itemRankPair = new SortedList<int, int>(); 

public static void Main() 

{ 

     var items = new List<int>(){7, 1, 3, 9, 5, 8}; 

      

     for (int i = 0; i < items.Count; i++) 

     { 

              var item = items[i]; 

              Console.WriteLine("Item={0}", item); 

              if (itemRankPair.ContainsKey(item) == false) 

              { 

                  itemRankPair.Add(item, GetRank(item)); 

              } 

              Console.WriteLine(); 

              for (int j = 0; j < i; j++) 

              { 

                  int k = items[j]; 

                  if (k >= item) 

                  { 

                            itemRankPair[k] += 1; 

                             

                            Console.WriteLine("item={0}, Rank={1}", k, itemRankPair[k]); 

                  } 

              } 

              Console.WriteLine(); 

     } 

     foreach (var k in itemRankPair.Keys.ToList()){ 

Console.WriteLine("item={0}, Rank={1}", k, itemRankPair[k]); 

     } 

} 

 

private static int GetRank(int n) 

{ 

int rank = 0; 

foreach( var key in itemRankPair.Keys.ToList()) 

{ 

if (key < n) 

{ 

    rank++;            

} 

} 

return rank; 

} 

 

}