CareerCup

use a PriorityQueue with greater predicate, here is the example in C++

class AddGetDS{
    
private:
    priority_queue<int,vector<int>,greater<int>> myQueue;
    
public:
    void add(int x){myQueue.push(x);}
    int getmin(){return myQueue.top();}
    
};

public class FindRep {
    
   public static void main(String[] args){
    
       int[] arr = {1,3,1,4,5,6,7,8,2,9};
       FindRep rep = new FindRep();
       System.out.println(rep.FindRepNum(arr));
       
   }
   
   public int FindRepNum(int[] arr1){
       
       HashSet myset = new HashSet();
       
       for(int i: arr1){
           
           if(myset.contains(i)){
               return i;
           }else{
               myset.add(i);
           }
       }
      return -1; 
   }
    
}

//Quick Sort gives you O(n log n)
public class QuickSort {
    int ArrLength;
    int[] arr = {9,6,3,7,2,1,8,10,5,4}; 
    static int count = 0;
     
    private void sort(int[] arr){
        if(arr == null || arr.length == 0){
            return;
        }
        ArrLength = arr.length;
        quicksortAlgo(0,ArrLength-1);

    }
    
    private void quicksortAlgo(int low, int high){
        
        int i = low;
        int j = high;        
        int pivot = ComputePivot(low, high);
        
        count++;
        
        while(arr[i] < arr[pivot]){
            i++;
        }
        
        while(arr[j] > arr[pivot]){
            j--;
        }
        
        if(i<=j){
           swap(i,j); 
           i++;
           j--;
        }
        
        if(i<high){
            quicksortAlgo(i, high);
        }
        
        if(j>low){
            quicksortAlgo(low, j);
        }
         
    }
    
    private int ComputePivot(int low, int high){
        
        return (new Random().nextInt(high - low +1) + low);
     
    }
    
    private void swap(int i, int j){
        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    } 
    
}