Skip to content

Instantly share code, notes, and snippets.

@yekmer
Created February 4, 2014 20:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yekmer/8811733 to your computer and use it in GitHub Desktop.
Save yekmer/8811733 to your computer and use it in GitHub Desktop.
Write a program, topN, that given an arbitrarily large file and a number, N, containing individual numbers on each line (e.g. 200Gb file), will output the largest N numbers, highest first. Tell me about the run time/space complexity of it, and whether you think there's room for improvement in your approach.
10
1
8
-20
4
2
79
123123
8
9
22
24
3
package com.yekmer.interview.intercom;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.PriorityQueue;
import java.util.Stack;
public class TopNumbers {
public static void main(String[] args) {
int N = 5;
topN("input_file", N);
}
//Assume file is one integer by one row
public static void topN(String fileName, int N) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(N);
Stack<Integer> resultStack = new Stack<Integer>();
BufferedReader bufferedReader = null;
try {
bufferedReader = new BufferedReader(new FileReader(fileName));
//reading line by line will not fill memory
String line = bufferedReader.readLine();
while (line != null) {
try {
int mInt = Integer.valueOf(line);
priorityQueue.add(mInt);
if(priorityQueue.size() > N) {
priorityQueue.remove();
}
} catch (NumberFormatException e) {
System.out.println("Continues if there is a non int row");
}
line = bufferedReader.readLine();
}
for(int i = 0; i < N; i++) {
resultStack.add(priorityQueue.remove());
}
//we can handle different type of exceptions here, it will be faster to execute
} catch(Exception ex) {
System.out.println("There is an error, program exits");
} finally {
try {
bufferedReader.close();
} catch (Exception e) {
System.out.println("Error while closing reader");
}
}
for(int i = 0; i < N; i++) {
System.out.println(resultStack.pop());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment