Exploring questions and answers from a job interview for a Java developer position. Part 10

Hi! How many hours does it take to become a master at something? I have often heard something like: "To become a master at anything, you need to spend 10,000 hours on it." That's an intimidating number, isn't it? Still, I wonder if it 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 over that special line of 10,000 hours and become a master, will I feel the difference? Or did I already cross that line a long time ago without realizing it? Either way, you don't have to invest such a huge amount of time to become a programmer. The important thing is to use your time wisely. Your primary goal is to get an interview. And in interviews, would-be software developers are first asked about theory, so that needs to be a strength. In fact, as you prepare for an interview, your job is to discover all the gaps in the knowledge of basic Java theory and then fill them. Today I am here to help you do just that, since today we will continue our review of the most popular interview questions. Well, let's continue!

89. How is an ArrayList different than a LinkedList?

This is one of the most popular questions, along with the question about the internal structure of a HashMap. No interview is complete without it, so your answer should readily roll off your tongue. In addition to the obvious (they have different names), they differ in their internal structure. Earlier, we discussed the internal structure of both ArrayList and LinkedList, so I won't dive into their implementation details. I'll just remind you that ArrayList is implemented using an internal array whose size increases dynamically according to this formula:

<size of the current array> * 3 / 2 + 1

Additionally, the implementation of a LinkedList uses an internal doubly linked list, that is, each element has a reference to the previous and next elements, except for the elements at the start and end of the list. Interviewers love to ask this question like this, "Which is better, ArrayList or LinkedList?" hoping to catch you. After all, if you say one or the other is better, then you've given the wrong answer. Instead, you should clarify the specific situation you are talking about: accessing elements by index or inserting in the middle of the list. Then, depending on their answer, you can explain which one is better. I previously described how ArrayList and LinkedList work in each situation. Let's summarize this by putting them in a row for comparison: Adding an element (add)

1. If an index is not specified, then a new item will be automatically added to the end for both kinds of lists. In a LinkedList, the new element will become the new tail (only a pair of references will be rewritten, so the algorithmic complexity is O(1)).

   The add method adds an element to the last empty cell in the array (O(1)).

2. Adding an item by index usually means inserting it somewhere in the middle of the list. In a LinkedList, the method will first search for the desired location by iterating over the elements from the tail and head (O(n/2)) and will then insert the value by overwriting the references of the elements on both sides of where the new element is inserted (O(1)). The overall algorithmic complexity of this operation will be O(n/2).

   In the same situation (adding by index), an ArrayList finds the desired location (O(1)) and then shifts all the elements located to the right (including the element already stored at the specified index) to the right by one (which may require the creation of a new internal array and copying elements to it) (O(n/2)). The overall complexity is O(n/2).

3. Adding an element to the beginning of a LinkedList is similar to adding an element to the end: the new element becomes the new head (O(1)). But for an ArrayList, that operation requires moving all the elements to the right (O(n)).

The bottom line is that for a LinkedList the algorithmic complexity will range from O(1) to O(n/2). Another observation is that the closer the insertion is to the end or beginning of the list, the faster it is. For ArrayList, the algorithmic complexity ranges from O(1) to O(n), and 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 any existing element. In a LinkedList, this operation is similar to adding, since the biggest challenge here is finding the element's location. The existing element is overwritten by updating a pair of references, so again we have an algorithmic complexity that varies from O(1) to O(n/2), depending on the desired position's distance from the end or beginning of the list. But for an ArrayList, this operation finds the desired cell by index and writes the new element there. Like the set operation, searching by index has an algorithmic complexity of O(1). Getting an element by index (get) Getting an element from a LinkedList follows the same search principle that is used in other operations. The complexity depends on the distance from the end or the beginning, i.e. it varies from O(1) to O(n/2). As noted earlier, for an ArrayList, finding an element by index in the internal array has a complexity of O(1). Removing an element by index (remove) For LinkedList, the same principle applies once again. First, the element is located, and then the references are rewritten, the deleted element's neighbors now refer to each other, eliminating the references to the deleted element, which will subsequently be cleaned up by the garbage collector. In other words, the algorithmic complexity is still the same — it varies from O(1) to O(n/2). For ArrayList, this operation is more like adding a new element (add). First, the method finds the desired element (O(1)), removes it, and then all the elements located to the right are shifted one step to the left in order to close the gap created by the removal. Removing an element has the same algorithmic complexity as the add operation — from O(1) to O(n). The closer the removed element is to the end of the list, the lower the algorithmic complexity of this operation. And now we've covered all the main operations. Let me remind you that when comparing these two types of lists, you need to clarify the specific situation they are being used in. Only then can you unequivocally answer the interviewer's question.

90. How an ArrayList different than a HashSet?

If we could compare ArrayList and LinkedList on an operation-by-operation basis to determine which one is better, we won't find it so easy to make such a comparison between ArrayList and HashSet, because they are completely different collections. You can compare one dessert with another, but comparing a dessert and a savory dish is a challenge — they are painfully different. Still, I will try to point out some of the differences between them:

