Java interview for developer. Collections. Part 1

About a year ago I've started searching new job and have to visit lots of interviews. I was looking for Java developer work, so most questions were related to the Java language and JVM. The most popular questions were related to Java collections. It was lucky for me that I have finished the Coursera course about algorithms by R.Sedgewick (by the way best material I ever heard or read on theme of classical algorithms and data structures) and it was related to Java collections. Without it, I suppose I will not show such solid knowledge of this area of Java. But nevertheless, I meet some really hard questions. After all this interviews I made an article in Russian about interview questions on Java collections (you can read it here). Now I try to tell its content in English to make it available to English speaking readers. So let start.

1. What is the difference between ArrayList and LinkedList?

I suppose this most popular question, that you can hear in interviews. Some years ago, on my first Java interview, such question caused a lot of problems for me that day, cause I was not sure about the internal logic of this data structure, it was funny.

In short the answer should looks like this: ArrayList - its the list that implemented on classic Java array, LinkedList - list that implemented on objects with links pointed on other element(s) of list, in other words it is classic linked list that we read about in canonical books on data structures.

Let's go deeper.

Pros of ArrayList: ability to access a random elemnet of a list for a constant time by index(cause it is an array), it consumes minimum memory and IN AVERAGE it is required constant time to insert element at the end of the list. I write IN AVERAGE, cause array at creation have some fixed size (in code, you can find it as capacity parameter), be default init size is n=10 elements. When you try to add a new n+1 element, a new array will be created with size (n * 3) / 2 + 1, all elements from old array will be copied to this new array and new n+1 element will be inserted. So we have that the most element are just placed in ready cell in array (it will require constant time), but from time to time array should be resized(it will, of course not constant time, it will depend on n - size of old array), but on average we can consider time for insertion as constant. Last element removing also will be performed in constant time. Internally this operation just clear value of last cell.

Cons of ArrayList will be discovered while insert/delete element from the middle (or any other position, except tail) of the list. Such operation will move every element, placed on "left hand" from element, which will be processed. In case of insert we should move every element in the next cell to the right hand direction, to make free cell for a new element in the middle of the list. On delete, it will be vise versa - we should move every element in previous cell to the left hand direction, to fill free cell in the middle of the list.

LinkedList has other pros and cons. It could perform insert and delete element from any position with a constant time (but be careful, constant time is only for insert and delete operation, but search time of element position isn't incuded in this constant time). Random element access performed for linear time, cause you need move from element to element in order, until you reach target element, but access to first and last element always performed for constant time (links to these elements always available, so if you want to insert new element to end of list, it doesn't mean that you should pass by all list's elements to reach list position to insert). In common, LinkedList consumes more memory and works slowly comparing to ArrayList. LinkedList will be more useful if you are going lot of insert/delete operation in the middle of list.

2. What do you usually use (ArrayList or LinkedList)? Why?

This question is rephrase of the first question, so the answer will be the same. In 90% of situations ArrayList will be better to use, you can start your answer with it, and then add facts about ArrayList from the first question to prove it. But do not forget to mention about the last 10% and explain in which situation LinkedList could be more useful (See end of answer for question 1).

3. What has better perfomance ArrayList or LinkedList?

It is a tricky variant of the first question. Why? It offers two variants and seems like the only thing for you to do is name some sort of list, but not a give deep answer about pros and cons of lists. Such question, as far as I understand, should uncover developers without deep knowledge of the internal structure of collection's datatypes. My answer to this question is going with some other questions: what operations will be performed with lists? Is there any limits on memory or time? Will be inserts in lists? In common, this is the same as the first question.

4. You need to add 1 million entries to list. What structure will you use?

This is another variant of the first question, also a little bit tricky. There is no enough info to make a proper choose, so you need to ask additional questions to get all info: what part of the list will be new elements added? Is there some info how elements will be processed after adding? Is there any limits on time and memory? This question once was very unlucky for. As a lot of people in this world I imagine adding element one by one, new element after previous, so as adding to end of list. This force me to promote ArrayList as best structure for this, but I have no arguments in this choose and it was wrong. In this question it even doesn't matter what structure you choose, it is important how you can notice that there is not enough information for choose and what questions you will ask to get it.

5. How is deletion performed in ArrayList? What is happening with ArrayList size?

The answer for this question could be also found in answer to the first question. Deletion of the element will cause movement of all elements located on "left hand" in the list on one element to right. Size of ArrayList (its real capacity) will not change. There is automatical extending of size, but there is no auto cut of length, but it can be done manually by calling method trimToSize().

6. Suppose you have a chance to implement method to delete some elements placed in succession in ArrayList. How would you implement it in effective way?

If you know how performed deletion of single element in ArrayList, then you understand what you should get after you method complete its work.

If we perform this the same way as ArrayList usual way, in this case a lot of shifts will be performed. The main idea of your method is to avoid lots of shifts of elements in the list. Suppose we need delete N elements from position M. To make delete in one pass we just need to perform shift of all elements starting from the N+M position for N positions to beginning of the list. This allows us to perform only N shifts instead of ~ N^2/2.

That's all for the first part.