Lo que podrían preguntar en una entrevista: Estructuras de datos en Java. Parte 1

¡Hola! No importa cómo se mire, no puede convertirse en desarrollador sin aprobar con éxito una entrevista técnica de ingreso. Hay muchas tecnologías relacionadas con Java y es imposible aprenderlas todas. Como regla general, durante las entrevistas se pregunta algo específico solo si se busca un desarrollador con buena experiencia en algún ámbito importante para el proyecto. Si esto es así, serás perseguido por este marco a toda velocidad, no tienes ninguna duda. Pero ahora hablamos de la base que todo desarrollador de Java debería conocer. Sobre ese conocimiento clásico desde el que comienza todo. Hoy me gustaría abordar uno de los temas fundamentales de cualquier entrevista: las estructuras de datos en Java . Entonces, en lugar de andar con rodeos, comencemos. Encuentre una lista de preguntas que le podrían hacer sobre este tema durante una entrevista.

1. Cuéntanos un poco sobre las estructuras de datos.

Una estructura de datos es un almacén de datos que contiene información estructurada de cierta manera. Estas estructuras están diseñadas para la realización eficiente de determinadas operaciones. Ejemplos típicos de estructuras de datos son:

• matrices,
• pilas,
• colas,
• listas relacionadas,
• gráficos,
• árboles,
• árboles de prefijo,
• tabla de picadillo.

Puedes saber más sobre ellos aquí y aquí . Los datos son un componente clave en un programa y las estructuras permiten que estos datos se almacenen en una forma específica y claramente estructurada. Haga lo que haga tu aplicación, este aspecto siempre estará presente en ella: si es una tienda web se almacenará información sobre productos, si es una red social, datos sobre usuarios y archivos, etc.

2. ¿Qué sabes sobre las matrices?

Una matriz es un contenedor para almacenar valores del mismo tipo, cuyo número se ha especificado de antemano. Un ejemplo de creación de una matriz con valores de cadena:

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

Al crear una matriz, se asigna memoria para todos sus elementos: cuantas más celdas para los elementos se especifiquen inicialmente, más memoria se asignará. Si se crea una matriz vacía con un cierto número de celdas, a todos los elementos de la matriz se les asignarán valores predeterminados. Por ejemplo:

int[] arr = new int[10];

Entonces, para una matriz con elementos de tipo booleano , los valores iniciales ( predeterminados ) serán falsos , para matrices con valores numéricos - 0, con elementos de tipo char - \u0000 . Para una matriz de tipo de clase (objetos): nulo (no cadenas vacías, "" pero específicamente nulo ). Es decir, en el ejemplo anterior, todos los valores de la matriz arr serán 0 hasta que se especifiquen directamente. A diferencia de las colecciones, las matrices no son dinámicas. Una vez que se declara una matriz de cierto tamaño, el tamaño en sí no se puede cambiar. Para agregar un nuevo elemento a una matriz, necesita crear una nueva matriz más grande y copiar todos los elementos de la anterior en ella (así es como funciona ArrayList). Hay un punto que no todo el mundo conoce y en el que te pueden pillar bastante bien. Hay dos tipos de variables en Java: tipos simples y referencias a objetos completos. ¿Cuáles de estos son arreglos? Por ejemplo, aquí:

int[] arr = new int[10];

Parece que todo es simple: son 10 elementos int . Entonces, ¿podemos decir que este es un tipo simple? No importa cómo sea. En Java, las matrices son objetos creados dinámicamente y pueden asignarse a variables de tipo Objeto. Todos los métodos de la clase Object se pueden llamar en una matriz. Entonces incluso podemos escribir:

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

Al enviar a la consola, es posible que obtenga algo como: Lea más sobre las características de las matrices en Java en este artículo sobre Java Array . Para consolidar tus conocimientos, puedes resolver varios problemas de esta colección .

3. Explicar la jerarquía de las colecciones.

