Print the Last N Lines (tail)
Problem
The first line is a number N. All other lines are the text of a file. Print the last N lines of the file, in the original order (like the tail command). If the file has fewer than N lines, print all lines. If N is 0, print (nothing). Keep only N lines in memory at any time, because real files can be huge.
Constraints
- 0 <= N <= 10^4
- 1 <= lines <= 10^5
Examples
Input
2 a b c
Output
b c
Solutions
Reading the whole file and slicing the end works for small files, but it needs memory for every line. A window of N lines needs only O(N) memory, however long the file is. This is the idea behind tail -n and log viewers.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : The last N lines.
* Approach: A number, then the file.
* Time : O(L)
* Space : O(N)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
int count = Integer.parseInt(lines[0].trim());
if (count == 0) {
return new String[] {"(nothing)"};
}
// Step 1: A deque works as a window of the last N lines. New lines go in at the back.
java.util.ArrayDeque<String> window = new java.util.ArrayDeque<>();
for (int i = 1; i < lines.length; i++) {
window.addLast(lines[i]);
// Step 2: When the window is too big, remove the oldest line at the front.
if (window.size() > count) {
window.removeFirst();
}
}
return window.toArray(new String[0]);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (1)
- How much memory does the window need for a file of a million lines and N = 10?