Explorando preguntas y respuestas de una entrevista de trabajo para un puesto de desarrollador de Java. parte 9

Ser programador no es fácil. Siempre hay algo nuevo que aprender. Y, como en cualquier otro emprendimiento, lo más difícil es empezar, dar el primer paso hacia tu objetivo. Pero como ya estás aquí y leyendo este artículo, has completado el primer paso. Esto significa que ahora debes avanzar deliberadamente hacia tu objetivo, sin reducir la velocidad ni desviarte hacia un lado. Supongo que tu objetivo es convertirte en desarrollador de Java o reforzar tus conocimientos si ya lo eres. Si es así, continuemos abordando una lista extensa de preguntas de la entrevista para desarrolladores de Java. ¡Continuemos!

Colecciones

84. Cuéntanos sobre los iteradores y cómo se utilizan.

Las colecciones son un tema favorito en cualquier entrevista con un desarrollador de Java. Cuando responden preguntas sobre la jerarquía de la colección, los candidatos suelen decir que comienza con la interfaz de la colección . Pero esto no es así. Hay otra interfaz un nivel arriba: Iterable . Esta interfaz consta del método iterator() , que le permite acceder al objeto Iterator de la colección actual. ¿Y qué es exactamente este objeto Iterador ? El objeto Iterador proporciona la capacidad de moverse a través de una colección e iterar sobre sus elementos, y el usuario no necesita conocer los detalles de implementación específicos de la colección. En otras palabras, es una especie de puntero a los elementos de la colección, como si estuviera asomándose al interior de uno de ellos. El iterador tiene métodos como:

• hasNext() — devuelve verdadero si la iteración tiene otro elemento (este método te permite saber cuando has llegado al final de la colección);

• next() : devuelve el siguiente elemento de la iteración. Si no hay ninguna, se lanza una NoSuchElementException . Eso significa que antes de usar este método, es mejor usar el método hasNext() para asegurarse de que exista el siguiente elemento;

• remove() : elimina de la colección el último elemento recibido usando el método next() . Si nunca se ha llamado a next() , entonces llamar a remove() provocará que se genere una excepción IllegalStateException ;

• forEachRemaining(<Consumer>) — ejecuta la acción pasada en cada elemento de la colección (este método apareció en Java 8).

A continuación se muestra un pequeño ejemplo de cómo iterar a través de una lista y eliminar todos sus elementos utilizando los diversos métodos de iteración que analizamos:

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

La consola mostrará lo siguiente: Esto significa que los elementos se eliminaron con éxito. Una vez que obtenga un iterador, puede usar un método para mostrar todos los elementos en la pantalla:

iterator.forEachRemaining(x -> System.out.print(x));

Pero una vez que hacemos esto, el iterador deja de ser adecuado para su uso posterior: ha recorrido toda la lista y un iterador ordinario no tiene métodos para iterar hacia atrás. Y eso constituye una buena transición a una discusión sobre LinkedList , específicamente, su método listIterator() , que devuelve un tipo mejorado de iterador: ListIterator . Además de los métodos de un iterador normal (estándar), este tipo tiene lo siguiente:

• add(<Element>) — agrega un nuevo elemento a la lista;

• hasPrevious() — devuelve verdadero si hay un elemento ubicado antes del siguiente elemento (si hay un elemento anterior);

• nextIndex() — devuelve el índice del siguiente elemento;

• anterior() — devuelve el elemento anterior (el que está antes del siguiente elemento);

• anteriorIndex devuelve el índice del elemento anterior.

• set(<Element>) — reemplaza el último elemento devuelto por next() o anterior() .

Como puede ver, este iterador tiene una funcionalidad mucho más interesante: le permite caminar en ambas direcciones y proporciona una libertad considerable al trabajar con elementos. También debes saber que cuando la gente habla de iteradores, a veces se refieren al patrón de diseño en sí.

85. ¿Qué jerarquía de colección existe en Java Collection Framework?

Hay dos jerarquías de colecciones en Java. La primera jerarquía es la jerarquía de Colección, la cual tiene la siguiente estructura: Se divide en las siguientes subcolecciones:

• Set es una interfaz que describe un conjunto, una estructura de datos que contiene elementos únicos (no repetidos) desordenados. Esta interfaz tiene algunas implementaciones estándar: TreeSet , HashSet y LinkedHashSet .

• Lista es una interfaz que describe una estructura de datos que almacena una secuencia ordenada de objetos. Los objetos en una Lista se pueden insertar y eliminar según su índice en la lista (como una matriz, pero con cambio de tamaño dinámico). Esta interfaz también tiene algunas implementaciones estándar: ArrayList , Vector ( en desuso y no se usa realmente ) y LinkedList .

• La cola es una interfaz que describe una estructura de datos que almacena elementos en una cola Primero en entrar, primero en salir (FIFO) . Esta interfaz tiene las siguientes implementaciones estándar: LinkedList (así es, también implementa Queue ) y PriotityQueue .