Las colecciones se utilizan en situaciones en las que se necesita flexibilidad al trabajar con datos. Las colecciones pueden agregar un elemento, eliminar un elemento y realizar muchas otras operaciones. Hay muchas implementaciones diferentes en Java y solo necesitamos elegir la colección adecuada para la situación actual. Normalmente, cuando menciona la interfaz Colección , se le pide que enumere algunas de sus implementaciones y su relación con Mapa . Bueno, averigüémoslo. Entonces, Colección y Mapa son dos jerarquías diferentes para estructuras de datos. Cómo se ve la jerarquía de la Colección : La interfaz de la Colección es el enlace superior clave con una lista de métodos básicos, a partir de los cuales se originan tres tipos básicos de estructuras de datos: Conjunto , Lista , Cola . Set<T> es una interfaz que representa una colección de objetos en la que cada objeto es único. List<T> es una interfaz que representa una secuencia ordenada de objetos llamada lista. Queue<T> es una interfaz responsable de estructuras que se organizan como una cola (almacenamiento secuencial de elementos). Como se mencionó anteriormente, Map es una jerarquía separada: Map<K, V> es una interfaz que representa un diccionario en el que los elementos están contenidos como pares clave-valor. Además, todas las claves (K) son únicas dentro del objeto Mapa . Este tipo de colección hace que sea más fácil encontrar un elemento si conocemos la clave, el identificador único del objeto.

4. ¿Qué sabes sobre Set?

Como se indicó anteriormente, esta colección presenta muchos elementos únicos. En otras palabras, el mismo objeto no puede aparecer más de una vez en un Java Set . También me gustaría señalar que no podemos extraer un elemento de un conjunto por número (índice), solo mediante fuerza bruta. Lo importante es que las diferentes implementaciones de Set tienen diferentes formas de estructurar los datos. Consideraremos implementaciones específicas más a fondo. Entonces, las principales implementaciones de Set : HashSet es un conjunto que se basa en una tabla hash, que a su vez ayuda con la búsqueda. Utiliza una función hash que mejora el rendimiento durante las búsquedas e inserciones. Independientemente del número de elementos, en general, la inserción y la búsqueda (a veces la eliminación) se realizan en un tiempo casi constante: O(1). Veremos la función hash con más detalle un poco más adelante. También me gustaría señalar que HashSet contiene un HashMap , que es donde ocurre toda la magia. Aquí hay un artículo detallado sobre HashSet en Java . LinkedHashSet : esta clase extiende HashSet sin agregar ningún método nuevo. Al igual que LinkedList , esta clase mantiene una lista enlazada de los elementos de un conjunto en el orden en que fueron insertados. Esto le permite organizar el orden necesario en una implementación determinada de Set . La clase TreeSet crea un conjunto basado en un árbol rojo-negro para organizar la estructura de almacenamiento de elementos. En otras palabras, en un conjunto determinado podemos ordenar los elementos en orden ascendente. Si utilizamos algunos objetos estándar del "cuadro", por ejemplo, Integer , entonces no necesitamos hacer nada para organizar el conjunto de Integers en orden ascendente:

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

System.out.println(set);

Y en la consola obtendremos el resultado: Es decir, en este conjunto los números se almacenan ordenados. Si usamos elementos String en un TreeSet , estarán ordenados, pero alfabéticamente. Bueno, ¿y si tenemos alguna clase estándar (personalizada)? ¿ Cómo estructurarán los objetos de esta clase el TreeSet ? Si intentamos asignar un objeto arbitrario a este Conjunto :

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);

Recibiremos una ClassCastException porque TreeSet no sabe cómo ordenar objetos de este tipo. En este caso, necesitamos nuestro objeto personalizado para implementar la interfaz Comparable y su método compareTo :

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 + '\'' +
               '}';
   }
}

Como habrás notado, el método compareTo devuelve un int :

• 1 si el objeto actual (este) se considera grande;
• -1 si el objeto actual se considera más pequeño que el que vino como argumento;
• 0 si los objetos son iguales (no usamos esto en este caso).

En este caso, nuestro TreeSet funcionará correctamente y mostrará el resultado: Otra forma es crear una clase de clasificación separada que implemente la interfaz del comparador y su método de comparación :

public class CatComparator implements Comparator {

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

En este caso, para usarlo, debemos asignar un objeto de esta clase al constructor TreeSet :

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

Después de esto, todos los objetos de la clase Cat que están incluidos en TreeSet se ordenarán utilizando la clase Cat Comparator . Puede obtener más información sobre Comparator y Comparable en Java en este artículo .

5. Cuéntanos sobre la cola

La cola es una interfaz responsable de las estructuras que se organizan como una cola: una estructura de datos que almacena elementos de forma secuencial. Por ejemplo, de una cola de personas, la primera persona en entrar será la que llegó antes que los demás, y la última será la que llegó más tarde que los demás. Este método se llama FIFO , es decir, primero en entrar, primero en salir . Los métodos de cola únicos se centran en trabajar con el primer o último elemento, por ejemplo:

• agregar y ofrecer : inserta un elemento al final de la cola,
• eliminar : recupera y elimina el encabezado de esta cola,
• peek: recupera pero no elimina el encabezado de la cola.

PARTE 2