CareerCup

public boolean isSimilarArrays(int aArr[], int bArr[]){
		int lenA = aArr.length;
		int lenB = bArr.length;
		if( lenA != lenB )
			return false;
		int result = 0,zeroA = 0,zeroB = 0;
		while( --lenA >= 0 ){						//	O(n) Solution
			if( aArr[lenA] == 0 ){					//	Count Zero's in A
				zeroA++;
				continue;
			}
			if( bArr[lenA] == 0 ){					//	Count Zero's in B
				zeroB++;
				continue;
			}
			result ^= aArr[lenA] ^ bArr[lenA];		//	XOR numbers so that replica can be confirmed
		}
		if( zeroA != zeroB )						//	if zeros match we are fine else boom wrong!!!
			return false;
		else
			return result == 0 ? true : false;		//	finally if XOR works 0 is the result else not similar
	}

// from an array build max Heap
// here array is A, mSize is size of array
// and finally return the top element of the heap by taking out k-1 max elements out of heap

// Main Program

MyHeap maxHeap = new MyHeap(A);
		maxHeap.buildHeap();
		for(int i=0;i<k-1;i++)
			maxHeap.removeTop();

maxHeap.getPriorityElement(); // required result

public MyHeap(ArrayList<Integer> arr){
		mArrList = arr;	
		mSize = arr.size();
	}

public void buildHeap(){		 O(n)
		for( int i=mSize/2-1; i>=0; i-- ){
			max_heapify(i);
		}
	}

private boolean max_heapify(int pos){
		int sPos = getMaxOfTwoChild(pos);
		if( pos > mSize || sPos == -1 )
			return true;		
		if( mArrList.get(pos-1) < mArrList.get(sPos-1) ){
			swap(pos-1,sPos-1);
			return max_heapify(sPos);
		}		
		else
			return true;
	}

private int getMaxOfTwoChild(int pos) {
		int left = leftOf(pos);
		int right = rightOf(pos);
		if( left <= mSize && right <= mSize && left > 0 ){
			return mArrList.get(left-1) > mArrList.get(right-1) ? left : right;
		}
		else if( left <= mSize && right > mSize )
			return left;
		else if ( right <= mSize && left > mSize )
			return right;
		return -1;
	}

public int removeTop(){                       //        O(k * logn)
		int top = getPriorityElement();
		if( top != -1 ){
			swap(0,mSize-1);
			mArrList.remove(--mSize);
			max_heapify(1);
		}
		return top;
	}

public int getPriorityElement(){
		if( mSize > 0 )
			return mArrList.get(0);
		else return -1;
	}

private int leftOf(int pos){
		return 2*pos;
	}
	
	private int rightOf(int pos){
		return 2*pos+1;
	}

// total complexity of program = O(n) + O(k * logn )