Print limited previous lines from a file

Question

This is a question from careercup.com. Given a word w and a number k.Find k words in the file occurring before occurrence of w.Assume that the average word size is m in the file eg. aaa bbb ccc booking alpha beta gamma

for k=3 and w = booking the output should be [aaa,bbb,ccc,booking] similarly for k =2 and w = beta output should be [booking,alpha,beta] Assume that the file size can grow very large and try to get solution with space complexity lesser than O(n)

package com.careercup;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class LimitedLengthQueue {

    private List<String> innerStore;
    private int size;   
    private static final String FILENAME="C:/filepath.txt.txt";
    public LimitedLengthQueue(int size) {       
        this.innerStore = new ArrayList<>();
        this.size = size;
    }

    boolean add(String s){
        if(innerStore.size() == size){
            innerStore.remove(0);
            innerStore.add(s);
            return true;
        }
        innerStore.add(s);
        return true;
    }


    public static void main(String[] args) throws FileNotFoundException, IOException  {
        LimitedLengthQueue inputQueue = new LimitedLengthQueue(Integer.parseInt(args[0]));
        String key = args[1];   

        try( FileReader fr = new FileReader(FILENAME);
             BufferedReader br = new BufferedReader(fr)){

            String input = null; 

            while( (input = br.readLine()) != null){

                if(key.equals(input.trim())){
                    inputQueue.innerStore.forEach(System.out::println);
                    System.out.println(input);
                    break;
                }
                inputQueue.add(input);
             }
        }
    }   
}

Answer 1

    private int size;

I would find this more consistent with other Java classes if it called this capacity rather than size.

    private int capacity;

The size is typically the number of elements currently in the data structure.

        this.innerStore = new ArrayList<>();

This could be

        innerStore = new ArrayList<>(capacity);

While you can use the this. there (perhaps to make it obvious that it is a field), you don't need to do so as it is not ambiguous as to which innerStore is involved.

Passing the capacity (or size) initially tells it how big the structure will grow. This saves having to do multiple allocations.

You could also do some extra work and use an array here. Of course, with an array, you have to manually keep track of where you are in the array. For a queue, you would normally use the array in circular fashion, overwriting the oldest entry and returning to the beginning after reaching the end.

    boolean add(String s){
        if(innerStore.size() == size){
            innerStore.remove(0);
            innerStore.add(s);
            return true;
        }
        innerStore.add(s);
        return true;
    }

This could be just

    boolean add(String s) {
        while (innerStore.size() >= capacity) {
            innerStore.remove(0);
        }

        return innerStore.add(s);
    }

The other way, if you passed the maximum capacity, it would stop enforcing it.

You don't need to add and return twice. Once is plenty.

You shouldn't always return true. If the internal add fails, you should return false. Returning the result of the internal add accomplishes this exactly.

Answer 2

Data structure:

First of all, choosing an ArrayList as the data structure for a queue is suboptimal to say the least. A remove(0) on an ArrayList always copies the remaining elements to the beginning of the list (see remove implementation in ArrayList - sources are available). Use a LinkedList instead, which has constant removal time.

New Files-API:

Usage of try-with-resources is good, but manually creating a FileReader and a BufferedReader is quite old-fashioned. Simply use java.nio.Files.newBufferedReader instead.

Method signature:

Your LimitedLengthQueue.add method has a boolean return which is always true and never queried. What for? If you don't care, simply make the method void.