Question

Java Problem: Please answer both parts of the question fully:

(a). Write Java code for a method to test if a LinkedList<Long> has Long values that form a Fibonacci sequence from the beginning to the end and return true if it is and false otherwise. A sequence of values is Fibonnaci if every third value is equal to sum of the previous two. Eg., 3,4,7,11,18,29 is a Fibonacci sequence whereas 1,2,3,4 is not, because 2+3 is not equal to 4. Any sequence containing only two values is Fibonacci. If the list has <=1 value, then it is NOT Fibonacci. Make sure to test the code for correctness before submission and you don’t need to submit test results.

public boolean isFibonacci(LinkedList<Long> li) {

//

}
Estimate in big-oh notation the run-time complexity of the method as a function of the size of the list n.

(b). Write Java code for extending the ArrayList<E> class of java.util.* to ExtArraayList<E> that includes the following one method:

public boolean equals(ExtArrayList<E> eal)

// returns true if the values in this list is the same as in eal. For instance, if E is Integer and this has {2,1,3,1,6} and eal has {1,2,3,1,6} then you should return true. If eal has {1,2,3,6}, you should return false. Clearly the size of each should be the same but obviously there is more to it than that. You can assume the existence of equals()method for testing equality of E. Do not use specific types like String or Integer. Estimate the run-time complexity of the methods assuming the size of the list is n.

Answer 1

(a)

/* method to test if a LinkedList<Long> has Long values that form a Fibonacci sequence from the beginning to the end and return true if it is and false otherwise.*/

public boolean isFibonacci(LinkedList<Long> li) {

       // check if size is atleast 2   

if(li.size() >= 2)

             {

                    // get the first 2 values of the linked list

                    long f1 = li.get(0);

                    long f2 = li.get(1);

                    /* loop over the linked list, starting from index 2

                    and check if this element is sum of the previous 2, if not return false, else assign 2^nd element to 1^st element and assign the current element to 2^nd element*/

                    for(int i=2;i<li.size();i++)

                    {

                           if(li.get(i) != (f2+f1))

                                 return false;

                           f1= f2;

                           f2 = li.get(i);

                    }

                   

                    return true;

             }

            

             return false;

}

//end of method

The time complexity of the method is O(n) since the for loop runs for a maximum of n times, where n is the size of the linked list. The worst time complexity will be of O(n).

(b)

public class ExtArrayList<E> extends ArrayList<E> {

             

       // returns true if the values in this list is the same as in eal

public boolean equals(ExtArrayList<E> eal)

       {

             // check if size is same

             if(size() == eal.size())

             {

                    int count1, count2;

                    // loop over the calling ArrayList

                    for(int i=0;i<size();i++)

                    {

                           count1 = 0;

                           count2 = 0;

             // loop to count the number of times ith element occurs in this list

                           for(int j=0;j<size();j++)

                                 if(get(i).equals(get(j)))

                                        count1++;

       // loop to count the number of times ith element occurs in this passed list

                           for(int j=0;j<eal.size();j++)

                                 if(get(i).equals(eal.get(j)))

                                        count2++;

       // check if both counts are same or not, if not then return false              

                           if(count1 != count2)

                                 return false;

                    }

                   

                    return true;

             }

            

             return false; // if size is not the same

       }

}

The time complexity of the method is O(n²) because the outer loop runs n times, where n is the size of the list and to count the number of times each element occurs in both lists, the for loop runs n times. So the inner loop also runs for n times giving the complexity of O(n²)