Created
February 4, 2014 20:30
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
10 | |
1 | |
8 | |
-20 | |
4 | |
2 | |
79 | |
123123 | |
8 | |
9 | |
22 | |
24 | |
3 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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