Interview Question: Determine the count of repeating integers within a List

I have been looking for a job change and am in the process of giving interviews. Recently went to a bank for an initial discussion.

The interviewer asked me the following question. Consider that I have a list of integers with the individual values ranging from 0 to 9. The list size is large i.e. in thousands and these individual numbers keep repeating. I want an approach to determine the number of times an individual value is repeated in the list.

After giving some careful thought, I suggested two approaches. One, traverse thru the list and maintain a HashMap with the integer as the key and the count as its value. Alternatively sort the list which would make the counting a simpler process. Both the solutions required traversal and thus did not appear to meet the interviewer’s expectations. He provided me the ‘tip of the day’ by saying that there is a Java Collection to handle this. I did a quick mental refresh but could not pin down the answer. After completion of the interview, out of curiosity I asked him for the solution. He suggested that I do my homework and find the solution and write a blog post about it.

So here I am doing that. After a bit of research, I found the solution in Apache Commons Collections. The class is org.apache.commons.collections.bag.HashBag.

Here’s a sample code which illustrates the point.

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.collections.bag.HashBag;

public class BagTest {

	public static void main(String[] args) {
		List<Integer> values = new ArrayList<Integer>();
		values.add(1);
		values.add(1);
		values.add(12);
		values.add(3);
		values.add(3);
		
		HashBag bag = new HashBag();
		bag.addAll(values);
		
		int count = bag.getCount(1);
		System.out.println(count);
	}
}

I hoping this is the solution. However the point to note here is that the addAll() method internally traverses the list and maintains a Map for storing the key and count. So my solution was not that much different except that I did not know the readily available class. Question here is if this can be considered a valid interview question and secondly is there a way to bypass the list traversal and still solve the problem.

Any thoughts from the developer community are welcome.

Advertisements

4 thoughts on “Interview Question: Determine the count of repeating integers within a List

  1. One other way is to use ‘Set’ in java.
    like:
    Integer[] in = { 1, 2, 4, 5, 6, 4, 6 };
    List integers = Arrays.asList(in);
    Set set = new HashSet(integers);
    System.out.println(“No of repeating integer :” + (integers.size() – set.size()));

  2. The previous commenter was incorrect. The question is the # of times a number is repeated. Note how many were repeated.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s