Analysis of questions and answers from interviews for a Java developer. Part 9

Firework! Being a programmer is not easy. You need to constantly learn, always learn something new. But, as in any other business, the most difficult thing is to start, to take the first step towards your goal. And since you are sitting on this site and reading this article, you have done the first step. So, now you need to purposefully move towards your goal, without slowing down and not turning off on the way. If I understand correctly, your goal is to become a Java developer or enhance your knowledge if you are one. If so, then you're in the right place, as we'll continue to sort through an extensive list of 250+ Java developer interview questions. Let's continue!

Collections

84. Tell us about iterators and their uses

Collections are one of the favorite topics in any Java developer interview, and when talking about the collection hierarchy, candidates often say that it starts with the Collection interface . But this is not so, because above this interface there is one more - Iterable . This interface represents the iterator() method , which allows you to call an Iterator object on the current collection. And what is this Iterator object ? Iteratoris an object that provides the ability to move through the collection and iterate over the elements, and the user does not need to know the implementation of a particular collection. That is, it is some pointer to the elements of the collection, which, as it were, looks at a certain place in it. The iterator has the following methods:

• hasNext() - returns true if there is an element located after the pointer (this method allows you to find out if the end of the collection has been reached);
• next() - returns the next element after the pointer. If there is none, a NoSuchElementException is thrown . That is, before using this method, it is better to make sure that the element exists - using hasNext() ;
• remove() - removes the last received element from the collection using the next() method . If next() has never been called before remove() was called, an IllegalStateException will be thrown ;
• forEachRemaining(<Consumer>) - performs the passed action on each element of the collection (method introduced since Java 8).

Here is a small example of iterating through a list and deleting all its elements using the iterator methods discussed:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

The console will output: This means that the removal of the elements was successful. Given an iterator, we could use a method to display all elements on the screen:

iterator.forEachRemaining(x -> System.out.print(x));

But after that, the iterator would become unsuitable for further use, since it would bypass the entire list, and the usual iterator does not have methods for reverse enumeration. Here we smoothly approach LinkedList , namely, its listIterator() method , which returns a modernized kind of iterator - ListIterator . Besides the regular (standard) iterator methods, this one has additional ones:

• add(<Element>) - inserts a new element into the list;
• hasPrevious() - returns true if there is an element before the pointer (is there a previous element);
• nextIndex() - returns the index in the list of the next element after the pointer;
• previous() - returns the previous element (up to the pointer);
• previousIndex() - returns the index of the previous element;
• set(<Element>) - Replaces the last element returned by the next() or previous() methods .

As you can see, the functionality of this iterator is much more interesting: it allows you to go in both directions and unties your hands when working with elements. Also, when talking about iterators, sometimes they mean the pattern itself. In order not to get into trouble and talk about it convincingly, read this article about the Iterator pattern .

85. What is the hierarchy of collections in the Java Collection Framework?

There are two collection hierarchies in Java. The first hierarchy is the Collection hierarchy itself , with the following structure: This in turn is divided into the following subcollections:

• Set is an interface that describes such a data structure as a set containing unordered unique (non-repeating) elements. The interface has standard implementations - TreeSet , HashSet , and LinkedHashSet .
• List is an interface that describes a data structure that stores an ordered sequence of objects. Instances contained in a List can be inserted and removed by their index in the given collection (similar to an array, but with dynamic resizing). The interface has standard implementations - ArrayList , Vector ( deprecated and not actually used ) and LinkedList .
• Queue - an interface that describes a data structure that stores elements in the form of a queue that follows the FIFO - First In First Out rule (first in, first out). The interface has the following standard implementations: LinkedList (yes, it implements Queue too) and PriotityQueue .

The second collection hierarchy is Map , which has the following structure: There are no divisions into subcollections in this collection (since the Map hierarchy itself is something like a subcollection, but lying separately). The standard Map implementations are Hashtable ( deprecated), LinkedHashMap and TreeMap . Actually, when people ask about Collection , they usually mean both hierarchies.

86. What is the internal structure of ArrayList?

ArrayList is similar to an array, but with the ability to dynamically expand. What does it mean? The fact is that ArrayList works on the basis of a regular array, namely, it stores elements in an internal array (its default size is 10 cells). When the inner array is filled, a new array is created, the size of which is determined by the formula:

<размерТекущегоМассива> * 3 / 2  + 1

That is, if the size of our array is 10, the size of the new one will be: 10 * 3 / 2 + 1 = 16. Then all the values ​​​​from the first (old) array are copied into it using the native System.arraycopy() method, and the first array is deleted . Actually, this is how the dynamic extensibility of ArrayList is implemented . Let's consider the most used methods of ArrayList : 1. add(<Element>) - adds an element to the end of the array (to the last empty cell), while first checking if there is a place in this array. If it doesn't exist, a new array is created and the elements are copied into. The logarithmic complexity of this operation is O(1). There is a similar method - add(<Index>,<Element>). It adds an element not to the end of the list (array), but to a specific cell with an index that came as an argument. In this case, the logarithmic complexity will differ depending on the place of addition:

• if it was about the beginning of the list, the logarithmic complexity will be close to O (N), because all elements located to the right of the new one will have to be moved one cell to the right;
• if the element is inserted in the middle - O(N/2) because we need to shift one cell to the right only half of the list items.

