"Fibonacci overlap and stats" - Java / Python / C++

Your solution will be scored against some number of hidden test cases. A sample is provided below.

The test cases focus only on correctness. You will be tested on malformed input as specified in the spec below. In addition, ensure you deal with edge cases correctly.

Time and space complexity optimizations are a nice bonus but secondary in grading the assignment. Feel free to improve on time and space complexity only if you have time left over.

Write a program in Java, Python, or C++ which has the following functions:

(1) "fibonacci" - Takes as argument a single non-zero, positive integer and prints the fibonacci series up to the highest fibonacci number that is smaller or equal to the input

argument. The output should be in ascending order with a single space character separating each integer.

Eg: If "15" is the input argument, the output would be "0 1 1 2 3 5 8 13". "15" is not a fibonacci number so we print up to the highest fibonacci number that is less than or equal

to "15"; in this case that is "13".

Eg: If "21" is the input argument, the output would be "0 1 1 2 3 5 8 13 21". "21" is a fibonacci number, so we print all the fibonacci numbers up to and including "21".

Eg: If "1" is the input argument, the output would be "0 1 1".

If the input argument is anything other than a positive, non-zero integer, you must print the string "error".

Eg: If "-6" is the input argument, output must be "error".

Eg: If "helloworld" is the input argument, output must be "error"

Eg: If "0" is the input argument, the output must be "error".

(2) "overlap" - Takes as argument a list of ranges and determines whether any two ranges overlap. If there is any overlap, it prints "true", otherwise it prints "false".

A range is given in the form "a,b", where a and b are both integers and where a <= b. Note that a and b can be negative, zero or positive. A list of ranges is a sequence of

ranges separated by a single space character (" "): "a,b x,y j,k". Two ranges overlap if they partially, or fully cover the same set of integers. For example: "3,6" and "5,9"

overlap because they both include 5 and 6. Similarly, "8,176" and "6,11" also overlap because they both include 8, 9, 10 and 11. On the other hand, "17,17" and "-5,4" do not

overlap because they do not share any integers.

If you encounter a malformed range, you must print "error". A malformed range, "a,b", is one where either a or b are not integers or where a > b.

For example, the following ranges are all malformed "17,4", "-1,-5", "five,9", "1,$*$", "hello,world".

The "overlap" function is guaranteed to be given a list of at least two intervals, therefore you need not worry about an empty list or a single

range as arguments.

Eg: Given "17,200 1,2 17,17 8,9" as input, the function would print "true" because "17,200" and "17,17" overlap.

Eg: Given "8,99 4,7 1,3" as input, the function would print "false" because no ranges overlap.

Eg: Given "4,8 dd,5" as input, the function would print "error" because "dd,5" is a malformed range.

(3) "stats" - Takes no arguments and prints the number of calls to "fibonacci" and "overlap" (in that order) as two integers, on a single line, separated by a single space

character (" ").

Eg: If "fibonacci" is called three times, and "overlap" is called twice, the output should be "3 2"

The input to your program will be given on stdin and will consist of one function call per line. Each line starts with a string ("fibonacci",

"overlap" or "stats"), indicating which function is being called. Following the function name, there will be a single space character (" "),

after which the input to the function (if any) is presented. If "stats" is called, it will always be the last function call.

-----------------------

Sample input:

fibonacci 21

overlap 8,99 4,7 1,3

fibonacci 0

fibonacci 15

overlap 1,3 10,17 -10,0 2,4

stats

Sample output:

0 1 1 2 3 5 8 13 21

false

error

0 1 1 2 3 5 8 13

true

3 2

-----------------------

Input & output explanation:

- Call "fibonacci" with "21" as the argument. The highest fibonacci number that is less than or equal to the input argument is "21" so we print all fibonacci numbers up to and

including "21".

- Call "overlap" with "8,99 4,7 1,3" as the argument. All ranges are wellformed but none overlap, so we print "false".

- Call "fibonacci" with "0" as the argument. Calling "fibonacci" with "0" as the argument should print "error" as detailed in the spec.

- Call "fibonacci" with "15" as the argument. The highest fibonacci number that is less than or equal to the input argument is "13" so we print all fibonacci numbers up to and

including "13".

- Call "overlap" with "1,3 10,17 -10,0 2,4" as the argument. All ranges are wellformed and "1,3" and "2,4" overlap so we print "true".

- Call "stats". "fibonacci" was called three times and "overlap" was called twice, so we print "3 2".

---------------------

Sample input:

bonacci 34 overlap 8,8 10,19 7,7 10,19 overlap -1,0 10,12 1,8 9,15 fibonacci 42 overlap -1,0 50,60 -5,-3 55,59 fibonacci 0 overlap 89,94 54,59 0,0 77,89 -1,9 overlap -1,-1 11,19 -11,-5 19,20 fibonacci -1 stats

sample output:

0 1 1 2 3 5 8 13 21 34 true true 0 1 1 2 3 5 8 13 21 34 true error true true error 4 5