User Konstantin
Konstantin
Level 36
Odesa

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

Published in the Random group
Being a programmer isn't easy. There is always something new to learn. And, as in any other endeavor, the most difficult thing is to start, to take the first step towards your goal. But since you're already here and reading this article, you have completed the first step. This means that now you need to deliberately move towards your goal, without slowing down or veering off to the side. I assume your goal is to become a Java developer or beef up your knowledge if you are already a developer. If so, let’s continue to tackle an extensive list of Java developer interview questions. Exploring questions and answers from a job interview for a Java developer position. Part 9 - 1Let's continue!

Collections

84. Tell us about iterators and how they are used

Collections is a favorite topic in any Java developer interview. When answers questions about the collection hierarchy, candidates often say that it starts with the Collection interface. But this is not so. There is another interface one level above: Iterable. This interface consists of the iterator() method, which lets you access the Iterator object for the current collection. And what exactly is this Iterator object? The Iterator object provides the ability to move through a collection and iterate over its elements, and the user doesn't need to know the specific implementation details of the collection. In other words, it is a kind of pointer to the collection's elements, as if it is peeking inside at one of them. The iterator has methods such as:
  • hasNext() — returns true if the iteration has another element (this method lets you know when you've reached the end of the collection);

  • next() — returns the next item in the iteration. If there isn't one, then a NoSuchElementException is thrown. That means that before you use this method, it is best to use the hasNext() method to make sure a next element exists;

  • remove() — removes from the collection the last element received using the next() method. If next() has never been called, then calling remove() will cause an IllegalStateException to be thrown;

  • forEachRemaining(<Consumer>) — executes the passed action on each element of the collection (this method appeared in Java 8).

Here is a small example of iterating through a list and removing all its elements using the various iterator methods we looked at:

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 the following:
0
This means that the elements were removed successfully. Once you get an iterator, you can use a method to display all the elements on the screen:

iterator.forEachRemaining(x -> System.out.print(x));
But once we do this, the iterator becomes unsuitable for further use: it has traversed the entire list, and an ordinary iterator has no methods for iterating backwards. And that makes for a nice segue into a discussion of LinkedList, specifically, its listIterator() method, which returns an enhanced type of iterator: ListIterator. In addition to the methods of a regular (standard) iterator, this kind has the following:
  • add(<Element>) — adds a new element to the list;

  • hasPrevious() — returns true if there is an element located before the next element (if there is a previous element);

  • nextIndex() — returns the index of the next element;

  • previous() — returns the previous element (the one before the next element);

  • previousIndex returns the index of the previous element.

  • set(<Element>) — replaces the last element returned by next() or previous().

As you can see, this iterator has much more interesting functionality: it lets you walk in both directions and provides considerable freedom when working with elements. You should also know that when people talk about iterators, they sometimes mean the design pattern itself. Exploring questions and answers from a job interview for a Java developer position. Part 9 - 2

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

There are two collection hierarchies in Java. The first hierarchy is the Collection hierarchy, which has the following structure: Exploring questions and answers from a job interview for a Java developer position. Part 9 - 3It is divided into the following subcollections:
  • Set is an interface that describes a set, a data structure that contains unordered unique (non-repeating) elements. This interface has some standard implementations: TreeSet, HashSet, and LinkedHashSet.

  • List is an interface describing a data structure that stores an ordered sequence of objects. Objects in a List can be inserted and removed by their index in the list (like an array, but with dynamic resizing). This interface also has some standard implementations: ArrayList, Vector (deprecated and not actually used), and LinkedList.

  • Queue is an interface describing a data structure that stores items in a First In First Out (FIFO) queue. This interface has the following standard implementations: LinkedList (that's right, it also implements Queue) and PriotityQueue.

The second collection hierarchy is the Map hierarchy, which has the following structure: Exploring questions and answers from a job interview for a Java developer position. Part 9 - 4This collection hierarchy has no divisions into subcollections (since the Map hierarchy itself is something of a subcollection that stands apart on its own). The standard Map implementations are Hashtable (deprecated), LinkedHashMap, and TreeMap. In practice, when people ask about Collections, they usually mean both hierarchies. Exploring questions and answers from a job interview for a Java developer position. Part 9 - 5

86. What is the internal structure of an ArrayList?

An ArrayList is like an array, but it can expand dynamically. What does that mean? Under the hood, ArrayList uses an ordinary array, i.e. it stores its elements in an internal array whose default size is 10 cells. Once the internal array is full, a new array is created. The size of the new array is determined by this formula:

 <size of the current array> * 3 / 2 + 1
So, if the size of our array is 10, then the size of the new one will be: 10 * 3 / 2 + 1 = 16. Then all values from the original (old) array are copied into it using the built-in System.arraycopy() method, and the original array is deleted. In a nutshell, that is how ArrayList implements dynamic resizing. Let's consider the most popular ArrayList methods: 1. add(<Element>) — adds an element to the end of the array (in the last empty cell), after first checking whether there is an available cell in the array. If not, a new array is created, and the elements are copied into it. The time complexity of this operation is O(1). There is a similar add(<Index>, <Elelement>) method. It adds an element not to the end of the list (array), but to the specific cell indicated by the index that came in as an argument. In this case, the time complexity will vary depending on where you add:
  • if the add is close to the beginning of the list, then the time complexity will be close to O(N), because all the 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, then it will be O(N/2), since we only need to shift half of the list items one cell to the right.
That is, this method's time complexity ranges from O(1) to O(N), depending on where the element is inserted. 2. set(<Index>, <Element>) — writes an element to the specified position in the list. If an element is already present at that position, the method overwrites it. The time complexity of this operation is O(1), because it doesn't involve any shift operations: we just use the index to calculate the cell's address in the array, which has complexity O(1), and then write the new element. 3. remove(<index>) — removes an element by its index in the internal array. When removing an item that is not at the end of the list, all items to the right of the deleted one must be shifted one cell to the left in order to close the gap that results from the deletion. Accordingly, the time complexity will be the same as for add(<Index>, <Element>) when an element is added in the middle: O(N/2). After all, you need to shift half of the elements one cell to the left. And if we're talking about the beginning, then O(N). Or if at the end, then O(1), since you don't need to move anything.

87. What is the internal structure of a LinkedList?

An ArrayList contains elements in the internal array, but a LinkedList stores them in a doubly-linked list. This means that each element contains a link to the previous element and to the next element. The first element does not link to a previous element (after all, it is the first). It is also considered the head of the list, and the LinkedList object has a direct reference to it. Similarly, the last element does not have the next element, since it is the tail of the list. The LinkedList object also references it directly. This means that the time complexity of accessing the head or tail of a list is O(1). Exploring questions and answers from a job interview for a Java developer position. Part 9 - 6In ArrayList, if the list grows, then the internal array grows. Here everything is easier: adding a reference is as simple as changing a couple of links. Let's look at some of the most used LinkedList methods: 1. add(<Element>) — adds an element to the end of the list, i.e. after the last element (5), a link to the new element will be added as next. The previous reference in the new element will point to the element (5) that now precedes it in the list. The time complexity of this operation is O(1), since we only need link to the last element, and as you'll remember, the LinkedList object has a direct reference to the tail, and accessing it has minimal constant time complexity. 2. add(<Index>, <Element>) — adds an element by index. When adding an element, let's say, in the middle of a list, this method first iterates over the elements from the head and tail (on both directions) until the desired place is found. If we add an element between the third and fourth element (in the picture above), then the next link of the third element will point to the new element. And the previous of the newly added element will point to the third one. In turn, the old fourth element's previous link will now point to the new element, and the new element's next link will point to the new fourth element: Exploring questions and answers from a job interview for a Java developer position. Part 9 - 7 The time complexity of this method depends on the index of the new element:
  • if it is close to the head or tail, the operation will approach O(1), since it will not actually be necessary to iterate over the elements;
  • if it is close to the middle, then we will have O(N/2), since the method will search from the head and tail at the same time until the desired element is found.
3. set(<Index>, <Element>) — writes an element to the specified position in the list. The time complexity of this operation will range from O(1) to O(N/2), again depending on how close the new element is to the head, tail, or middle. 4. remove(<index>) — removes an element from the list by making it so that the element before the deleted one (previous) now refers to the element after the deleted one (next). And vice versa, i.e. the element after the deleted one now refers to the one before the deleted one: Exploring questions and answers from a job interview for a Java developer position. Part 9 - 8This process is the opposite of adding by index (add(<Index>, <Element>)).

88. What is the internal structure of a HashMap?

This may be one of the most popular interview questions to ask Java developer candidates. A HashMap works with key-value pairs. How are they stored inside the HashMap itself? A HashMap has an internal array of nodes:

Node<K,V>[] table
By default, the size of the array is 16, and it doubles each time it is filled with elements (that is, when the LOAD_FACTOR is reached; it specifies the threshold for how full the array can get — by default, it is 0.75). Each of the nodes stores a hash of the key, the key, a value, and a reference to the next element: Exploring questions and answers from a job interview for a Java developer position. Part 9 - 9In this case, the "reference to the next element" means that we're dealing with a singly-linked list, where each element contains a link to the next. In other words, a HashMap stores its data in an array of singly-linked lists. But let me say right away that when a cell of the table array has a singly-linked list that consists of more than one element, that is not good. This phenomenon is called a collision. But first things first. Let's see how a new pair is saved using the put method. First, the method gets the key's hashCode(). This implies that in order for a HashMap to work correctly, the keys you use must be classes that override this method. This hash code is then used in the internal hash() method to determine an index of some cell within the table array. The resulting index allows us to access a specific cell of the table array. We have two cases here:
  1. The cell is empty — in this case, the new Node value is stored in it.
  2. The cell is not empty — in this case, the values of the keys are compared. If they are equal, then the new Node value overwrites the old one; if not equal, then the next is accessed, and its key is compared... And so on, until the new value either overwrites some old value or we reach the end of the singly linked list and then store the new value there as the last element.
When searching for an element by key (using the get(<key>) method), the key's hashCode() is calculated, and then its index within the array is calculated using hash(). The resulting number is the index of a cell in the table array, which we then search by iterating over nodes and comparing the key of the desired node with the key of the current node. Ideally, Map operations have an algorithmic complexity of O(1), because we're accessing an array, and, as you will remember, is O(1), regardless of the number of elements it contains. But we're not dealing with the ideal case. When the cell is not empty (2) and already stores some nodes, then the algorithmic complexity becomes O(N) (linear), because now it is necessary to iterate over the elements before we find the right place. I can't help but mention that starting in Java 8, if a node in the form of a singly-linked list has more than 8 elements (collisions), then it gets converted into a binary tree. In this case, the algorithmic complexity is no longer O(N), but O(log(N)) — and that's a whole other matter, isn't it? Exploring questions and answers from a job interview for a Java developer position. Part 9 - 10HashMap is a big topic, and people love to ask questions about it in job interviews. So, I suggest that you know it like the back of your hand. Personally, I have never had an interview that did not include questions on HashMap. That's all for today. To be continued... Exploring questions and answers from a job interview for a Java developer position. Part 9 - 11
Read more:
Comments
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION