Análisis de preguntas y respuestas de entrevistas para desarrollador Java. parte 9

¡Fuegos artificiales! Ser programador no es fácil. Necesitas aprender constantemente, siempre aprender algo nuevo. Pero, como en cualquier otro negocio, lo más difícil es empezar, dar el primer paso hacia tu objetivo. Y como está sentado en este sitio y leyendo este artículo, ha completado el primer paso. Esto significa que ahora debes avanzar con determinación hacia tu objetivo, sin reducir la velocidad ni desviarte en el camino. Si entiendo correctamente, su objetivo es convertirse en desarrollador de Java o mejorar sus conocimientos, si lo es. Si es así, entonces estás en el lugar correcto, porque continuaremos analizando una lista extensa de más de 250 preguntas de entrevistas para desarrolladores de Java. ¡Continuemos!

Colecciones

84. Cuéntanos sobre los iteradores y su uso.

Las colecciones son uno de los temas favoritos en cualquier entrevista con un desarrollador de Java y, cuando hablan de la jerarquía de colecciones, los candidatos suelen decir que comienza con la interfaz de la Colección . Pero esto no es cierto, porque encima de esta interfaz hay otra: Iterable . Esta interfaz representa el método iterator() , que le permite llamar a un objeto Iterator para la colección actual. ¿Y qué es exactamente este objeto Iterador ? Un iterador es un objeto que brinda la capacidad de moverse a través de una colección e iterar sobre elementos sin que el usuario necesite conocer la implementación de una colección en particular. Es decir, se trata de una especie de puntero a los elementos de la colección, que, por así decirlo, mira a un lugar determinado de la misma. El iterador tiene los siguientes métodos:

• hasNext() : devuelve verdadero si hay un elemento ubicado después del puntero (este método le permite saber si se ha llegado al final de la colección);
• next() : devuelve el siguiente elemento después del puntero. Si no hay ninguno, se lanza NoSuchElementException . Es decir, antes de utilizar este método, es mejor asegurarse de que el elemento exista, utilizando hasNext() ;
• remove() : elimina el último elemento recibido de la colección usando el método next() . Si nunca se ha llamado a next() antes de llamar a remove() , se generará una excepción: IllegalStateException ;
• forEachRemaining(<Consumer>) : realiza la acción pasada con cada elemento de la colección (el método apareció en Java 8).

Aquí hay un pequeño ejemplo de cómo iterar a través de una lista y eliminar todos sus elementos usando los métodos de iterador discutidos:

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á: Esto significa que la eliminación de elementos fue exitosa. Una vez que tuviéramos un iterador, podríamos usar un método para imprimir todos los elementos en la pantalla:

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

Pero después de esto, el iterador dejaría de ser adecuado para su uso posterior, ya que atravesaría toda la lista y un iterador normal no tiene métodos para retroceder. Aquí nos acercamos gradualmente a LinkedList , es decir, a su método listIterator() , que devuelve un tipo de iterador modernizado: ListIterator . Además de los métodos iteradores habituales (estándar), este tiene otros adicionales:

• add(<Elemento>) - inserta un nuevo elemento en la lista;
• hasPrevious() - devuelve verdadero si hay un elemento ubicado antes del puntero (si hay un elemento anterior);
• nextIndex() : devuelve el índice en la lista del siguiente elemento después del puntero;
• anterior() : devuelve el elemento anterior (hasta el puntero);
• anteriorIndex() - devuelve el índice del elemento anterior;
• set(<Elemento>) : reemplaza el último elemento devuelto por los métodos next() o anterior() .

Como puede ver, la funcionalidad de este iterador es mucho más interesante: le permite moverse en ambas direcciones y libera sus manos al trabajar con elementos. Además, cuando la gente habla de iteradores, a veces se refieren al patrón en sí. Para evitar meterse en problemas y hablar de ello de manera convincente, lea este artículo sobre el patrón Iterador .

85. ¿Cuál es la jerarquía de colecciones en Java Collection Framework?

Hay dos jerarquías de colecciones en Java. La primera jerarquía es la propia jerarquía de Colección con la siguiente estructura: Esta, a su vez, se divide en las siguientes subcolecciones:

• Set es una interfaz que describe dicha estructura de datos como un conjunto que contiene elementos únicos (no repetidos) desordenados. La interfaz tiene implementaciones estándar: TreeSet , HashSet y LinkedHashSet .
• Lista es una interfaz que describe una estructura de datos que almacena una secuencia ordenada de objetos. Las instancias contenidas en una Lista se pueden insertar y eliminar según su índice en esta colección (análogo a una matriz, pero con cambio de tamaño dinámico). La interfaz tiene implementaciones estándar: ArrayList , Vector ( considerada obsoleta y en realidad no utilizada ) y LinkedList .
• La cola es una interfaz que describe una estructura de datos que almacena elementos en forma de cola que sigue la regla FIFO (primero en entrar, primero en salir ). La interfaz tiene las siguientes implementaciones estándar: LinkedList (sí, también implementa Queue ) y PriotityQueue .