La segunda jerarquía de colección es la jerarquía de Mapa , que tiene la siguiente estructura: Esta jerarquía de colección no tiene divisiones en subcolecciones (ya que la jerarquía de Mapa en sí es una especie de subcolección que se distingue por sí sola). Las implementaciones estándar de Map son Hashtable (en desuso), LinkedHashMap y TreeMap . En la práctica, cuando la gente pregunta sobre Colecciones , normalmente se refieren a ambas jerarquías.

86. ¿Cuál es la estructura interna de un ArrayList?

Una ArrayList es como una matriz, pero puede expandirse dinámicamente. ¿Qué significa eso? En esencia, ArrayList utiliza una matriz ordinaria, es decir, almacena sus elementos en una matriz interna cuyo tamaño predeterminado es 10 celdas. Una vez que la matriz interna está llena, se crea una nueva matriz. El tamaño de la nueva matriz está determinado por esta fórmula:

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

Entonces, si el tamaño de nuestra matriz es 10, entonces el tamaño de la nueva será: 10 * 3 / 2 + 1 = 16. Luego, todos los valores de la matriz original (antigua) se copian en ella usando el software incorporado. Método System.arraycopy() y se elimina la matriz original. En pocas palabras, así es como ArrayList implementa el cambio de tamaño dinámico. Consideremos los métodos ArrayList más populares : 1. add(<Element>) — agrega un elemento al final de la matriz (en la última celda vacía), después de verificar primero si hay una celda disponible en la matriz. De lo contrario, se crea una nueva matriz y los elementos se copian en ella. La complejidad temporal de esta operación es O (1). Existe un método add(<Index>, <Element>) similar . Agrega un elemento no al final de la lista (matriz), sino a la celda específica indicada por el índice que entró como argumento. En este caso, la complejidad del tiempo variará dependiendo de dónde agregue:

• si el complemento está cerca del comienzo de la lista, entonces la complejidad temporal será cercana a O(N), porque todos los elementos ubicados a la derecha del nuevo tendrán que moverse una celda hacia la derecha;
• si el elemento se inserta en el medio, entonces será O(N/2), ya que solo necesitamos desplazar la mitad de los elementos de la lista una celda hacia la derecha.

Es decir, la complejidad temporal de este método varía de O(1) a O(N), dependiendo de dónde se inserte el elemento. 2. set(<Índice>, <Elemento>) : escribe un elemento en la posición especificada de la lista. Si un elemento ya está presente en esa posición, el método lo sobrescribe. La complejidad temporal de esta operación es O(1), porque no implica ninguna operación de desplazamiento: simplemente usamos el índice para calcular la dirección de la celda en la matriz, que tiene complejidad O(1), y luego escribimos el nuevo elemento. . 3. remove(<index>) : elimina un elemento por su índice en la matriz interna. Al eliminar un elemento que no está al final de la lista, todos los elementos a la derecha del eliminado deben desplazarse una celda hacia la izquierda para cerrar el espacio que resulta de la eliminación. En consecuencia, la complejidad temporal será la misma que para add(<Index>, <Element>) cuando se agrega un elemento en el medio: O(N/2). Después de todo, debes mover la mitad de los elementos una celda hacia la izquierda. Y si hablamos del principio, entonces O(N). O si está al final, entonces O(1), ya que no es necesario mover nada.

87. ¿Cuál es la estructura interna de una LinkedList?

Una ArrayList contiene elementos en la matriz interna, pero una LinkedList los almacena en una lista doblemente enlazada. Esto significa que cada elemento contiene un enlace al elemento anterior y al siguiente . El primer elemento no enlaza con un elemento anterior (al fin y al cabo, es el primero). También se considera el encabezado de la lista y el objeto LinkedList tiene una referencia directa a él. De manera similar, el último elemento no tiene el siguiente elemento, ya que es el final de la lista. El objeto LinkedList también hace referencia a él directamente. Esto significa que la complejidad temporal de acceder al principio o al final de una lista es O (1). En ArrayList , si la lista crece, entonces la matriz interna crece. Aquí todo es más fácil: añadir una referencia es tan sencillo como cambiar un par de enlaces. Veamos algunos de los métodos LinkedList más utilizados: 1. add(<Element>) — agrega un elemento al final de la lista, es decir, después del último elemento (5), se agregará un enlace al nuevo elemento como siguiente . La referencia anterior en el nuevo elemento apuntará al elemento (5) que ahora le precede en la lista. La complejidad temporal de esta operación es O(1), ya que solo necesitamos un enlace al último elemento y, como recordará, el objeto LinkedList tiene una referencia directa a la cola y acceder a él tiene una complejidad temporal mínima y constante. 2. add(<Index>, <Element>) — agrega un elemento por índice. Al agregar un elemento, digamos, en medio de una lista, este método primero itera sobre los elementos desde la cabeza y la cola (en ambas direcciones) hasta encontrar el lugar deseado. Si agregamos un elemento entre el tercer y cuarto elemento (en la imagen de arriba), entonces el siguiente enlace del tercer elemento apuntará al nuevo elemento. Y el anterior del elemento recién agregado apuntará al tercero. A su vez, el enlace anterior del antiguo cuarto elemento ahora apuntará al nuevo elemento, y el siguiente enlace del nuevo elemento apuntará al nuevo cuarto elemento: La complejidad temporal de este método depende del índice del nuevo elemento:

• si está cerca de la cabeza o la cola, la operación se aproximará a O(1), ya que en realidad no será necesario iterar sobre los elementos;
• si está cerca del medio, entonces tendremos O(N/2), ya que el método buscará desde la cabeza y la cola al mismo tiempo hasta encontrar el elemento deseado.

3. set(<Índice>, <Elemento>) : escribe un elemento en la posición especificada de la lista. La complejidad temporal de esta operación variará de O(1) a O(N/2), nuevamente dependiendo de qué tan cerca esté el nuevo elemento de la cabeza, la cola o el medio. 4. remove(<index>) : elimina un elemento de la lista haciendo que el elemento anterior al eliminado ( anterior ) ahora se refiera al elemento posterior al eliminado ( siguiente ). Y viceversa, es decir, el elemento después del eliminado ahora se refiere al anterior al eliminado: este proceso es lo opuesto a agregar por índice ( add(<Index>, <Element>) ).

88. ¿Cuál es la estructura interna de un HashMap?

Esta puede ser una de las preguntas de entrevista más populares para los candidatos a desarrolladores de Java. Un HashMap funciona con pares clave-valor . ¿ Cómo se almacenan dentro del propio HashMap ? Un HashMap tiene una matriz interna de nodos:

Node<K,V>[] table

De forma predeterminada, el tamaño de la matriz es 16 y se duplica cada vez que se llena con elementos (es decir, cuando se alcanza LOAD_FACTOR ; especifica el umbral de cuán llena puede llegar a ser la matriz; de forma predeterminada, es 0,75 ). . Cada uno de los nodos almacena un hash de la clave, la clave, un valor y una referencia al siguiente elemento: en este caso, la "referencia al siguiente elemento" significa que estamos tratando con una lista enlazada individualmente, donde cada elemento contiene un enlace al siguiente. En otras palabras, un HashMap almacena sus datos en una serie de listas enlazadas individualmente. Pero permítanme decirles de inmediato que cuando una celda de la matriz de la tabla tiene una lista enlazada individualmente que consta de más de un elemento, eso no es bueno. Este fenómeno se llama colisión . Pero primero lo primero. Veamos cómo se guarda un nuevo par usando el método put . Primero, el método obtiene el hashCode() de la clave . Esto implica que para que un HashMap funcione correctamente, las claves que utilice deben ser clases que anulen este método. Este código hash luego se usa en el método interno hash() para determinar un índice de alguna celda dentro de la matriz de la tabla. El índice resultante nos permite acceder a una celda específica de la matriz de la tabla. Tenemos dos casos aquí:

1. La celda está vacía; en este caso, el nuevo valor del Nodo se almacena en ella.
2. La celda no está vacía; en este caso, se comparan los valores de las claves. Si son iguales, entonces el nuevo valor de Nodo sobrescribe el anterior; si no es igual, se accede al siguiente y se compara su clave... Y así sucesivamente, hasta que el nuevo valor sobrescribe algún valor antiguo o llegamos al final de la lista enlazada individualmente y luego almacenamos el nuevo valor allí como último elemento.

Al buscar un elemento por clave (usando el método get(<key>) ), se calcula el hashCode() de la clave y luego su índice dentro de la matriz se calcula usando hash() . El número resultante es el índice de una celda en la matriz de la tabla , que luego buscamos iterando sobre los nodos y comparando la clave del nodo deseado con la clave del nodo actual. Idealmente, las operaciones de mapa tienen una complejidad algorítmica de O(1), porque estamos accediendo a una matriz y, como recordarás, es O(1), independientemente de la cantidad de elementos que contenga. Pero no estamos ante el caso ideal. Cuando la celda no está vacía (2) y ya almacena algunos nodos, entonces la complejidad algorítmica se vuelve O(N) (lineal), porque ahora es necesario iterar sobre los elementos antes de encontrar el lugar correcto. No puedo evitar mencionar que a partir de Java 8, si un nodo en forma de lista enlazada individualmente tiene más de 8 elementos (colisiones), se convierte en un árbol binario. En este caso, la complejidad algorítmica ya no es O(N), sino O(log(N)), y ese es otro asunto, ¿no? HashMap es un tema importante y a la gente le encanta hacer preguntas al respecto en las entrevistas de trabajo. Así que te sugiero que lo conozcas como la palma de tu mano. Personalmente, nunca he tenido una entrevista que no incluyera preguntas sobre HashMap . Eso es todo por hoy. Continuará...