CareerCup

If this was the complete interview question, I would follow up with several clarifying questions to ensure you are on target (and to display that you have the aptitude for developing requirements that your client might not even understand they need).

Q1: Is the file sorted?
Q2: What are the memory constraints? (can we load the entire file to memory, or must we work with the stream)
Q3: Are we finding just the 2 largest, or the Nth largest?

For the sake of my answer, I will assume the file is unsorted, the file is too large to load into memory, and that we are seeking the Nth largest. In this instance, you would establish a file input stream using your chosen programming language, and then parse the input one number at a time. You also declare a linked list to keep track of your Nth largest items in sorted order. Each time you evaluate a number you compare it to the smallest element in your list (the first element). If it is larger, you add to the correct spot in the list to maintain sorted order. If the list size is larger than Nth larger elements, you delete the smallest node.

This algorithm will give you O(n) worst case running time. For the worst case, your file would be sorted ascending and you would have to add every element to your list which requires N*K elements operations, which truncates to O(n). The space complexity is O(N) as you only allocate memory in proportion to the number of elements you want to find.

public LinkList findNthLargestFromFile(InputStream in, int n){
	LinkList list = new LinkList();
	int temp;
	
	while(in.hasNext()){
		temp = in.getNextInt();
		if(temp > list.getFirst() || list.size() < n){
			list.add(temp);
			list.sort();
			if(list.size() > n){
				list.deleteFirst();
			}
		}
	}
	return list;
}

I have written a code to find the first highest and second highest from a file .
1) For better optimization instead of reading character by character , I read the whole line as a string using BufferedReader , and then split the sting and find the first and second higest.
This same program can be modified to find the nth highest/smallest
*** instead of putting them in a string [] - we can put them in an ArrayList and then use the Collections.sort and then find the nth higest or smallest by the array index .

#######################################################################
package com.CareerCup;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;


public class FirstAndSecondLargest {

public static void main(String str[])
{
FileReader fileReader=null;
BufferedReader buffReader=null;
boolean initializeOnlyOnce=true;
int firstLarge=0;
int secLarge=0;
int nextNumberInFile=0;
StringBuilder integersInFile = new StringBuilder();
File file = new File("c:\\TestFile.txt");
try {
fileReader= new FileReader(file);
buffReader = new BufferedReader(fileReader);
String strr=null;

while ( (strr=buffReader.readLine() )!= null)
{
integersInFile.append(strr) ;
}
String resultStr[] = integersInFile.toString().split("\\s+");

firstLarge=Integer.parseInt(resultStr[0]);
secLarge = Integer.parseInt(resultStr[1]);

int len= resultStr.length;

for(int i=1; i<len;i++)
{
int nextNumber = Integer.parseInt(resultStr[i]);

if( nextNumber > firstLarge)
{
secLarge= firstLarge;
firstLarge = nextNumber;
}
else if(secLarge < nextNumber && (secLarge < firstLarge))
{
secLarge = nextNumber;
}

}

System.out.println("first larget ="+firstLarge+"second largest "+secLarge);


}

catch (Exception ex) {
ex.printStackTrace(System.out);

}
finally
{
try {
fileReader.close();
buffReader.close();

} catch (Exception ex) {

}

}

}


}

Maintain a heap of N elements, and each next item read from the file, push into the heap. If you maintain a max heap, then highest element in file will be at the top and last element in the heap will be the Nth largest element of the file.