Analysis of questions and answers from interviews for 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 completed the first step. This means that now you need to purposefully move towards your goal, without slowing down or turning off along 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 are in the right place, because we will continue to analyze an extensive list of 250+ Java developer interview questions. Let's continue!

Collections

84. Tell us about iterators and their use

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 true, because above this interface there is another one - Iterable . This interface represents the iterator() method , which allows you to call an Iterator object for the current collection. And what exactly is this Iterator object ? An Iterator is an object that provides the ability to move through a collection and iterate over elements without the user needing to know the implementation of a particular collection. That is, this is some kind of 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 whether the end of the collection has been reached);
• next() - returns the next element after the pointer. If there is none, 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 element received from the collection using the next() method . If next() has never been called before remove() is called, an exception will be thrown - IllegalStateException ;
• forEachRemaining(<Consumer>) - performs the passed action with each element of the collection (the method appeared in Java 8).

Here is a small example of iterating through a list and removing 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 display: This means that the removal of elements was successful. Once we had an iterator, we could use a method to print all the elements to the screen:

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

But after this, the iterator would become unsuitable for further use, since it would traverse the entire list, and a regular iterator does not have methods for backtracking. Here we gradually approach LinkedList , namely, its listIterator() method , which returns a modernized type 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 located before the pointer (whether there is 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 move in both directions and frees up your hands when working with elements. Also, when people talk about iterators, they sometimes mean the pattern itself. To avoid getting into trouble and talk about it convincingly, read this article about the Iterator pattern .

85. What is the collection hierarchy in Java Collection Framework?

There are two collection hierarchies in Java. The first hierarchy is the Collection hierarchy itself with the following structure: It, 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 deleted by their index in this collection (analogous to an array, but with dynamic resizing). The interface has standard implementations - ArrayList , Vector ( considered obsolete and not actually used ) and LinkedList .
• Queue is 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 . The interface has the following standard implementations: LinkedList (yes, it implements Queue too) and PriotityQueue .

The second hierarchy of collections is Map , which has the following structure: In this collection there are no divisions into subcollections (since the Map hierarchy itself is something like a subcollection, but lying separately). Standard Map implementations are Hashtable (considered deprecated), LinkedHashMap and TreeMap . Actually, when asked about Collection , both hierarchies are usually meant.

86. What is the internal structure of an ArrayList?

ArrayList is similar to an array, but with the ability to expand dynamically. 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 internal array is full, 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. Next, all 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 dynamic extensibility of ArrayList is implemented . Let's look at the most used ArrayList methods : 1. add(<Elelement>) - adds an element to the end of the array (to the last empty cell), and first checks whether there is space in this array. If it is not there, a new array is created into which the elements are copied. The logarithmic complexity of this operation is O(1). There is a similar method - add(<Index>,<Elelement>) . It adds an element not to the end of the list (array), but to a specific cell with the index that came as an argument. In this case, the logarithmic complexity will differ depending on where it is added:

• if this was approximately 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 move only half of the list elements one cell to the right.

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>,<Elelement>) - writes an 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 a complexity of O(1), and writing the element. 3. remove(<index>) - removing an element by its index in the internal array. When deleting an item that is not at the end of the list, you must move all the items to the right of it one cell to the left to close the gap left after deleting the item. Therefore, the logarithmic complexity will be the same as add(<Index>,<Elelement>) if the element was in the middle - O(N/2) - because you need to shift half of the elements one to the left. Accordingly, if it was at the beginning - O(N). Well, if at the end it’s O(1), there’s no need to move anything. For those who want to delve deeper into this topic, I will leave this link to an article with 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 link to the previous element ( previous ) and the next one ( next ). The first element does not have a link to the previous one (it is the first), but it is considered the head of the list, and the LinkedList has a link directly to it. The last element, in fact, does not 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 of accessing the head or tail of a list is O(1). In ArrayList, when the list grew, the internal array increased, but here everything happens more simply - when adding an element, a couple of links simply change. Let's look at some of the most used LinkedlList methods : 1. add(<Elelement>) - adding at the end of the list, i.e. after the last element (5) a link to the new element will be added as next . The new element will have a link to the last (5) as the previous element. The logarithmic complexity of such an operation will be O(1), since only a link to the last element is needed, and as you remember, the tail has a direct link from LinkedList and the logarithmic complexity of accessing it is minimal. 2. add(<Index>,<Elelement>) - adding an element by index. When adding an element, for example, to the middle of a list, the elements from the head and tail (on both sides) are first iterated 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 the new element's 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, 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) - the elements from the head and tail will be sorted simultaneously until the required element is found.

3. set(<Index>,<Elelement>) - writes an 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 ) reference the element that comes after the one being removed ( next ). And vice versa: so that the element that comes after the one being deleted refers to the one that comes before the one being deleted: The result is a process inverse to adding by index ( add(<Index>,<Elelement>) ). For those wishing to learn more about the internal structure of LinkedList , I recommend reading this article .

88. What is the internal structure of a HashMap?

Perhaps one of the most popular questions when interviewing a Java developer. 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 doubles each time 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 the key, a key, a value, and 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 a new pair is saved using the put method . First, the hachCode() of the key is taken. Therefore, for hashmap to work correctly , you need to take classes in which this method is overridden as keys. This hash code is then used in the internal method - hash() - to determine the number within the size of the table array . Next, using the received number, a specific cell of the table array is accessed . 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 and compared 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 ( get(<key>) method ), the hashCode of the key is calculated, then its value within the array using hash() , and using the resulting number, the cell of the table array is found, in which the search is already carried out by enumerating nodes and comparison the key of the desired node with the key of the current one. Operations in Map, in an ideal situation, have an algorithmic complexity of O(1), because they are accessing an array, and as you remember, regardless of the number of elements, operations on an array have a complexity of O(1). But this is ideal. 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 it is necessary to iterate over the elements before finding the right place. I can't help but mention this: starting with 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? HashMap is a big topic, and people like to ask questions about it in interviews. Therefore, I advise you to understand it in detail (so that it bounces off your teeth). Personally, I haven't had an interview without HashMap questions . You can find a deep dive into HashMap in this article . That's all for today, to be continued...