Google Interview

IntegerSummary.java

import java.util.*;

// complexity = O(N)
public class IntegerSummary{
	public static void main(String [] args){
		Integer [] array = {3, 5, 8, 23, 88, 99};
		System.out.println(getSummary(array));
	}

	public static String getSummary(Integer [] numbers){
		Set <Integer> integers = new HashSet <Integer>(Arrays.asList(numbers));
		
		List <Integer> missingNumbers = new ArrayList <Integer>();

		for(int i = 1; i <= 99; i++){
			if(! integers.contains(i)){
				missingNumbers.add(i);
			}
		}

		if(missingNumbers.size() == 99){
			return "1-99";
		}

		List <String> results = new ArrayList <String>();
		
		for(int i = 0; i < missingNumbers.size()-1; i++){
			int currentIndex = i;
			int loop = 0;
			
			while(currentIndex + loop < missingNumbers.size()-1){
				int current = missingNumbers.get(i + loop);
				int next = missingNumbers.get(i + loop + 1);
				int diff = next - current;
				if(diff != 1){
					break;
				}
				loop += 1;
			}
			int boundary = currentIndex + loop;
			String range = "";
			if(currentIndex == boundary){
				range += missingNumbers.get(currentIndex);
			}
			else{
				range = missingNumbers.get(currentIndex) + "-" + missingNumbers.get(boundary);
			}
			results.add(range);
			i += loop; // This what makes O(N)
		}

		String output = "";
		for(String s : results){
			output += s + ",";
		}
		return output.substring(0, output.length() - 1);
	}
}