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

Hello! How many hours does it take to become a master at something? I’ve often heard something like: “To become a master at anything, you need to spend 10,000 hours.” A scary number, isn't it? However, I wonder if this is true? And I'm constantly trying to figure out how many hours I've already invested in mastering the art of programming. And when I cross those cherished 10,000 hours and become a master, will I feel this difference? Or have I already stepped over them long ago without realizing it? One way or another, to become a programmer, you don’t need to invest such a huge amount of time. The main thing is to use it wisely. Your primary goal is to pass the interview. And at interviews for newcomers, the first thing they ask is theory, so you must be strong in it. Actually, when preparing for the interview, your task is to discover all your gaps in the basic theory of a Java developer and cover them with knowledge. And today I will help you in this matter, because I am here to continue analyzing the most popular questions. So let's continue!

89. How is ArrayList different from LinkedList?

This is one of the most popular questions along with the question about the internal structure of HashMap . Not a single interview is complete without it, and therefore the answer to it should “bounce off your teeth.” In addition to the obvious - different names - they differ in internal structure. Previously, we examined the internal structure of both ArrayList and LinkedList , so I will not go into the details of their implementation. Let me just remind you that ArrayList is implemented based on an internal array, which is increased as needed according to the formula:

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

At the same time, LinkedList is implemented based on an internal doubly linked list, that is, each element has a link to the previous and next, excluding values ​​that are the beginning/end of the list. People like to ask this question in the format: “Which is better - ArrayList or LinkedList ?”, hoping to catch you. After all, if you point to one of them as an answer, it will be the wrong answer. Instead, you should clarify what specific situation you are talking about - index access or insertion into the middle of a list. Depending on the answer, you will be able to explain your choice. I have previously described how ArrayList and LinkedList work in one situation or another. Let's summarize this by putting them on the same page for comparison: Adding an element (add)

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

Bottom line: in LinkedList, algorithmic complexity will range from O(1) to O(n/2) . That is, the closer the insertion is to the end or beginning of the list, the faster it is. At the same time, for ArrayList it ranges from O(1) to O(n) : the closer the insertion is to the end of the list, the faster it is. Setting an element (set) This operation writes an element to the specified position in the list, overwriting the previous one, if any. In LinkedList, this operation will be similar to adding, because The biggest difficulty here is finding the element. Rewriting an element will take place by rewriting a pair of links, so here too the algorithmic complexity will range from O(1) to O(n/2) depending on the distance of the position from the end or beginning of the list. At that time, the required cell will be found in the ArrayList for this index operation, and a new element will be written to it. Index search, like this operation, has an algorithmic complexity of O(1) . Take an element by index (get) In LinkedList, taking an element will occur according to the same principle as searching for other operations - depending on the distance from the end or beginning, i.e. from O(1) to O(n/2) . In ArrayList , as I said earlier, finding an element in an array by index has O(1) complexity . Remove an element by index (remove) For LinkedList, its operating principle also works here: first the element is found, and then the links are overwritten - the neighbors of the element begin to refer to each other, losing references to this element, which will subsequently be deleted by the garbage collector. That is, the algorithmic complexity is still the same - from O(1) to O(n/2) . For ArrayList , this operation is more similar to the operation of adding a new element (add). First, the required element is found - O(1) , then it is removed, and all the elements that were to the right of it are moved one unit to the left to close the resulting gap. The delete operation will have the same algorithmic complexity as the add operation - from O(1) to O(n) . The closer the deletion is to the end of the list, the less algorithmic complexity it has. Actually, these were all the main operations. Let me remind you: when comparing these two lists, you need to clarify what specific situation we are talking about, and then you can unambiguously answer the question posed.

90. How is ArrayList different from HashSet?

If ArrayList and LinkedList could be compared in terms of operations - which is better - then it is not so easy to compare ArrayList with HashSet , because these are completely different collections. You can compare one sweet dish with another, but it will work out with a meat dish - they are too different. However, I will try to give some differences between them:

• ArrayList implements the List interface , while HashSet implements the Set interface ;

• In ArrayList, access is possible by element index: the get operation has an algorithmic complexity of O(1) , and in HashSet the required element can only be obtained by brute force, and this is from O(1) to O(n) ;

• ArrayList allows duplicate elements. In a HashSet, all elements are unique: adding an element to a HashSet whose analogue is already present in the collection will not work (duplicates are checked using hashcode, hence the name of this collection);

• ArrayList is implemented using an internal array, and HashSet is implemented using an internal HashMap ;

• An ArrayList maintains the insertion order of the elements, while a HashSet is an unordered set and does not maintain the order of the elements;

• ArrayList allows any number of empty values ​​(null), only one null value can be inserted into a HashSet (after all, the uniqueness of the elements).

91. Why is there such a variety of dynamic array implementations in Java?

Well, this is more of a philosophical question. Well, why do they come up with so many different new technologies? For comfort. Actually, it’s the same with a large number of dynamic array implementations. None of them can be called the best or ideal. Each has an advantage in some specific situation. And our task is to know their differences, their strengths/weaknesses: in order to be able to use the most suitable one in the right situation.

92. Why is there such a variety of key-value storage implementations in Java?

Here the situation is the same as with dynamic array implementations. There is no one best: each has strengths and weaknesses. And we, of course, must make the most of our strengths. Example: the concurrent package, which contains many multi-threaded technologies, has its own Concurrent collections. The same ConcurrentHashMap has an advantage in the safety of multi-threaded work with data compared to a regular HashMap , but in a non-multi-threaded environment it loses in speed. Well, implementations, which are not the strongest in any situation, are gradually stopped being used. Example: Hashtable was originally intended to be a thread-safe HashMap , but ConcurrentHashMap outperformed it in a multi-threaded environment and Hashtable was eventually forgotten and no longer used.

93. How to sort a collection of elements?

The first thing to say is that the collection element class must implement the Comparable interface and its compareTo method . Or you need a class that implements Comaprator with its comparator method . You can read more about them in this post . Both methods specify how objects of a given type should be compared. When sorting, this is critically important, because you need to understand the principle by which elements can be compared. The main way to do this is to implement Comparable , implemented directly in the class you want to sort. At the same time, the use of Comparator is less common. Let's say you're using a class from some library that doesn't have a Comparable implementation , but you'll need to sort it somehow. Without being able to change the code of this class (except by extending it), you can write an implementation of Comparator , in which you indicate on what principle you want to compare objects of this class. And one more example. Let's say you need different principles for sorting objects of the same type, so you write several Comparators that you use in different situations. As a rule, many classes out of the box already implement the Comparable interface - the same String . Actually, when using them, you don’t have to worry about how to compare them. You just take them and use them. The first and most obvious way is to use a collection of type TreeSet or TreeMap , which stores the elements in already sorted order according to the element class comparator. Remember that TreeMap sorts keys, but not values. If you use the Comparator implementation instead of Comparable , you will need to pass its object to the collection constructor upon creation:

TreeSet treeSet = new TreeSet(customComparator);

But what if you have a different type of collection? How to sort it? In this case, the second method of the Collections utility class is suitable - the sort() method . It is static, so all you need is the name of the class and a method to which the required list is passed. For example:

Collections.sort(someList);

If you are not using Comparable , but rather an implementation of Comparator , you need to pass it as the second parameter:

Collections.sort(someList, customComparator);

As a result, the internal order of the elements of the passed list will change: it will be sorted according to the element comparator. I note that the transferred list of elements must be mutable, i.e. mutable, otherwise the method will not work and an UnsupportedOperationException will be thrown . As a third way, you can use the Stream sort operation , which sorts the elements of the collection if the Comparable implementation is used :

someList = someList.stream().sorted().collect(Collectors.toList());

if Comparator :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

You can read more about Stream in this article . The fourth method is to manually implement sorting, such as bubble sort or merge sort .

ClassObject. Equals and HashCode

94. Give a brief description of class object in Java

In the second part of the analysis, we already talked about the methods of the Object class , and I will remind you that the Object class is the progenitor of all classes in Java. It has 11 methods, which, accordingly, are inherited by all classes. Information about all 11 methods can be found in the second part of the discussion.

95. What are Equals and HashCode used for in Java?

hashCode() is a method of the Object class that is inherited by all classes. Its task is to generate some number that represents a specific object. An example of using this method is its use in a HashMap on a key object to further determine the local hashcode, which will determine the cell of the internal array (bucket) in which the pair will be stored. We talked in detail about the work of HashMap in part 9 of the analysis , so we won’t dwell on this too much. Also, as a rule, this method is used in the equals() method as one of its main tools for determining the identity of objects. equals() is a method of the Object class whose job is to compare objects and determine whether they are equal or not. This method is used everywhere where we need to compare objects, because the usual comparison using == is not suitable for objects, because compares only links to them.

96. Tell us about the contract between Equals and HashCode in Java?

The first thing I will say is that for the equals() and hashCode() methods to work correctly , they need to be overridden correctly. After this they must follow the rules:

• identical objects for which comparison via equals returns true must have the same hash codes;
• objects with the same hash codes may not always be equal.

At this point we will pause until the next part of the analysis!