Kotlin para entrevistas – Parte 5: Fragmentos de código de uso frecuente | de Sherry Yuan | Noviembre de 2020

Foto de Fabrice Villard en Unsplash

Esta es la parte 5 de Kotlin para entrevistas, una serie en la que miro las funciones de Kotlin y los fragmentos de código que han aparecido a menudo durante la preparación de mi entrevista de Android. También he compilado una hoja de referencia que cubre las 5 partes de esta serie, que puede encontrar aquí.

Puede encontrar la Parte 1: Tipos de datos comunes aquí, la Parte 2: Recopilar funciones aquí, la Parte 3: Números y matemáticas aquí, y la Parte 4: Iteración aquí.

Esta parte cubre:

Veremos bloques de código que me he encontrado usando con frecuencia para muchos problemas diferentes. Por ejemplo, muchos problemas de entrevistas se reducen a una búsqueda en profundidad, y he utilizado variaciones del fragmento de código de búsqueda en profundidad para resolverlos.

Para muchos problemas de gráficos, se le dará una lista de pares de nodos, donde el segundo nodo depende del primer nodo (o viceversa, según el entrevistador). Por ejemplo, una pareja que se parece [0, 1] significa que para visitar el nodo 1 primero debe visitar 0. Sin embargo, la mayoría de los algoritmos de gráficos requieren una representación de lista de adyacencia, por lo que aquí hay un algoritmo que toma una lista de pares de nodos y la convierte en una lista de adyacencia .

Dada esta entrada de ejemplo:

[[1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [3, 6], [4,6], [4, 7], [5, 4], [5, 7]]

Lo que representa este gráfico:

Queremos crear la siguiente lista de adyacencia:

[[1: [2, 4, 3]] [2: [4, 5]] [3: [6]] [4: [6, 7, 3]] [5: [4, 7]] [7: [6]]]

Tenga en cuenta que este algoritmo es para gráficos directos. Si le dicen que la gráfica no está orientada, ese es el par [0, 1] solo significa que 0 y 1 tienen un borde entre ellos, simplemente repita el código en el archivo forEach() bucle con pair[0] es pair[1] intercambiado, por lo que el MutableLists en el gráfico representan todos los nodos adyacentes en lugar de solo dependencias directas.

Muchos problemas de entrevistas requieren atravesar gráficos: desde encontrar un nodo hasta verificar bucles y encontrar la longitud de una ruta entre dos nodos. Buscar en amplitud es una forma de hacer esto. El algoritmo comienza desde un nodo en el gráfico y, con la ayuda de una cola, explora todos los nodos cercanos a la profundidad actual antes de pasar a los nodos del siguiente nivel de profundidad.

Aquí hay una versión básica que atraviesa todos los nodos accesibles por el primero. Puede cambiarlo según el problema del gráfico que esté resolviendo.

La primera búsqueda profunda también se puede utilizar para problemas de cruce de gráficos. El algoritmo utiliza una pila en lugar de una cola y escanea la rama del nodo actual tanto como puede antes de verse obligado a retroceder y expandirse a otros nodos.

Aquí hay una versión recursiva que se basa en una pila de llamadas de función en lugar de una variable de pila explícita. También puede escribir una versión iterativa del algoritmo utilizando una variable de pila.

Los problemas con los árboles son muy comunes en las entrevistas. Algunos ejemplos buscan el ancestro común más bajo de dos nodos, la suma de los valores de todos los nodos en un árbol, etc.

Árbol binario

Los árboles binarios son el árbol más común con el que se encontrará en las entrevistas. Un nodo para un árbol binario se verá así:

Tenga en cuenta que no todos los árboles binarios son árboles de búsqueda binarios y no debe asumir que se le asignó un BST a menos que su entrevistador lo confirme. Un árbol binario es un BST solo si también cumple con los siguientes criterios:

  • El subárbol izquierdo de un nodo contiene solo nodos con claves menores que la clave del nodo.
  • El subárbol derecho de un nodo contiene solo nodos con claves mayores que la clave del nodo.
  • El subárbol izquierdo y derecho también debe ser un árbol de búsqueda binario.

Usemos este árbol (que no es una BST) como ejemplo:

Puedes construirlo usando el siguiente código:

Así es como se vería un cruce de pedido anticipado:

Así es como se vería un cruce en orden:

Así es como se vería un crossover posterior a la orden:

Árbol con varios hijos

También puede encontrar árboles que tengan una matriz de elementos secundarios en lugar de nodos izquierdo y derecho. Un ejemplo de esta estructura de datos sería la jerarquía de vistas de Android, donde cada vista puede tener varios hijos.

En este caso, tendría que llamar recursivamente a su función en todos los niños y el código se vería así:

Siempre que se encuentre con un algoritmo recursivo que tenga llamadas repetidas con las mismas entradas, probablemente pueda ajustarlo usando programación dinámica. La idea es almacenar los resultados de los subproblemas en una tabla para que no tenga que volver a calcularlos cuando sea necesario más adelante. Esto reduce la complejidad del tiempo de exponencial a polinomio. Se puede implementar mediante iteración o recursividad.

Iteración

Empecemos por el más pequeño i y complete la tabla de resultados desde allí. Cualquier subproblema que necesitemos para la iteración actual ya debería estar resuelto. En la iteración final, resolvemos i=n y devolver ese resultado.

Recursividad

Empecemos por i = n. Si los resultados de los subproblemas que necesitamos para la iteración actual ya existen en la tabla de resultados, podemos usarlos. Si no, llamaremos a la función de forma recursiva para resolverlos y almacenar los resultados.

Y ese es el final de la serie Kotlin for Interview. Aquí está el enlace a la hoja de trucos que cubre las 5 partes nuevamente. ¡Buena suerte con tus entrevistas!

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *