CareerCup

This is likely a question they want you to answer multiple ways. With questions like this, it's perfectly fine to start off with a naive approach and work your way to something they are looking for.

I will discuss some ways to answer this:

Time: O(n^2) Space: Constant - Go through number by number starting at index 0 comparing if they are the same, if they are the same increase the count. If the count is above 3 at the end print that number and move onto the next index.

Time O(nlogn / n^2) space: depends - You can sort the array, and once it's sorted you can do this in N (as a number appearing more than 3 times would be like this 1,2,3,3,3,3,4 etc.). The reason space depends and time is unsure because it depends how you sort the array.

Time O(n) space: maximum size of input integer - You can make an array of ints that stores the counts of each occurence. So in your first pass through, you are increasing the count of countarray[i] where i is the number in your input array. At any point if your count increases past threshold you output right there. If you use a hash table, you can preserve space.

As far as bitwise operations go, I am not sure how they help you.

This is acouple ways to solve, hope this helps.

O(n) time and O(n) space

public static void printMoreThanK(int[] data, int k) {
		HashMap<Integer, Integer> map =
			new HashMap<Integer, Integer>();
		for (int i : data)
			if (map.containsKey(i))
				map.put(i, map.get(i)+1);
			else map.put(i, 1);
		for (int i : map.keySet())
			if (map.get(i)>=k)
				System.out.println(i);
	}

Why cant you just go through array and store it in HashMap. Where each element is key and count is the value. When you add value to Hashmap after adding value check if the count >= freq if it is print it out. And these way the biggest number doesn't even matter.
Complexity - O(n)
Space- O(n)

Build a heap tree, wherein the elements are inserted in terms of their occurence

can't we sort it and do?sort - O(nlogn) and then check from i=0 to n a[i] and a[i+k] if both equal then a[i] is the number.

The solution above is correct, however, i've written it little more completely (in java as well) accounting for base cases, etc.

//Solution below: 
//Running Time: O(a + hm)
//Space: O(a + hm) worst case
public ArrayList<Integer> findKRepeated(ArrayList<Integer> a, int k){
    if(a.size() < 1) return null;
    if(a.size() == 1){
        if(k == 1) return a;
        return null;
    }
    ArrayList<Integer> retList = new ArrayList<Integer>();
    HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    for(int i : a){ //create a hashmap of numbers as key and their appearances as values
        if(hm.containsKey(i)){
            int value = hm.get(i);
            value++;
            hm.put(i, value);
            continue;
        }
        hm.put(i, 1);
    }
    for(int j : hm){  //iterate hashmap to find all number appearing 3 or more times
        if(hm.get(j) >= 3) //in this case, k is hard coded to 3
            retList.add(j);
    }
    return retList;//list of all integers repeated more than 2 times
}