Interview Questions: Java Data Structures. Part 1

Hello! Like it or not, you won't become a developer without successfully passing the entrance technical interview. There are a lot of technologies related to Java, and it is impossible to learn everything. Something specific, as a rule, is only asked at interviews if they are looking for a developer with good experience in some important framework for the project. If so, you will be driven around this framework in full growth, you have no doubt. But we are now talking about the basics that every Java developer should know. About those classical knowledge with 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, we'll get started. Catch a list of questions that you may be asked about this topic in 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 tailored for the efficient execution of certain operations. Typical examples of data structures are:

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

More details about them can be found here and here . Data is a key component in a program, while structures allow you to store this data 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 was set 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 the elements are initially set, the more memory will be allocated. If an empty array is created with some number of cells, then all array elements 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 equal to 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 — “” namely null ). That is, in the example above, all values ​​of the array arrwill 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 well caught. There are two kinds of variables in Java - simple types and full object references . Which of these are arrays? For example, here:

int[] arr = new int[10];

Everything seems to be simple - these are 10 int elements . It turns out, we can say that this is a simple type? No matter how. 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 can get something like: For more information about the features of arrays in Java, see this article on Java Array . To consolidate knowledge, you can solve several problems from this collection .

3. Talk about 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 the relationship with Map . Well, let's figure it out. So, Collection and Map are two different hierarchies for data structures. What the Collection hierarchy looks like : The Collection interfaceis a 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 is 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 (consecutive storage of elements). As mentioned earlier, Map is a separate hierarchy: Map<K, V>- an interface representing a dictionary in which elements are contained in the form of key-value pairs. In this case, 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 mentioned earlier, this collection represents many unique items. In other words, the same object cannot appear more than once in a Java Set . We would also like to indicate that we cannot extract an element from a Set by number (index) - only by enumeration. The important thing is that different Set implementations have different ways of structuring data. We will consider specific implementations below. So, the main implementations of Set : HashSet- a set that is based on a hash table, which in turn helps with the search. Uses a hash function that improves lookup and insertion performance. Regardless of the number of elements, in general, insertion and search (sometimes deletion) are performed in time close to a constant - O (1). We will learn more about the hash function a little later. I would also like to note that the HashSet contains a HashMap , in which all the magic happens. Here is a detailed article on HashSet in Java . LinkedHashSet - This class extends HashSet without adding any new methods. Like LinkedList, this class maintains a linked list of the set's elements 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 storage structure of 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 build a 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 get the output: That is, in this set, the numbers are stored in sorted form. If we use the String elements in the TreeSet , they will be sorted, but alphabetically. Well, what if we have some standard (custom) class? How will the objects of this class structure the TreeSet ? If we try to assign an arbitrary object to a given 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'll get a ClassCastException since the TreeSet doesn't 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 that 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 specify an object of this class in the TreeSet constructor :

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

After that, all objects of the Cat class that are 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. Talk 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 the queue of people, the person who came earlier than the others will go first, the last one will be the one who came later than everyone else. This method is called - FIFO , that is, First in First Out . Queue unique methods are designed to work 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