La segunda jerarquía de colecciones es Map , que tiene la siguiente estructura: En esta colección no hay divisiones en subcolecciones (ya que la jerarquía Map en sí es algo así como una subcolección, pero se encuentra separada). Las implementaciones de mapas estándar son Hashtable (considerada obsoleta), LinkedHashMap y TreeMap . En realidad, cuando se pregunta sobre Collection , generalmente se hace referencia a ambas jerarquías.

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

ArrayList es similar a una matriz, pero con la capacidad de expandirse dinámicamente. ¿Qué significa? El hecho es que ArrayList funciona sobre la base de una matriz normal, es decir, almacena elementos en una matriz interna (su tamaño predeterminado es 10 celdas). Cuando la matriz interna está llena, se crea una nueva matriz, cuyo tamaño está determinado por la fórmula:

<размерТекущегоМассива> * 3 / 2  + 1

Es decir, si el tamaño de nuestra matriz es 10, el tamaño de la nueva será: 10 * 3 / 2 + 1 = 16. A continuación, todos los valores de la primera (antigua) matriz se copian en ella usando el método nativo System.arraycopy () y se elimina la primera matriz. En realidad, así es como se implementa la extensibilidad dinámica de ArrayList . Veamos los métodos ArrayList más utilizados : 1. add(<Elemento>) : agrega un elemento al final de la matriz (hasta la última celda vacía) y primero verifica si hay espacio en esta matriz. Si no está ahí, se crea una nueva matriz en la que se copian los elementos. La complejidad logarítmica de esta operación es O(1). Existe un método similar: add(<Index>,<Element>) . Agrega un elemento no al final de la lista (matriz), sino a una celda específica con el índice que vino como argumento. En este caso, la complejidad logarítmica diferirá según dónde se agregue:

• si este fuera aproximadamente el comienzo de la lista, la complejidad logarítmica será cercana a O(N), porque todos los elementos ubicados a la derecha de la nueva tendrán que moverse una celda hacia la derecha;
• si el elemento se inserta en el medio - O(N/2) porque Necesitamos mover solo la mitad de los elementos de la lista una celda hacia la derecha.

Es decir, la complejidad logarítmica de este método varía de O(N) a O(1) dependiendo de dónde se inserte el elemento. 2. set(<Índice>,<Elemento>) : escribe un elemento en la posición especificada en la lista. Si ya hay un elemento en esa posición, lo sobrescribe. La complejidad logarítmica de esta operación es O(1), porque no hay desplazamientos: sólo se busca por índice en el array, que, como recordamos, tiene una complejidad de O(1), y se escribe el 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, debe mover todos los elementos a la derecha una celda hacia la izquierda para cerrar el espacio que queda después de eliminar el elemento. Por lo tanto, la complejidad logarítmica será la misma que add(<Index>,<Element>) si el elemento estaba en el medio - O(N/2) - porque necesitas desplazar la mitad de los elementos uno hacia la izquierda. En consecuencia, si fuera al principio - O(N). Bueno, si al final es O(1), no hay necesidad de mover nada. Para quienes quieran profundizar más en este tema, les dejaré este enlace a un artículo con análisis de la clase ArrayList .

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

Si ArrayList contiene elementos en una matriz interna, entonces LinkedList tiene la forma de una lista doblemente enlazada. Esto significa que cada elemento contiene un enlace al elemento anterior ( anterior ) y al siguiente ( siguiente ). El primer elemento no tiene enlace con el anterior (es el primero), pero se considera cabecera de la lista, y la LinkedList tiene enlace directo a él. El último elemento, de hecho, no tiene un elemento siguiente, es el final de la lista y, por lo tanto, hay un enlace directo a él en la propia LinkedList . Por lo tanto, la complejidad logarítmica de acceder al principio o al final de una lista es O (1). En ArrayList, cuando la lista creció, la matriz interna aumentó, pero aquí todo sucede de manera más simple: al agregar un elemento, un par de enlaces simplemente cambian. Veamos algunos de los métodos LinkedlList más utilizados : 1. add(<Element>) - agregar al final de la lista, es decir. después del último elemento (5), se agregará un enlace al nuevo elemento como siguiente . El nuevo elemento tendrá un enlace al último (5) como el elemento anterior . La complejidad logarítmica de dicha operación será O(1), ya que solo se necesita un enlace al último elemento y, como recordará, la cola tiene un enlace directo desde LinkedList y la complejidad logarítmica de acceder a ella es mínima. 2. add(<Índice>,<Elemento>) : agrega un elemento por índice. Al agregar un elemento, por ejemplo, al medio de una lista, los elementos de la cabeza y la cola (en ambos lados) se iteran primero hasta encontrar el lugar deseado. Si queremos insertar un elemento entre el tercero y el cuarto (en la figura de arriba), cuando busquemos el lugar correcto, el siguiente enlace del tercer elemento ya apuntará al nuevo. Para el nuevo, el enlace anterior apuntará al tercero. En consecuencia, el enlace del cuarto elemento ( anterior ) ya apuntará al nuevo elemento, y el siguiente enlace del nuevo elemento apuntará al cuarto elemento: La complejidad logarítmica de este método dependerá del índice dado al nuevo elemento:

• si está cerca de la cabeza o la cola, se aproximará a O(1), ya que en realidad no será necesario iterar sobre los elementos;
• si está cerca del medio, entonces O(N/2): los elementos de la cabeza y la cola se ordenarán simultáneamente hasta que se encuentre el elemento requerido.

3. set(<Índice>,<Elemento>) : escribe un elemento en la posición especificada en la lista. La complejidad logarítmica de esta operación variará de O(1) a O(N/2), nuevamente dependiendo de qué tan cerca esté el elemento de la cabeza, la cola o el medio. 4. remove(<index>) : elimina un elemento de la lista, esencialmente haciendo que el elemento que viene antes del que se elimina ( anterior ) haga referencia al elemento que viene después del que se elimina ( siguiente ). Y viceversa: para que el elemento que viene después del que se elimina se refiere al que viene antes del que se elimina: El resultado es un proceso inverso a la suma por índice ( add(<Index>,<Element>) ). Para aquellos que deseen aprender más sobre la estructura interna de LinkedList , recomiendo leer este artículo .

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

Quizás una de las preguntas más populares al entrevistar a un desarrollador de Java. HashMap v funciona con pares clave-valor . ¿ Cómo se almacenan dentro del propio HashMapv ? Dentro del HashMap hay una serie 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 (cuando se alcanza LOAD_FACTOR , un cierto porcentaje de plenitud, de forma predeterminada es 0,75 ). Cada nodo almacena un hash de la clave, una clave, un valor y un enlace al siguiente elemento: En realidad, "enlazar al siguiente elemento" significa que estamos tratando con una lista enlazada individualmente, donde cada elemento contiene un enlace a el siguiente. Es decir, HashMap almacena datos en una serie de listas enlazadas individualmente. Pero lo señalaré de inmediato: cuando una celda de la matriz de la tabla tiene un enlace a una lista similar de un solo enlace que consta de más de un elemento, esto 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, se toma el hachCode() de la clave. Por lo tanto, para que hashmap funcione correctamente , debe tomar clases en las que este método se anule como claves. Este código hash luego se usa en el método interno, hash() , para determinar el número dentro del tamaño de la matriz de la tabla . A continuación, utilizando el número recibido, se accede a una celda específica de la matriz de la tabla . Aquí tenemos dos casos:

1. La celda está vacía: el nuevo valor del Nodo está almacenado en ella .
2. La celda no está vacía: se compara el valor de las claves. Si son iguales, el nuevo valor del Nodo sobrescribe el anterior, si no son iguales, se accede al siguiente elemento y se compara con su clave... Y así sucesivamente hasta que el nuevo valor sobrescribe alguno antiguo o llega al final del lista enlazada individualmente y se almacenará allí como el último elemento.

Al buscar un elemento por clave ( método get(<key>) ), se calcula el código hash de la clave, luego su valor dentro de la matriz usando hash() , y usando el número resultante, se encuentra la celda de la matriz de la tabla . , en el que la búsqueda ya se realiza enumerando nodos y comparando la clave del nodo deseado con la clave del actual. Las operaciones en Map en una situación ideal tienen una complejidad algorítmica de O(1), porque acceden a una matriz y, como recordará, independientemente del número de elementos, las operaciones en una matriz tienen una complejidad de O(1). Pero esto es ideal. Cuando la celda de la matriz que se utiliza no está vacía (2) y ya hay algunos nodos allí, 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 esto: a partir de Java 8, si un nodo 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 será O(N), sino O(log(N)); esa es otra cuestión, ¿no? HashMap es un tema importante y a la gente le gusta hacer preguntas al respecto en las entrevistas. Por eso, te aconsejo que lo entiendas en detalle (para que rebote en tus dientes). Personalmente, no he tenido una entrevista sin preguntas sobre HashMap . Puede encontrar una inmersión profunda en HashMap en este artículo . Eso es todo por hoy, continuará...