Find size of ArrayList in minumum steps

This line is just meant to add an ad here. This is link to a product on amazon.in

Hey fellow coders!

I am going to give a solution to a rather simple question which is sometimes asked in software programming interviews.

"There is one class which has private array list and this array list is initialized in constructor of this class.
We have one public method getItem(int i) { ” return ith item of array list” }, We need to know the size of array list. We can only call getItem method."

For more clarity, you can also look at this link: https://ideone.com/VaE0QL

Solution:

Well to solve this problem, we require a little bit knowledge of how an arraylist grows in size.

An arraylist is better for situations where a programmer doesn't know in advance, the number of items he will need to store in an array.

For eg. let's say Adam declared an arraylist of size 5. Now, if he needs to add 4 more elements,

rather than having to declare a new array each time, Adam can simply add new elements to arraylist.

Internally, Arraylist uses array datastructure.

Then how addition happens in ArrayList?

A look at add() method of arraylist tells:

       
public boolean add(E e) {
        ensureCapacity(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}

In add() method, ensureCapacity() method ensures, that array has capacity to store one more element, if not, then it increases capacity of array.

As of Java 7, new capacity is 1.5 times of old capacity on capacity increase,

int newCapacity = oldCapacity + (oldCapacity >> 1);

While creating an arraylist, if size is not specified, java initializes list of default size 10.
So, according to our theory, list size should increase as 10, 15, 22, 33...so on.

Now we have enough info to proceed with algo to find out size of an arraylist in min. number of steps!


Basically, we will begin by checking if requireItem() method gives an exception for index i,

if not then, we will check for index i + 0.5*i.

This way, the first index that gives an exception, will tell us about size of arraylist!!

Do try this algo and post your comments below!