Zynga Interview Question
AnalystsCountry: United States
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);
}
Traversing over a Hash Map is not N. It's however big the hashmap is. You don't need the second for loop anyways, when you are incrementing your value in map, you can immediately check if it is past your k threshold.
I agree on the second part, but traversing over the map is N (we are stepping through every value in the original array; there are duplicates but it's still O(n) )
Plus, we can check the threshold in the first loop but we would have somehow to keep track of elements that we have printed already
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)
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
}
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.
- Dan February 15, 2013I 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.