What they might ask at an interview: Data structures in Java. Part 1

Hello! No matter how you look at it, you can’t become a developer without successfully passing a technical entrance interview. There are a lot of technologies related to Java, and it is impossible to learn everything. As a rule, something specific is asked during interviews only if they are looking for a developer with good experience in some framework important for the project. If this is so, you will be chased around this framework at full speed, you have no doubt about it. But now we are talking about the base that every Java developer should know. About that classical knowledge from which it all begins. Today I would like to touch on one of the fundamental topics of any interview - data structures in Java . So, instead of beating around the bush, let's get started. Find a list of questions that you might be asked about this topic during an interview.

1. Tell us a little about data structures

A data structure is a data store that contains information structured in a certain way. These structures are designed for the efficient performance of certain operations. Typical examples of data structures are:

• arrays,
• stacks,
• queues,
• related lists,
• graphs,
• trees,
• prefix trees,
• hash table.

You can find out more about them here and here . Data is a key component in a program, and structures allow this data to be stored in a specific, clearly structured form. Whatever your application does, this aspect will always be present in it: if it is a web store, then information about products will be stored, if it is a social network, data about users and files, and so on.

2. What do you know about Arrays?

An array is a container for storing values ​​of the same type, the number of which has been specified in advance. An example of creating an array with string values:

String[] strArray = {"Java","is","the","best","language"};

When creating an array, memory is allocated for all its elements: the more cells for elements are initially specified, the more memory will be allocated. If an empty array with a certain number of cells is created, then all elements of the array will be assigned default values. For example:

int[] arr = new int[10];

So, for an array with elements of the boolean type, the initial ( default ) values ​​will be false , for arrays with numeric values ​​- 0, with elements of the char type - \u0000 . For an array of class type (objects) - null (not empty strings - “” but specifically null ). That is, in the example above, all values ​​of the arr array will be 0 until they are directly specified. Unlike collections, arrays are not dynamic. Once an array of a certain size is declared, the size itself cannot be changed. To add a new element to an array, you need to create a new larger array and copy all the elements from the old one into it (this is how ArrayList works). There is one point that not everyone knows and on which you can be caught quite well. There are two types of variables in Java - simple types and references to full-fledged objects. Which of these are arrays? For example, here:

int[] arr = new int[10];

It seems that everything is simple - these are 10 int elements . So, we can say that this is a simple type? No matter how it is. In Java, arrays are objects, are dynamically created and can be assigned to variables of type Object. All methods of the Object class can be called on an array. So we can even write:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

When outputting to the console you might get something like: Read more about the features of arrays in Java in this article about Java Array . To consolidate your knowledge, you can solve several problems from this collection .

3. Explain the hierarchy of collections

Collections are used in situations where you need flexibility when working with data. Collections can add an element, remove an element, and perform many other operations. There are many different implementations in Java, and we just need to choose the right collection for the current situation. Typically, when you mention the Collection interface , you are asked to list some of its implementations and its relationship with Map . Well, let's find out. So, Collection and Map are two different hierarchies for data structures. What the Collection hierarchy looks like : The Collection interface is the key top link with a list of basic methods, from which three basic types of data structures originate - Set , List , Queue . Set<T> is an interface that represents a collection of objects in which each object is unique. List<T> is an interface that represents an ordered sequence of objects called a list. Queue<T> is an interface responsible for structures that are organized as a queue (sequential storage of elements). As mentioned earlier, Map is a separate hierarchy: Map<K, V> is an interface representing a dictionary in which elements are contained as key-value pairs. Moreover, all keys (K) are unique within the Map object . This type of collection makes it easier to find an element if we know the key - the unique identifier of the object.

4. What do you know about Set?

As stated earlier, this collection features many unique elements. In other words, the same object cannot appear more than once in a Java Set . I would also like to point out that we cannot extract an element from a Set by number (index) - only by brute force. The important thing is that different Set implementations have different ways of structuring data. We will consider specific implementations further. So, the main implementations of Set : HashSet is a set that is based on a hash table, which in turn helps with searching. Uses a hash function which improves performance during lookups and insertions. Regardless of the number of elements, in general, insertion and search (sometimes deletion) are performed in close to constant time - O(1). We'll look at the hash function in more detail a little later. I would also like to note that the HashSet contains a HashMap , which is where all the magic happens. Here is a detailed article about HashSet in Java . LinkedHashSet - this class extends HashSet without adding any new methods. Like LinkedList , this class maintains a linked list of the elements of a set in the order in which they were inserted. This allows you to organize the necessary order in a given Set implementation . The TreeSet class creates a set that is based on a red-black tree to organize the structure of storing elements. In other words, in a given set we can sort the elements in ascending order. If we use some standard objects from the “box”, for example, Integer , then we don’t need to do anything to arrange the set of Integers in ascending order:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

And in the console we will get the output: That is, in this set the numbers are stored in sorted form. If we use String elements in a TreeSet , they will be sorted, but alphabetically. Well, what if we have some standard (custom) class? How will objects of this class structure the TreeSet ? If we try to assign an arbitrary object to this Set :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

We will receive a ClassCastException because the TreeSet does not know how to sort objects of this type. In this case, we need our custom object to implement the Comparable interface and its compareTo method :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

As you noticed, the compareTo method returns an int :

• 1 if the current (this) object is considered large;
• -1 if the current object is considered smaller than the one that came as an argument;
• 0 if the objects are equal (we don't use this in this case).

In this case, our TreeSet will work correctly and display the result: Another way is to create a separate sorting class that implements the comparator interface and its compare method :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

In this case, to use it, we must set an object of this class to the TreeSet constructor :

TreeSet set = new TreeSet<>(new CatComparator());

After this, all objects of the Cat class that are included in the TreeSet will be sorted using the Cat Comparator class . You can learn more about Comparator and Comparable in Java from this article .

5. Tell us about Queue

Queue is an interface responsible for structures that are organized as a queue - a data structure that stores elements sequentially. For example, from a queue of people, the first person to enter will be the one who arrived earlier than others, and the last one will be the one who arrived later than everyone else. This method is called FIFO , that is, First in First Out . Unique Queue methods focus on working with the first or last element, for example:

• add and offer - inserts an element at the end of the queue,
• remove - retrieves and removes the header of this queue,
• peek - Retrieves but does not remove the queue header.

PART 2