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

Hello! How many hours does it take to become a master at something? Often heard something like: "To become a master in any field, you need to spend 10,000 hours." Scary number, isn't it? However, I'm wondering if this is true? And I'm constantly trying to figure out how many hours I have already invested in mastering the art of programming. And when I step over those cherished 10,000 hours and become a master, will I feel this difference? Or have I already stepped over them for a long time without realizing it? One way or another, to become a programmer, you do not 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 beginners, first of all, they just ask the theory, so you must be strong in it. Actually, when preparing for an interview, your task is to find 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 the analysis of the most popular questions. So, let's continue!

89. What is the difference between ArrayList and LinkedList?

This is one of the most popular questions along with the question about the internals 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 - a different name - they differ in their internal structure. Earlier, we analyzed the internals of both ArrayList and LinkedList , so I won't go into the details of their implementation. Let me just remind you that ArrayList is implemented on the basis of an internal array, which, if necessary, increases according to the formula:

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

At the same time, LinkedList is implemented on the basis of an internal doubly linked list, that is, each element has a link to the previous and next, excluding the 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 which specific situation you are talking about - index access or insertion in the middle of the list. Depending on the answer, you will be able to explain your choice. Earlier I already described how ArrayList and LinkedList work.in one situation or another. Let's sum it up by putting them side by side for comparison: Adding an element (add)

1. Adding a new element without specifying an index as a location will happen automatically at the end of both lists. In a LinkedList, the new element will become the new tail (only rewriting of a pair of links occurs - algorithmic complexity O(1) ).

   The ArrayList will add a new element to the last empty array cell - O(1) .

2. Adding an element by index usually means inserting it roughly in the middle of the list. The LinkedList will first search for the right place by iterating through the elements from the “tail” and “head” - O(n/2) , and then inserting the value by redefining the links of the elements between which a new one is inserted - O(1) . The total algorithmic complexity of this action will be O(n/2) .

   ArrayList in this situation finds the element by index - O(1) , and all elements on the right (including the element that is already stored at this index) move one unit to the right (this may require creating a new list and copying elements into it) - O (n/2) . The total complexity is O(n/2) .

3. Adding an element to the beginning of a LinkedList will have a situation similar to adding to the end: the new element will become the new “head” - O(1) , while the ArrayList will need to move all elements to the right - O(n) .

Bottom line: in LinkedList, the algorithmic complexity will range from O(1) to O(n/2) . That is, the closer the insertion is to the end or the 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 go through rewriting a pair of links, so here also the algorithmic complexity will range fromO(1) to O(n/2) depending on how far the position is from the end or the beginning of the list. At that time, the required cell will be found in the ArrayList for this operation by index, and a new element will be written to it. Search by index, like this operation, has an algorithmic complexity of O(1) . Get an element by index (get) In LinkedList , the element will be taken according to the same principle as the search for other operations - depending on the distance from the end or the beginning, i.e. 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 element by index (remove) For LinkedList, its principle of operation also works here: first the element is found, and then the links are rewritten - the element's neighbors begin to refer to each other, losing links 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 an ArrayList , this operation is more like 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 gap. The delete operation will have the same algorithmic complexity as the add operation, from O(1) to O(n) . The closer the removal is to the end of the list, the less algorithmic complexity it has. Actually, these were all the main operations. I remind you: when comparing these two lists, you need to clarify what specific situation we are talking about, and then you can already unambiguously answer the question posed.

90. How is ArrayList different from HashSet?

If ArrayList and LinkedList could be compared by operations - where who 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 with meat it will work out - they are painfully different. However, I will try to give some of their differences:

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

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

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

• ArrayList is implemented with an internal array, while HashSet is implemented with an internal HashMap ;

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

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

91. Why does Java have such a variety of dynamic array implementations?

Well, it's more of a philosophical question. Well, why come up with so many new diverse technologies? For comfort. Actually, it is 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 a particular situation. And our task is to know their differences, their strengths / weaknesses: in order to be able to use the most suitable of them in the right situation.

92. Why does Java have such a variety of key-value storage implementations?

Here the situation is the same as with dynamic array implementations. Definitely the best there is no: each has strengths and weaknesses. And, of course, we must make the most of our strengths. Example: the concurrent package, which has many multithreading 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 it loses in speed in a non-multi-threaded environment. Well, implementations that are not the strongest in any of the situations gradually cease to be used. Example: Hashtable , which was originally intended to be thread-safeHashMap , but ConcurrentHashMap outperformed it when running in a multi-threaded environment, and as a result, Hashtable was 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 ways indicate how to compare objects of a given type. When sorting, this is critical, because you need to understand the principle by which elements can be compared. Basically, the way is through the implementation of Comparable , implemented directly in the class that you want to sort. At the same time, the application of Comparator- but more rarely. Let's say you're using a class from some library that doesn't have a Comparable implementation , but you need to sort it somehow. Without being able to change the code of this class (other than extend it), you can write an implementation of Comparator , in which you specify how objects of this class should be compared. And one more example. Let's say you need different sorting principles for 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 do not need to worry about how to compare them. You just take and use them. The first and most obvious way is to use a collection of type TreeSet or TreeMap , which store the elements in an already sorted order, according to the element class comparer. Don't forget that TreeMap sorts the keys, not the values. If you use the Comparator implementation instead of Comparable , you will need to pass its object to the collection's constructor on creation:

TreeSet treeSet = new TreeSet(customComparator);

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

Collections.sort(someList);

If you are using a Comparator implementation instead of Comparable , 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 passed list of elements must be mutable, i.e. mutable, otherwise the method will fail and an UnsupportedOperationException will be thrown . A third way is to 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 way is to manually implement a sort, such as bubble sort or merge sort .

class object. Equals and HashCode

94. Briefly describe 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 are respectively inherited by all classes. Information on all 11 methods can be found in the second part of the question paper.

95. Why use Equals and HashCode 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 particular 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 about the work of HashMap in detail in part 9 of the analysis , so we won’t dwell on it too much. It is also commonly used in the equals() method as one of its main tools for determining the identity of objects. equals() - class methodObject , whose task 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 through == is not suitable for objects, because compares only references to them.

96. Tell me 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 redefined correctly. After that, they must follow the rules:

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

On this we will pause until the next part of the analysis!