# TOP X numbers

This program reads `a file` which contains one number each line and prints out the `top X numbers` as you wish.

## How to build and run

I use Docker to build and run this little project, so please make sure you have Docker installed.

Then all you need to do are:

```
# Build
docker build -t topx .

# Then quick run with default parameters
docker run -it --rm topx

# Run tests
docker run -it --rm topx sh -c "TOPX=4 go test ./... -v --cover"
```

## Available options for running the program

We use environment variables to override program parameters just for simplicity. You can change the following two environment variables:

- `INPUT ` The relative file path which contains the numbers
- `TOPX` Indicates who many largest numbers you want to pick up.

There are some sample commands below:

```

docker run -it --rm topx sh -c "INPUT=./test1.txt go run main.go"

docker run -it --rm topx sh -c "INPUT=./test1.txt TOPX=1 go run main.go"

docker run -it --rm topx sh -c "TOPX=1 go run main.go"

```

## Complexities

- Space complexity: We only have a heap with size `x` to store the top numbers, and we don't read the entire file into memory , so the space complexity is `O(x)`.

- Time complexity: As we use Priority Heap to store the top `x` numbers, the time complexity for both `Pop` and `Push` are `O(logx)`, and we need to do this for every number, given we have `n` numbers in total. So the complexity of finding top x numbers is `O(nlogx)`, and lastly we do another sorting for the top `x` numbers to make sure numbers are following the descending order, which the time complexity is `O(logx)` as well. So the total time complexity should still be `O(nlogx)`

## Future improvements

- Refactor the `calculator.CalculateLargestNumbers` function to extract file reading, so that this function doesn't need to reply on a actual file in unit and can be tested better, and even to be mocked out when unit testing.
- Still in the `calculator.CalculateLargestNumbers` function, it would be better to just call `heap.Init()` once no matter how many top numbers we need to fetch.
- Allow program to parse options for parameters, such as `./app -input x.txt -topx 5`
- Add benchmark tests to reveal the actual performance of this program, and improve the program from there.
- Better error handling. Such as custom error types, more specific error messages and so on.