That is, the logarithmic complexity of this method ranges from O(N) to O(1) depending on where the element is inserted. 2. set(<Index>,<Element>) - writes the element to the specified position in the list. If there is already an element at that position, overwrites it. The logarithmic complexity of this operation is O(1), because there are no shifts: only searching by index in the array, which, as we remember, has complexity O(1), and writing the element. 3. remove(<index>) - remove an element by its index in the internal array. When deleting an element that is not at the end of the list, it is necessary to move all elements to the right of it one cell to the left in order to close the gap created after the element was deleted. Therefore, the logarithmic complexity will be the same as that ofadd(<Index>,<Element>) , if the element was in the middle - O(N/2), because you need to move half of the elements one left. Accordingly, if it was at the beginning - O (N). Well, if at the end - O (1), after all, nothing needs to be moved. For those who want to delve into this topic, I will leave this link to an article with an analysis of the ArrayList class .

87. What is the internal structure of LinkedList?

If ArrayList contains elements in an internal array, then LinkedList is in the form of a doubly linked list. This means that each element contains a reference to the previous element ( previous ) and the next element ( next ). The first element does not have a link to the previous one (it is the first one after all), while it is considered the head of the list, and LinkedList has a link directly to it. The last element does not actually have a next element, it is the tail of the list, and therefore there is a direct link to it in the LinkedList itself . Therefore, the logarithmic complexity when accessing the head or tail of the list is O(1). In ArrayListwhen the list increased, the internal array increased, but immediately everything is simpler - when an element is added, a couple of links simply change. Let's look at some of the most used LinkedlList methods : 1. add(<Element>) - adds at the end of the list, ie. after the last element (5) a reference to the new element will be added as next . The link to the last (5) as the previous element will be added to the new element. The logarithmic complexity of such an operation will be O (1), since only a reference to the last element is needed, and as you remember, there is a direct link to the tail from LinkedList and the logarithmic complexity of accessing it is minimal. 2.add (<Index>,<Element>)— adding an element by index. When adding an element, for example, in the middle of the list, the elements from the head and tail (on both sides) are first sorted out until the desired place is found. If we want to insert an element between the third and fourth (in the figure above), then when searching for the right place, the next link of the third element will already point to the new one. For the new one, the previous link will point to the third one. Accordingly, the link of the fourth element - previous - will already point to the new element, and for the new element, the next link will point to the fourth element: The logarithmic complexity of this method will depend on the index given to the new element:

• if it is close to the head or tail, then it will approach O (1), since it will not actually be necessary to iterate over the elements;
• if it is close to the middle, then O (N / 2) - there will be a sorting of elements from the head and tail at the same time until the desired element is found.

3. set(<Index>,<Element>) - writes the element to the specified position in the list. The logarithmic complexity of this operation will range from O(1) to O(N/2), again depending on how close the element is to the head, tail, or middle. 4. remove(<index>) - removes an element from the list, essentially making the element that comes before the one being removed ( previous ) refer to the element that comes after the one being removed ( next ). And vice versa: so that the element that comes after the removed one refers to the one that comes before the removed one: The process is reverse of adding by index ( add(<Index>,<Element>) ). For those wishing to learn more about the internals of LinkedListI recommend reading this article .

88. What is the internal structure of HashMap?

Perhaps one of the most popular questions in a Java developer interview. HashMap v works with key-value pairs . How are they stored inside the HashMapv itself ? Inside the HashMap there is an array of nodes:

Node<K,V>[] table

By default, the size of the array is 16, and it increases each time twice as it is filled with elements (when LOAD_FACTOR is reached - a certain percentage of fullness, by default it is 0.75 ). Each node stores a hash of a key, a key, a value, a link to the next element: Actually, “link to the next element” means that we are dealing with a singly linked list, where each element contains a link to the next one. That is, HashMap stores data in an array of singly linked lists. But I’ll note right away: when one cell of the table array has a link to a similar singly linked list consisting of more than one element, this is not good. This phenomenon is called collision.. But first things first. Let's see how the new pair is stored through the put method . The hachCode() of the key is taken first . Therefore, for the hashmap to work correctly , you need to take classes in which this method is overridden as keys. Next, this hash code is used in the internal method - hash() - to determine the number within the size of the table array . Further on the received number, there is an appeal to a specific cell of the table array . Here we have two cases:

1. The cell is empty - the new Node value is stored in it .
2. The cell is not empty - the value of the keys is compared. If they are equal, the new Node value overwrites the old one, if they are not equal, the next element is accessed , the comparison is already made with its key ... And so on until the new value overwrites some old one or reaches the end of the singly linked list and will be stored there as the last element.

When searching for an element by key (method get(<key>) ), the hashCode of the key is calculated , then its value within the array using hash() , and the cell of the table array is found by the resulting number , in which the search is already being carried out by iterating over the nodes and comparing the key of the desired node with the key of the current one. Operations in Mapin the ideal scenario, they have algorithmic complexity O (1), because an array is being accessed, and as you remember, regardless of the number of elements, operations in an array have complexity O (1). But this is in the ideal case. When the array cell being used is not empty (2) and there are already some nodes there, the algorithmic complexity turns into linear O(N), because now you need to iterate over the elements before you find the right place. I can't help but mention this: since Java 8, if a singly linked list node has more than 8 elements (collisions), it turns into a binary tree. In this case, the algorithmic complexity will no longer be O(N), but O(log(N)) - that's another matter, isn't it? hashmapis a big topic, and people like to ask questions on it at interviews. Therefore, I advise you to understand it in detail (so that it bounces off your teeth). Personally, I have not had interviews without questions on HashMap . You can find a deep analysis of HashMap in this article . That's all for today, to be continued...