• ArrayList implements the List interface while HashSet implements the Set interface.

• ArrayList lets you access an element by index: the get operation has O(1) algorithmic complexity, but HashSet only lets you access a desired element by iteration, which yields algorithmic complexity ranging from O(1) to O(n).

• ArrayList allows duplicate elements. In a HashSet, all the elements are unique: any attempt to add an element that is already present in a HashSet will fail (duplicates are checked by hashcode, hence the name of this collection).

• ArrayList is implemented using an internal array, but HashSet is implemented using an internal HashMap.

• ArrayList maintains the elements' order of insertion, but HashSet is an unordered set and does not maintain the order of elements.

• ArrayList allows any number of null values, but you can only add one null value to a HashSet (after all, the elements must be unique).

91. Why does Java have so many different dynamic array implementations?

This is more of a philosophical question. We could also ask why do they come up with so many new and varied technologies? For convenience. And the same thing is true about a large number of dynamic array implementations. None of them can be called the best or ideal implementation. Each has its advantages specific situations. Our job is to know their differences and their strengths/weaknesses in order to be able to use the collection that is most suitable for any given situation.

92. Why does Java have so many different key-value storage implementations?

Here the situation is the same as with the dynamic array implementations. There are definitely none that are universally better than the others: each has strengths and weaknesses. And we must make the most of their strengths, of course. Example: the concurrent package, which has many multithreaded classes, has its own Concurrent collections. The ConcurrentHashMap class has an advantage over the standard HashMap in terms of safety when working with data in a multi-threaded environment, but that comes at the cost of slower performance. And implementations that aren't the best choice in any situation gradually cease to be used. For example: Hashtable, which was originally intended to be a thread-safe HashMap, has been forgotten and fallen out of use, because ConcurrentHashMap is even better than Hashtable when working in a multi-threaded environment.

93. How do I sort a collection of elements?

The first thing to say is that the class representing collection elements must implement the Comparable interface, which consists of the compareTo method. Or you need a class that implements the Comparator interface, including its compare method. Both methods indicate how to compare objects of a given type. This is critical when sorting, because the sorting algorithm needs to understand what principle to use to compare elements. This is mainly done by implementing Comparable directly in the class that you want to sort. Using Comparator is less common. Suppose you're using a class from some library and it doesn't implement Comparable, but you need to sort a collection of its objects. Since you cannot change the code of this class (except by extending it), you can write an implementation of Comparator that indicates how to compare objects of the class. And one more example. If you need to sort objects of the same type in different ways, then you can write multiple Comparator implementations to use in different situations. As a rule, many out-of-the-box classes, e.g. String, already implement the Comparable interface. That means that you don't need to worry about how to compare these classes. You can just go ahead and use them. The first and most obvious way is to use the TreeSet or TreeMap class. These classes store elements in sorted order based on the comparator implemented by the class elements. Don't forget that TreeMap sorts keys, not values. If you use Comparator instead of Comparable, then you need to pass a Comparator object to the collection's constructor when you create it:

TreeSet treeSet = new TreeSet(customComparator);

But what if you have a different type of collection? How do you sort it? In this case, the Collections utility class's second way — the sort() method — is suitable. The method is static, so all you need is to prepend the name of the class and then pass in the list to be sorted. For example:

Collections.sort(someList);

If you are using an implementation of Comparator rather than Comparable, then you need to pass it in as the second argument:

Collections.sort(someList, customComparator);

This operation will change the internal order of the elements in the passed list: the list will be sorted using the comparator. Note that the passed list must be mutable, otherwise the method will fail and throw an UnsupportedOperationException. A third option is to use the Stream class's sorted method, which sorts the collection's elements. If we're using Comparable:

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

If we're using Comparator:

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

The fourth way is to manually implement a sort algorithm, for example, bubble sort or merge sort.

Object class. equals() and hashCode()

94. Give a brief description of the Object class in Java.

In the second part of the review, we already discussed the methods of the Object class. Here I will remind you that the Object class is an ancestor of every class in Java. It has 11 methods, which are in turn inherited by all classes.

95. What are equals() and hashCode() used for in Java?

hashCode() is a method of Object class that is inherited by all classes. Its job is to generate a number that represents a specific object. An example of this method in action can be found in HashMap, where it is called on key objects to get the local hashcode, which will determine which bucket (cell of the internal array) the key-value pair will be stored in. Also, this method is generally used in the equals() method as one of its main ways to identify objects. equals() is a method of the Object class whose job is to compare objects and determine whether they are equal. This method is used everywhere we need to compare objects, because the standard == comparison operator is not suitable for objects, since it only compares object references.

96. Tell us about the contract between equals() and hashCode() in Java?

First, let me say that in order for the equals() and hashCode() methods to work correctly, they must be overridden correctly. Their new implementations must follow these rules:

• Identical objects for which equals returns true must have the same hash codes.
• Objects with the same hash codes are not necessarily equal.

Now seems like a good place to pause until the next part of the review!