Array

Question 1

Find majority element in array

Answer 1

Use Moore Voting algo. Also can use Binary searh tree

public class Solution{
	public int majorityElement(final int[] A) {
		int count = 0;
		int maj_element = 0;
		for(int i = 0; i < A.length; i++){
			if(count == 0)
				maj_element = A[i];
			if(A[i] == maj_element)
				count++;
			else
				count--;
		}
		count = 0;
		for(int i = 0; i < A.length; i++){
			if(A[i] == maj_element)
				count++;
			if(count > A.length/2)
				return maj_element;
		}
		return -1;
	}
}

Question 2

Find median of sorted array of equal size

Answer 2

Base case:

1. n=2, then median is (max(a1,b1) + min(a2,b2))/2
2. if n > 2 and m1 == m2, median is m1

based on m1 < m2 or m2 < m1 , change the start and end indices and recurse

Question 3

Find first and last occurence of number in sorted array with duplicates

Answer 3

if we want in O(n) time, then we parse and keep tab of first and last occurence

if we want in O(log n) time then we do modified binary search.
for last occurence if number is found in mid, then ensure that a[mid+1] is greater than number

Question 4

Finding missing element or non duplicate element in an array

Answer 4

when the two input arrays are off by just one element which needs to be found, consider XOR operations
XOR : if there is a difference, output is 1
if there is no difference, output in 0

Question 5

max square formed from a matrix of 1’s and 0’s

Answer 5

dynamic progr

derive it from the min of left, top and left top diagonal

Question 6

Find the ‘n’th most frequent number in array

Answer 6

revisit this question