crackingthecodinginterviewes

[crackingthecodinginterviewes]

Big 0

La notación Big O se utiliza en análisis de Algoritmos para medir la eficiencia en términos de tiempo. Se menciona varias veces en el libro y hay que conocerla antes de empezar a resolver preguntas de entrevistas.

[crackingthecodinginterviewes]

9.4.Q

Preguntas de entrevista

4.1 Ruta entre nodos: Dado un gráfico dirigido, diseñe un algoritmo para averiguar si hay un ruta entre dos nodos.

Sugerencias: # 127

4.2 Árbol mínimo: dada una matriz ordenada (orden creciente) con elementos enteros únicos, escriba un algoritmo rithm para crear un árbol de búsqueda binario con una altura mínima.

Sugerencias: # 19, # 73, # 116

4.3 Lista de profundidades: Dado un árbol binario, diseñe un algoritmo que cree una lista vinculada de todos los nodos. en cada profundidad (por ejemplo, si tiene un árbol con profundidad D, tendrá D listas enlazadas).

Sugerencias: # 107, # 123, # 135

4.4 Verificar equilibrado: implemente una función para verificar si un árbol binario está equilibrado. Con el propósito de En esta pregunta, un árbol equilibrado se define como un árbol tal que las alturas de los dos subárboles de cualquier nodo nunca difiere en más de uno.

Sugerencias: # 27, # 33, # 49, # 105, # 124

4.5 Validar BST: Implemente una función para verificar si un árbol binario es un árbol de búsqueda binario

Sugerencias: # 35, # 57, # 86, # 113, # 128

4.6 Sucesor: escriba un algoritmo para encontrar el "siguiente" nodo (es decir, sucesor en orden) de un nodo dado en un árbol de búsqueda binaria. Puede suponer que cada nodo tiene un enlace a su padre.

Sugerencias: # 79, # 91

4.7 Orden de construcción: se le proporciona una lista de proyectos y una lista de dependencias (que es una lista de pares de proyectos, donde el segundo proyecto depende del primer proyecto). Todas las dependencias de un proyecto debe construirse antes que el proyecto. Encuentre un orden de construcción que permita construir los proyectos. Sí hay no es una orden de construcción válida, devuelve un error.

EJEMPLO

Entrada:

proyectos: a, b, c, d, e, f

dependencias: (a, d), (f, b), (b, d), (f, a), (d, c)

Salida: f, e, a, b, d, c

Sugerencias: # 26, # 47, # 60, # 85, # 125, # 133

4.8 Primer antepasado común: diseñe un algoritmo y escriba código para encontrar el primer antepasado común de dos nodos en un árbol binario. Evite almacenar nodos adicionales en una estructura de datos. NOTA: Esto no es necesariamente un árbol de búsqueda binario.

Sugerencias: # 70, # 76, # 28, # 36, # 46, # 70, # 80, # 96

4.9 Secuencias BST: Se creó un árbol de búsqueda binario atravesando una matriz de izquierda a derecha e insertando cada elemento. Dado un árbol de búsqueda binario con elementos distintos, imprima todo lo posible matrices que podrían haber llevado a este árbol.

EJEMPLO

Entrada:

4.1 O Verifique el subárbol: Tl y T2 son dos árboles binarios muy grandes, con Tl mucho más grande que T2. Crear un

algoritmo para determinar si T2 es un subárbol de Tl.

Un árbol T2 es un subárbol de Tl si existe un nodo n en Tl tal que el subárbol de n sea idéntico a T2.

Es decir, si corta el árbol en el nodo n, los dos árboles serían idénticos.

Sugerencias: # 4, # 11, # 18, # 31, # 37

4.11 Nodo aleatorio: está implementando una clase de árbol binario desde cero que, además de

insertar, buscar y eliminar, tiene un método getRandomNode () que devuelve un nodo aleatorio

del árbol. Todos los nodos deberían tener la misma probabilidad de ser elegidos. Diseñar e implementar un algoritmo

para getRandomNode y explique cómo implementaría el resto de los métodos.

Sugerencias: # 42, # 54, # 62, # 75, # 89, # 99, # 112, # 119

4.12 Rutas con suma: se le proporciona un árbol binario en el que cada nodo contiene un valor entero (que

puede ser positivo o negativo). Diseñe un algoritmo para contar el número de caminos que suman un

valor dado. No es necesario que el camino comience o termine en la raíz o en una hoja, pero debe ir hacia abajo.

(viajando solo de los nodos principales a los nodos secundarios).

Sugerencias: # 6, # 14, # 52, # 68, # 77, # 87, # 94, # 103, # 108, # 115

Preguntas adicionales: recursividad (n. ° 8.10), diseño y escalabilidad del sistema (n. ° 9.2, n. ° 9.3), clasificación y búsqueda

(# 10.10), Problemas difíciles (# 17.7, # 17.12, # 17.13, # 17.14, # 17.17, # 17.20, # 17.22, # 17.25).

Las sugerencias comienzan en la página 653.

[crackingthecodinginterviewes]

9.4.5

Grafos

Un árbol es en realidad un tipo de gráfico, pero no todos los gráficos son árboles. En pocas palabras, un árbol es un gráfico conectado sin ciclos.

Un gráfico es simplemente una colección de nodos con bordes entre (algunos de) ellos.

- Los gráficos pueden ser dirigidos (como el siguiente gráfico) o no dirigidos. Mientras que los bordes dirigidos son como calles de un solo sentido, los bordes no dirigidos son como una calle de dos sentidos.

- El gráfico puede constar de varios subgrafos aislados. Si hay un camino entre cada par de vértices, se llama un "gráfico conectado."

- El gráfico también puede tener ciclos (o no). Un "gráfico acíclico" es uno sin ciclos.

Visualmente, podría dibujar un gráfico como este:

En términos de programación, hay dos formas comunes de representar un gráfico.

Lista de adyacencia

Esta es la forma más común de representar un gráfico. Cada vértice (o nodo) almacena una lista de vértices adyacentes. En un gráfico no dirigido, una arista como (a, b) se almacenaría dos veces: una en los vértices adyacentes a a y una vez en los vértices adyacentes de b.

Una definición de clase simple para un nodo de gráfico podría verse esencialmente igual que un nodo de árbol.

codigo

La clase Graph se usa porque, a diferencia de un árbol, no necesariamente puede llegar a todos los nodos desde un solo nodo.

No es necesario que haya clases adicionales para representar un gráfico. Una matriz (o una tabla hash) de listas (matrices, listas de matrices, listas enlazadas, etc.) pueden almacenar la lista de adyacencia. El gráfico anterior podría representarse como:

0: 1

1: 2

2: 0, 3

3: 2

4: 6

5: 4

6: 5

Es un poco más compacto, pero no tan limpio. Tendemos a usar clases de nodo a menos que exista una razón para no hacerlo.

Matrices de adyacencia

Una matriz de adyacencia es una matriz booleana NxN (donde N es el número de nodos), donde un valor verdadero en la matriz [i] [j] indica un borde desde el nodo i al nodo j. (También puede usar una matriz entera con Os y 1 s.)

En un gráfico no dirigido, una matriz de adyacencia será simétrica. En un gráfico dirigido, no (necesariamente) ser.

Se pueden realizar los mismos algoritmos de gráficos que se utilizan en las listas de adyacencia (búsqueda primero en amplitud, etc.) con matrices de adyacencia, pero pueden ser algo menos eficientes. En la representación de la lista de adyacencia, puede iterar fácilmente a través de los vecinos de un nodo. En la representación de la matriz de adyacencia, necesitará iterar a través de todos los nodos para identificar los vecinos de un nodo.

Búsqueda de gráficos

Las dos formas más comunes de buscar en un gráfico son la búsqueda en profundidad y la búsqueda en amplitud.

En la búsqueda en profundidad primero (DFS), comenzamos en la raíz (u otro nodo seleccionado arbitrariamente) y exploramos cada rama completamente antes de pasar a la siguiente rama. Es decir, profundizamos primero (de ahí el nombre profundidad primera búsqueda) antes de ampliar.

En la búsqueda primero en amplitud (BFS), comenzamos en la raíz (u otro nodo seleccionado arbitrariamente) y exploramos cada vecino antes de continuar con cualquiera de sus hijos. Es decir, ampliamos (por lo tanto, buscamos primero en amplitud) antes vamos profundo.

Vea la siguiente descripción de un gráfico y su búsqueda en profundidad y en anchura (asumiendo que los vecinos son iterado en orden numérico).

La búsqueda en amplitud y la búsqueda en profundidad tienden a usarse en diferentes escenarios. A menudo se prefiere DFS si desea visitar todos los nodos del gráfico. Ambos funcionarán bien, pero la búsqueda en profundidad es un poco más simple.

Sin embargo, si queremos encontrar la ruta más corta (o simplemente cualquier ruta) entre dos nodos, BFS es generalmente mejor. Considere representar todas las amistades del mundo entero en un gráfico y tratar de encontrar un camino de amigos entre Ash y Vanessa.

En la búsqueda en profundidad, podríamos tomar un camino como Ash -> Brian -> Carleton -> Davis -> Eric -> Farah -> Gayle -> Harry -> Isabella -> John · -> Kari ... y luego nos encontramos muy lejos. Podríamos recorrer la mayor parte del mundo sin darnos cuenta de que, de hecho, Vanessa es amiga de Ash. Nosotros eventualmente encontrará el camino, pero puede llevar mucho tiempo. Tampoco nos encontrará el camino más corto.

En la búsqueda de amplitud, nos mantendríamos cerca de Ash durante el mayor tiempo posible. Podríamos iterar a través de muchos de los amigos de Ash, pero no acudiríamos a sus contactos más distantes hasta que fuera absolutamente necesario. Si Vanessa es amigo de Ash, o amigo de un amigo, lo averiguaremos con relativa rapidez.

Búsqueda en profundidad (DFS)

En DFS, visitamos un nodo ay luego iteramos a través de cada uno de los vecinos de a. Al visitar un nodo b que es un vecino de a, visitamos a todos los vecinos de b antes de ir a los otros vecinos de a. Es decir, una exhaustiva busca la rama de b antes que cualquiera de sus otros vecinos.

Tenga en cuenta que el pedido anticipado y otras formas de recorrido de árbol son una forma de DFS. La diferencia clave es que cuando al implementar este algoritmo para un gráfico, debemos verificar si el nodo ha sido visitado. Si no lo hacemos, corremos el riesgo quedando atascado en un bucle infinito.

El pseudocódigo siguiente implementa DFS.

Búsqueda primero en amplitud (BFS)

BFS es un poco menos intuitivo y muchos entrevistados luchan con la implementación a menos que ya estén familiarizado con él. El principal punto de inflexión es la suposición (falsa) de que BFS es recursivo. No es. En cambio, usa una cola.

En BFS, el nodo a visita a cada uno de los vecinos de a antes de visitar a cualquiera de sus vecinos. Puedes pensar en esto como búsqueda nivel por nivel desde a. Una solución iterativa que incluya una cola suele funcionar mejor.

Si se le pide que implemente BFS, la clave a recordar es el uso de la cola. El resto del algo El ritmo fluye de este hecho.

Búsqueda bidireccional

La búsqueda bidireccional se utiliza para encontrar la ruta más corta entre un nodo de origen y de destino. Opera esencialmente ejecutando dos búsquedas simultáneas en amplitud, una de cada nodo. Cuando sus búsquedas chocar, hemos encontrado un camino.

Para ver por qué esto es más rápido, considere un gráfico donde cada nodo tiene como máximo k nodos adyacentes y el más corto La ruta desde el nodo sa el nodo t tiene una longitud d.

- En la búsqueda tradicional de amplitud primero, buscaríamos hasta k nodos en el primer "nivel" de la búsqueda. En el segundo nivel, buscaríamos hasta k nodos para cada uno de esos primeros k nodos, por lo que k2 nodos en total (hasta ahora). Haríamos esto d veces, por lo que son 0 (kd) nodos.

- En la búsqueda bidireccional, tenemos dos búsquedas que chocan después de aproximadamente niveles (el punto medio del camino). La búsqueda de s visita aproximadamente kd12, al igual que la búsqueda de t. Eso es aproximadamente 2 kdl2, o 0 (kd / 2), nodos en total.

Esto puede parecer una diferencia menor, pero no lo es. Es enorme. Recuerde que (kd12) * (kd12) = kd. El bidirec La búsqueda tradicional es en realidad más rápida por un factor de kd12.

Dicho de otra manera: si nuestro sistema solo pudiera admitir la búsqueda de rutas de "amigo de amigo" en la búsqueda en amplitud, ahora probablemente podría apoyar los caminos de "amigo de amigo de amigo de amigo". Podemos apoyar caminos que son dos veces tanto tiempo.

Lectura adicional: Clasificación topológica (pág. 632), Algoritmo de Dijkstra (pág. 633), Árboles AVL (pág. 637), Árboles Rojo-Negro (pág. 639).

[crackingthecodinginterviewes]

9.4. Arboles

Muchos entrevistados consideran que los problemas de árboles y gráficos son algunos de los más complicados. Buscar un árbol es más complicado que buscar en una estructura de datos organizada linealmente, como una matriz o una lista enlazada. Adicionalmente, el peor de los casos y el tiempo promedio del caso pueden variar enormemente, y debemos evaluar ambos aspectos de cualquier algoritmo. La fluidez en la implementación de un árbol o gráfico desde cero resultará esencial.

Debido a que la mayoría de la gente está más familiarizada con los árboles que con los gráficos (y son un poco más simples), hablaremos de los árboles primero. Sin embargo, esto está un poco fuera de lugar, ya que un árbol es en realidad un tipo de gráfico.

Nota: algunos de los términos de este capítulo pueden variar ligeramente en diferentes libros de texto y otros fuentes. Si está acostumbrado a una definición diferente, está bien. Asegúrese de aclarar cualquier ambigüedad con su entrevistador.

Tipos de árboles

Una buena forma de entender un árbol es con una explicación recursiva. Un árbol es una estructura de datos compuesta por nodos.

- Cada árbol tiene un nodo raíz. (En realidad, esto no es estrictamente necesario en la teoría de grafos, pero por lo general es la forma en que se utilizan árboles en la programación, y especialmente en las entrevistas de programación.)

- El nodo raíz tiene cero o más nodos secundarios.

- Cada nodo secundario tiene cero o más nodos secundarios, y así sucesivamente.

El árbol no puede contener ciclos. Los nodos pueden o no estar en un orden particular, podrían tener cualquier tipo de dato como valores, y pueden o no tener enlaces a sus nodos principales.

Una definición de clase muy simple para Node es:

1 clase Nodo {

2 nombre de cadena pública;

3 niños públicos de Nodo [];

4}

También puede tener una clase de árbol para envolver este nodo. A los efectos de las preguntas de la entrevista, normalmente no utilice una clase de árbol. Puede hacerlo si cree que hace que su código sea más simple o mejor, pero rara vez lo hace.

1 árbol de clase {

2 raíz de nodo público;

3}

Las preguntas de árbol y gráfico están plagadas de detalles ambiguos y suposiciones incorrectas. Asegúrate de tener cuidado para los siguientes problemas y busque aclaraciones cuando sea necesario.

Árboles contra árboles binarios

Un árbol binario es un árbol en el que cada nodo tiene hasta dos hijos. No todos los árboles son árboles binarios. Por ejemplo, este árbol no es un árbol binario. Podrías llamarlo árbol ternario.

Hay ocasiones en las que es posible que tenga un árbol que no sea un árbol binario. Por ejemplo, supongamos que estuvieras usando un árbol para representar un montón de números de teléfono. En este caso, puede usar un árbol de 10 arios, con cada nodo que tiene hasta 10 hijos (uno por cada dígito).

Un nodo se denomina nodo "hoja" si no tiene hijos.

Árbol binario vs árbol de búsqueda binaria

Un árbol de búsqueda binario es un árbol binario en el que cada nodo se ajusta a una propiedad de ordenación específica: todo a la izquierda

descendientes <= n <todos los descendientes correctos. Esto debe ser cierto para cada nodo n.

La definición de un árbol de búsqueda binario puede variar ligeramente con respecto a la igualdad. Bajo algunos definiciones, el árbol no puede tener valores duplicados. En otros, los valores duplicados estarán a la derecha o puede estar en cualquier lado. Todas son definiciones válidas, pero debe aclarar esto con su entrevistador.

Tenga en cuenta que esta desigualdad debe ser cierta para todos los descendientes de un nodo, no solo para sus hijos inmediatos. El siguiente árbol de la izquierda a continuación es un árbol de búsqueda binaria. El árbol de la derecha no lo es, ya que el 12 está a la izquierda del 8.

Cuando se les da una pregunta de árbol, muchos candidatos asumen que el entrevistador se refiere a un árbol de búsqueda binario. Estar seguro preguntar. Un árbol de búsqueda binario impone la condición de que, para cada nodo, sus descendientes izquierdos sean menores o igual al nodo actual, que es menor que los descendientes de la derecha.

Equilibrado frente a desequilibrado

Si bien muchos árboles están equilibrados, no todos lo están. Pídale una aclaración a su entrevistador aquí. Tenga en cuenta que equilibrar un árbol no significa que los subárboles izquierdo y derecho sean exactamente del mismo tamaño (como se ve en "binario perfecto árboles "en el siguiente diagrama).

Una forma de pensarlo es que un árbol "equilibrado" realmente significa algo más como "no terriblemente imbalanced: 'Es lo suficientemente equilibrado como para garantizar 0 (log n) veces para insertar y buscar, pero no es necesariamente tan equilibrado como podría ser.

Dos tipos comunes de árboles equilibrados son los árboles rojo-negro (pág. 639) y los árboles AVL (pág. 637). Estos son discutido con más detalle en la sección Temas avanzados.

Árboles binarios completos

Un árbol binario completo es un árbol binario en el que todos los niveles del árbol están completamente llenos, excepto quizás el nivel pasado. En la medida en que se llene el último nivel, se llenará de izquierda a derecha.

Árboles binarios completos

Un árbol binario completo es un árbol binario en el que cada nodo tiene cero o dos hijos. Es decir, ningún nodo tiene solo un hijo.

Árboles binarios perfectos

Un árbol binario perfecto es uno que está completo y completo. Todos los nodos hoja estarán en el mismo nivel, y esto level tiene el número máximo de nodos.

Tenga en cuenta que los árboles perfectos son raros en las entrevistas y en la vida real, ya que un árbol perfecto debe tener exactamente 2k - 1 nodos (donde k es el número de niveles). En una entrevista, no asuma que un árbol binario es perfecto.

Árbol Binario Transversal

Antes de su entrevista, debe sentirse cómodo implementando en orden, post-orden y pre-orden el recorrido. El más común de ellos es el recorrido en orden.

En Orden Transversal

En orden transversal significa "visitar" (a menudo, imprimir) la rama izquierda, luego el nodo actual y, finalmente, la derecha. rama.

CODIGO

Cuando se realiza en un árbol de búsqueda binaria, visita los nodos en orden ascendente (de ahí el nombre "en orden")

Recorrido de pedidos anticipados

El recorrido de pedido anticipado visita el nodo actual antes que sus nodos secundarios (de ahí el nombre "pedido anticipado").

CODIGO

En un recorrido de preorden, la raíz es siempre el primer nodo visitado.

CODIGO

En un recorrido de preorden, la raíz es siempre el primer nodo visitado.

Recorrido posterior al pedido

El recorrido posterior al pedido visita el nodo actual después de sus nodos secundarios (de ahí el nombre "posterior al pedido").

CODIGO

En un recorrido posterior a la orden, la raíz es siempre el último nodo visitado.

Montones binarios (Min-Montones y Max-Montones)

Solo hablaremos de min-montones aquí. Los montones máximos son esencialmente equivalentes, pero los elementos están en orden descendente orden en lugar de orden ascendente.

Un min-heap es un árbol binario completo (es decir, totalmente lleno con excepción de los elementos de la derecha en el último level) donde cada nodo es más pequeño que sus hijos. La raíz, por tanto, es el elemento mínimo del árbol.

Tenemos dos operaciones clave en un min-heap: insert y extract_min.

Insertar

Cuando insertamos en un min-heap, siempre comenzamos insertando el elemento en la parte inferior. Insertamos en el punto más a la derecha para mantener la propiedad del árbol completa.

Luego, "arreglamos" el árbol intercambiando el nuevo elemento con su padre, hasta que encontremos un lugar apropiado para el elemento. Básicamente, burbujeamos el elemento mínimo.

Esto toma O (log n) tiempo, donde n es el número de nodos en el montón.

Extraer elemento mínimo

Encontrar el elemento mínimo de un min-heap es fácil: siempre está en la parte superior. La parte más complicada es cómo eliminar eso. (De hecho, esto no es tan complicado).

Primero, eliminamos el elemento mínimo y lo intercambiamos con el último elemento del montón (el más inferior, elemento más a la derecha). Luego, burbujeamos este elemento, intercambiándolo con uno de sus hijos hasta que el mínimo se restaura la propiedad del montón.

¿Lo intercambiamos con el niño de la izquierda o con el niño de la derecha? Eso depende de sus valores. No hay inherente ordenando entre el elemento izquierdo y derecho, pero deberá tomar el más pequeño para mantener el orden de min-heap.

Este algoritmo debe tomar 0( log n) tiempo.

Tries (árboles de prefijos)

Un trie (a veces llamado árbol de prefijos) es una estructura de datos divertida. Aparece mucho en las preguntas de las entrevistas, pero los libros de texto de algoritmos no dedican mucho tiempo a esta estructura de datos.

Un trie es una variante de un árbol n-ario en el que los caracteres se almacenan en cada nodo. Cada camino por el árbol puede representar una palabra.

Los nodos * (a veces llamados "nodos nulos") se utilizan a menudo para indicar palabras completas. Por ejemplo, el El hecho de que haya un nodo * debajo de MUCHOS indica que MUCHOS es una palabra completa. La existencia del camino MA indica que hay palabras que comienzan con MA.

La implementación real de estos * nodos podría ser un tipo especial de hijo (como un TerminatingTrieNode, que hereda de TrieNode). O podríamos usar solo una bandera booleana termina dentro del nodo "padre".

Un nodo en un trie podría tener desde 1 hasta ALPHABET _SIZE + 1 hijos (o, 0 a ALPHABET _SIZE si se usa una bandera booleana en lugar de un * nodo).

Muy comúnmente, un trie se usa para almacenar todo el idioma (inglés) para búsquedas rápidas de prefijos. Mientras un hash tabla puede buscar rápidamente si una cadena es una palabra válida, no puede decirnos si una cadena es un prefijo de cualquier palabras. Un trie puede hacer esto muy rápidamente.

¿Qué tan rápido? Un trie puede verificar si una cadena es un prefijo válido en el tiempo 0 (K), donde K es la longitud del cuerda. En realidad, este es el mismo tiempo de ejecución que tomará una tabla hash. Aunque a menudo nos referimos a hash búsquedas de tablas como 0 (1) tiempo, esto no es del todo cierto. Una tabla hash debe leer todos los caracteres en la entrada, lo que lleva tiempo O (K) en el caso de una búsqueda de palabras.

Muchos problemas que involucran listas de palabras válidas aprovechan un trie como optimización. En situaciones en las que buscamos a través del árbol en prefijos relacionados repetidamente (por ejemplo, buscando M, luego MA, luego MAN, luego MUCHOS), podríamos pasar una referencia al nodo actual en el árbol. Esto nos permitirá comprobar si Y es un hijo de MAN, en lugar de comenzar desde la raíz cada vez.

[crackingthecodinginterviewes]

9.3.Q

Preguntas de entrevista

3.1 Tres en uno: Describe cómo podrías usar una sola matriz para implementar tres pilas. Sugerencias: # 2, # 72, # 38, # 58 3.2

3.2 Stack Min: ¿Cómo diseñarías una pila que, además de push y pop, tenga una función min que devuelve el elemento mínimo? Push, pop y min deben funcionar todos en 0 (1) tiempo. Sugerencias: # 27, # 59, # 78 98

3.3 Pila de platos: Imagine una pila (literal) de platos. Si la pila es demasiado alta, podría caerse. Por lo tanto, en la vida real, probablemente comenzaríamos una nueva pila cuando la pila anterior supere algunos umbral. Implemente una estructura de datos SetOfStacks que imite esto. SetO-fStacks debe ser compuesto por varias pilas y debe crear una nueva pila una vez que la anterior supere la capacidad. SetOfStacks. push () y SetOfStacks. pop () debería comportarse de manera idéntica a una sola pila (es decir, pop () debería devolver los mismos valores que si hubiera una sola pila).

HACER UN SEGUIMIENTO

Implemente una función popAt (int index) que realiza una operación pop en una sub-pila específica. Sugerencias: # 64, # 87 pág. 233

3.4 Cola a través de pilas: implemente una clase MyQueue que implementa una cola usando dos pilas. Sugerencias: # 98, # 7 74

3.5 Ordenar pila: escriba un programa para ordenar una pila de modo que los elementos más pequeños estén en la parte superior. Puedes usar una pila temporal adicional, pero no puede copiar los elementos en ninguna otra estructura de datos (como una matriz). La pila admite las siguientes operaciones: push, pop, peek y está vacía. Sugerencias: # 15, # 32, # 43

3.6 Refugio de animales: Un refugio de animales, que solo admite perros y gatos, opera estrictamente en un "primero en entrar, primero out ". Las personas deben adoptar el" más viejo "(según la hora de llegada) de todos los animales en el refugio, o pueden seleccionar si prefieren un perro o un gato (y recibirán el animal más viejo de ese tipo). No pueden seleccionar qué animal específico les gustaría. Cree las estructuras de datos para mantener este sistema e implementar operaciones como enqueue, dequeueAny, dequeueDog, y dequeueCat. Puede utilizar la estructura de datos de lista vinculada incorporada. Sugerencias: # 22, # 56, # 63

...

Preguntas adicionales: Listas vinculadas (n. ° 2.6), problemas moderados (n. ° 16.26), problemas difíciles (n. ° 17.9). Las sugerencias comienzan en la página 653.

https://github.com/careercup/CtCI-6th-Edition-JavaScript/tree/master/chapter03

[crackingthecodinginterviewes]

9.3. Stacks y Consultas

Las preguntas sobre pilas y colas serán mucho más fáciles de manejar si se siente cómodo con las entradas y fuera de la estructura de datos. Sin embargo, los problemas pueden ser bastante complicados. Si bien algunos problemas pueden ser ligeras modificaciones en la estructura de datos original, otras tienen desafíos mucho más complejos.

Implementar una pila

La estructura de datos de la pila es precisamente lo que parece: una pila de datos. En ciertos tipos de problemas, puede Ser favorable almacenar datos en una pila en lugar de en una matriz.

Una pila utiliza el orden LIFO (último en entrar, primero en salir). Es decir, como en una pila de platos, el elemento más reciente agregado a la pila es el primer elemento que se eliminará.

Utiliza las siguientes operaciones:

pop (): Elimina el elemento superior de la pila.

empujar (i tern): agrega un elemento a la parte superior de la pila.

peek (): Devuelve la parte superior de la pila.

is Empty (): Devuelve verdadero si y solo si la pila está vacía.

A diferencia de una matriz, una pila no ofrece acceso en tiempo constante al i-ésimo elemento. Sin embargo, permite constantes el tiempo agrega y elimina, ya que no requiere cambiar elementos.

Hemos proporcionado un código de muestra simple para implementar una pila. Tenga en cuenta que también se puede implementar una pila utilizando una lista vinculada, si se agregaron y eliminaron elementos del mismo lado.

1 public class MyStack<T> {

2 private static class StackNode<T> {

3 private T data;

4 private StackNode<T> next;

5

6 public StackNode(T data) {

7 this.data = data;

8 }

9 }

16

11 private StackNode<T> top;

12

13 public T pop() {

14 if (top == null) throw new EmptystackException();

15 T item = top.data;

16 top= top.next;

17 return item;

18 }

19

20 public void push(T item) {

21 StackNode<T> t = new StackNode<T>(item);

22 t.next = top;

23 top= t;

24 }

25

26 public T peek() {

27 if (top== null) throw new EmptyStackException();

28 return top.data;

29 }

30

31 public boolean isEmpty() {

32 return top == null;

33 }

34 }

Un caso en el que las pilas suelen ser útiles es en ciertos algoritmos recursivos. A veces necesitas empujar datos temporales en una pila a medida que recurre, pero luego elimínelos a medida que retrocede (por ejemplo, porque la comprobación recursiva falló). Una pila ofrece una forma intuitiva de hacer esto.

También se puede utilizar una pila para implementar un algoritmo recursivo de forma iterativa. (¡Este es un buen ejercicio! algoritmo recursivo simple e implementarlo iterativamente).

Implementar una cola (Queue)

Una cola implementa el orden FIFO (primero en entrar, primero en salir). Como en una fila o cola en una taquilla, los artículos se se eliminan de la estructura de datos en el mismo orden en que se agregan.

Utiliza las operaciones:

add (i tern): añade un elemento al final de la lista.

remove (): Elimina el primer elemento de la lista.

peek (): Devuelve la parte superior de la cola.

is Empty (): devuelve verdadero si y solo si la cola está vacía.

También se puede implementar una cola con una lista vinculada. De hecho, son esencialmente lo mismo, siempre que los elementos se agregan y quitan de lados opuestos.

ESTE CODIGO ESTA MAL

1 public class MyQueue<T> {

2 private static class QueueNode<T> {

3 private T data;

4 private QueueNode<T> next;

5

6 public QueueNode(T data) {

7 this.data = data;

8 }

9 } 10

11 private QueueNode<T> first;

12 private QueueNode<T> last;

13

14 public void add(T item) {

15 QueueNode<T> t = new QueueNode<T>(item);

16 if (last != null) {

17 last.next= t;

18 } last = t;

19 if (first== null) {

20 first= last;

21 }

22 public T remove() {

23 }

24

25 if (first== null) throw new NoSuchElementException();

26 T data= first.data;

27 first= first.next;

28 if (first == null) {

28 last = null;

29 } return data;

30 public T peek() {

}

Es especialmente fácil estropear la actualización del primer y último nodos de una cola. Asegúrate de comprobarlo dos veces esta.

Un lugar donde las colas se utilizan a menudo es en la búsqueda de amplitud o en la implementación de una caché.

En la búsqueda de amplitud primero, por ejemplo, usamos una cola para almacenar una lista de los nodos que necesitamos procesar. Cada vez que procesamos un nodo, agregamos sus nodos adyacentes al final de la cola. Esto nos permite procesar nodos en el orden en que se visualizan.

[crackingthecodinginterviewes]

Herramienta para convertir JS a diagrama de flujo

Muy útil cuando encuentras un código y no estás seguro que hace.

[crackingthecodinginterviewes]

9.2 Listas vinculadas

Una lista vinculada es una estructura de datos que representa una secuencia de nodos. En una lista enlazada individualmente, cada nodo apunta al siguiente nodo de la lista vinculada. Una lista doblemente enlazada le da a cada nodo punteros al siguiente nodo y el nodo anterior.

El siguiente diagrama muestra una lista doblemente enlazada

A diferencia de una matriz, una lista enlazada no proporciona acceso de tiempo constante a un "índice" particular dentro de la lista. Esto significa que si desea encontrar el elemento Kth en la lista, deberá iterar a través de los elementos K. El beneficio de una lista vinculada es que puede agregar y eliminar elementos del principio de la lista en constante tiempo. Para aplicaciones específicas, esto puede resultar útil.

Crear una lista vinculada

El siguiente código implementa una lista de enlaces sencillos muy básica.

1 class Node {

2 Node next= null;

3 int data;

4

5 public Node(int d) {

6 data= d;

7 }

8

9 void appendToTail(int d) {

10 Node end= new Node(d);

11 Node n = this;

12 while (n.next !=null) {

13 n= n.next;

14 }

15 n.next = end;

16 }

17 }

En esta implementación, no tenemos una estructura de datos de lista vinculada. Accedemos a la lista enlazada a través de un referencia al nodo principal de la lista enlazada. Cuando implementa la lista enlazada de esta manera, necesita estar un poco de cuidado. ¿Qué sucede si varios objetos necesitan una referencia a la lista vinculada y luego el encabezado de la lista vinculada cambios? Es posible que algunos objetos sigan apuntando a la cabeza vieja.

Podríamos, si quisiéramos, implementar una clase Linked List que envuelva la clase Node. Esto esencialmente solo tiene una sola variable miembro: el nodo principal. Esto resolvería en gran medida el problema anterior.

Recuerde que cuando está discutiendo una lista vinculada en una entrevista, debe comprender si es una lista unicamente enlazada o una lista doblemente enlazada.

Eliminar un nodo de una lista enlazada individualmente

Eliminar un nodo de una lista vinculada es bastante sencillo. Dado un nodo n, encontramos el nodo anterior prev y establezca la anterior. siguiente igual an. Siguiente. Si la lista está doblemente vinculada, también debemos actualizar n. junto al conjunto norte. Siguiente. prev igual an. anterior Las cosas importantes para recordar son (1) verificar el puntero nulo y (2) actualizar el puntero de cabeza o cola según sea necesario

Además, si implementa este código en C, C ++ u otro lenguaje que requiera que el desarrollador haga administración de memoria, debe considerar si el nodo eliminado debe ser desasignado.

1 Node deleteNode(Node head, int d) {

2 Node n = head;

3

4 if (n.data == d) {

5 return head.next; /* moved head*/

6 }

7

8 while (n.next != null) {

9 if (n.next.data == d) {

10 n.next = n.next.next;

11 return head; /* head didn't change*/

12 }

13 n = n.next;

14 }

15 return head;

16 }

La técnica del "corredor"

La técnica del "corredor" (o segundo puntero) se utiliza en muchos problemas de listas enlazadas. La técnica del corredor significa que itera a través de la lista vinculada con dos punteros simultáneamente, con uno delante del otro. El nodo "rápido" puede estar por delante en una cantidad fija o puede estar saltando varios nodos para cada un nodo por el que itera el nodo "lento".

Por ejemplo, suponga que tiene una lista enlazada a1 ->a2 -> ... ->an ->b1 ->b2 -> ... ->bn y desea reorganícelo en a1 -> b1 -> a2 -> b2 -> ... -> an -> bn. No conoce la longitud de la lista enlazada (pero sé que la longitud es un número par).

Podría hacer que un puntero p1 (el puntero rápido) se mueva cada dos elementos por cada movimiento que p2 marcas. Cuando pl llegue al final de la lista vinculada, p2 estará en el punto medio. Luego, mueva p1 de nuevo al frente y empezar a "tejer" los elementos. En cada iteración, p2 selecciona un elemento y lo inserta después de p1.

Problemas recursivos

Varios problemas de listas vinculadas se basan en la recursividad. Si tiene problemas para resolver un problema de lista vinculada, debería explorar si un enfoque recursivo funcionará. No profundizaremos en la recursividad aquí, ya que más tarde capítulo está dedicado a ello.

Sin embargo, debe recordar que los algoritmos recursivos ocupan al menos O (n) espacio, donde n es la profundidad de la llamada recursiva. Todos los algoritmos recursivos se pueden implementar de forma iterativa, aunque pueden ser mucho mas complejo.

Preguntas de entrevista

2.1 ¡Remover Duplicados! Escriba un código para eliminar duplicados de una lista vinculada sin clasificar.

SEGUIMIENTO

¿Cómo resolvería este problema si no se permite un búfer temporal? Sugerencias: # 9, # 40

2.2 Devolver K.esimo (Kth) al último: Implemente un algoritmo para encontrar el kth al último elemento de una lista enlazada individualmente. Sugerencias: # 8, # 25, # 41, # 67, # 12

Nota: Por lo menos yo no sabía que cosa es K.esimo.

2.3 Eliminar nodo medio: implemente un algoritmo para eliminar un nodo en el medio (es decir, cualquier nodo menos el primer y último nodo, no necesariamente el medio exacto) de una lista enlazada individualmente, al que solo se le da acceso a ese nodo.

EJEMPLO

Entrada: el nodo c de la lista enlazada-> b-> c-> d-> e-> f

Resultado: no se devuelve nada, pero la nueva lista vinculada parece a-> b-> d-> e-> f

Sugerencias: # 72

2.4 Partición: escriba el código para particionar una lista enlazada alrededor de un valor x, de modo que todos los nodos menores que x vengan antes de todos los nodos mayores o iguales ax. Si x está contenido en la lista, los valores de x solo necesitan estar después de los elementos menores que x (ver más abajo). El elemento de partición x puede aparecer en cualquier parte del "partición derecha"; no es necesario que aparezca entre las particiones izquierda y derecha.

EJEMPLO

Aporte: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [partición = 5]

3 -> 1 -> 2 -> 10 -> 5 -> 5 ->

Sugerencias: # 3, # 24

94 Entrevista para descifrar la codificación, sexta edición

Capítulo 2 I Listas vinculadas

2.5 Listas de suma: tiene dos números representados por una lista enlazada, donde cada nodo contiene un solo dígito. Los dígitos se almacenan en orden inverso, de modo que el dígito del 1 esté al principio de la lista. Escribe un función que suma los dos números y devuelve la suma como una lista vinculada.

EJEMPLO

Entrada: (7-> 1 -> 6) + (5 -> 9 -> 2), es decir, 617 + 295.

Salida: 2 -> 1 -> 9. Es decir, 912.

HACER UN SEGUIMIENTO

Suponga que los dígitos se almacenan en orden de avance. Repita el problema anterior.

EJEMPLO

Ingrese: (6 -> 1 -> 7) + (2 -> 9 -> 5), es decir, 617 + 295.

Salida: 9 -> 1 -> 2. Es decir, 912.

Sugerencias: # 7, # 30, # 71, # 95, # 109

2.6 Palíndromo: Implemente una función para verificar si una lista vinculada es un palíndromo.

Sugerencias: # 5, # 13, # 29, # 61, # 101

2.7 Intersección: Dadas dos listas enlazadas (individualmente), determine si las dos listas se cruzan. Devuelve el interseccionamiento del nodo. Tenga en cuenta que la intersección se define en función de la referencia, no del valor. Es decir, si El nodo de la primera lista enlazada es exactamente el mismo nodo (por referencia) que el j-ésimo nodo de la segunda lista enlazada, entonces se están cruzando.

Sugerencias: # 20, # 45, # 55, # 65, # 76, # 93, # 111, # 120, # 129

2.8 Detección de bucle: Dada una lista enlazada circular, implemente un algoritmo que devuelva el nodo en el comienzo del bucle.

DEFINICIÓN

Lista vinculada circular: una lista vinculada (corrupta) en la que el siguiente puntero de un nodo apunta a un nodo anterior, por lo que como para hacer un bucle en la lista enlazada.

EJEMPLO

Entrada: A -> B -> C -> D -> E -> C [la misma C que antes]

Salida: C

Sugerencias: # 50, # 69, # 83, # 90

Preguntas adicionales: árboles y gráficos (n. ° 4.3), diseño orientado a objetos (n. ° 7.12), diseño de sistemas y Scalhabilidad (n. ° 9.5), problemas moderados (n. ° 16.25), problemas difíciles (n. ° 17.12).

Las sugerencias comienzan en la página 653.

CrackingTheCodinglnterview.com I 6ta Edición 95

https://github.com/careercup/CtCI-6th-Edition-JavaScript/tree/master/chapter02

[crackingthecodinginterviewes]

Actividad Sugerida

Hacer calculadoras con cada ejercicio

[crackingthecodinginterviewes]

9.1. Q

Preguntas de entrevista

1.1 Único y detergente: implementa un algoritmo para determinar si todos los caracteres de una cadena son únicos. ¿Cómo se resuelve si no puedes utilizar estructuras de datos adicionales?

Sugerencias: # 44, # 7 7 7, # 732

1.2 Verificador de permutación: A partir de dos cadenas, escribe un método que verifique si una es una permutación de la otra.

Sugerencias: # 7, # 84, # 722, # 737 _pg 193

Permutación f. Mat. Cada una de las ordenaciones posibles de los elementos de un conjunto finito. RAE

1.3 URLify: escriba un método para reemplazar todos los espacios en una cadena con '% 20'. Puede suponer que la cadena tiene suficiente espacio al final para contener los caracteres adicionales, y que se le da el "verdadero" longitud del string. (Nota: si se implementa en Java, utilice una matriz de caracteres para que pueda realizar esta operación en su lugar).

EJEMPLO

Entrada: "Sr. John Smith", 13

Resultado: "Mr% 20John% 20Smith"

Sugerencias: # 53, # 118 90

1.4 Permutación del palíndromo: Dada una cadena, escribe una función para verificar si es una permutación de un palindrome. Un palíndromo es una palabra o frase que es igual hacia adelante y hacia atrás. Una permutación es una reordenación de letras. El palíndromo no tiene por qué limitarse solo a las palabras del diccionario.

EJEMPLO

Entrada: Tact Coa

Resultado: Verdadero (permutaciones: "taco cat", "atco cta", etc.)

Sugerencias: # 106, # 121, # 134, # 136

1.5 One Modo: hay tres tipos de ediciones que se pueden realizar en cadenas: insertar un carácter, eliminar un carácter o reemplazar un carácter. Dadas dos cadenas, escriba una función para comprobar si estan a una edición (o cero) de distancia.

EJEMPLO

pale, ple -> true

pales, pale -> true

pale, bale -> true

pale, bake -> false

Sugerencias: # 23, # 97, # 130

1.6 Compresión de cadenas: implemente un método para realizar una compresión básica de cadenas contando los caracteres repetidos. Por ejemplo, la cadena aabcccccaaa se convertiría en a2b1c5a3. Si la cadena "comprimida" no es más pequeña que la cadena original, tu método devuelve la cadena original. Puede asumir que la cadena solo tiene letras mayúsculas y minúsculas (a - z).

Sugerencias: # 92, # 110

1.7 Rotar matriz: dada una imagen representada por una matriz NxN, donde cada píxel de la imagen es 4 bytes, escriba un método para rotar la imagen 90 grados. ¿Podrías?

Sugerencias: # 51, # 100

1.8 Matriz cero: escriba un algoritmo tal que si un elemento en una matriz MxN es 0, toda su fila y columna se establecen en 0.

Sugerencias: # 17, # 74, # 702

1.9 Rotación de cadenas: suponga que tiene un método llamado isSubstring que comprueba si una palabra es una subcadena de otro. Dadas dos cadenas, s1 y s2, escriba el código para verificar que s2 sea una rotación de s1 usando solo una llamada al método isSubstring (por ejemplo, "botella" es una rotación de "alletob").

Sugerencias: # 34, # 88, # 7 04

Preguntas adicionales: Diseño orientado a objetos (# 7.12). Recursividad (n. ° 8.3), clasificación y búsqueda (n. ° 10.9), C ++ (# 12.11), Problemas medios (# 16.8, # 16.17, # 16.22), Problemas difíciles (# 17.4, # 17.7, # 17.13, # 17.22, # 17.26).

Las sugerencias comienzan en la página 653.

https://github.com/careercup/CtCI-6th-Edition-JavaScript/tree/master/chapter01

[crackingthecodinginterviewes]

Soluciones

Descargar las soluciones

6ta Edición: https://github.com/gaylemcd/CtCI-6th-Edition

5ta Edición: https://github.com/gaylemcd/ctci

Para iniciar Git / GitHub

Sigue estas instrucciones: https://help.github.com/articles/set-up-git

(En el libro, la mayoría de los ejercicios están planteados para Java)

Como agregar un proyecto a Eclipse

1. Abre Eclipse

2. Dirígete a Archivo > Nuevo > Proyecto de Java

3. Deselecciona "Usar locación por defecto" y entonces navega hasta la carpeta donde se encuentre el código fuente en tu computadora.

4. Click en OK

Nota personal

Como yo estoy estudiando JavaScript, el enlace directo de las soluciones será hacia este lenguaje.

Dependiendo del tiempo que disponga, voy a ir subiendo el enlace a las soluciones en Java (lenguaje principal del libro) y si tengo tiempo, en otros lenguajes.

Por otro lado, siguiendo el enlace principal del repositorio de GitHub es fácil encontrar las soluciones en 10 de los lenguajes más populares del momento (2021 Annus Pandemicus).

[crackingthecodinginterviewes]

9.1. Arrays y Cadenas

Asumimos que todos los lectores de este libro están familiarizados con las matrices y las secuencias, por lo que no lo aburriremos con tales detalles. En su lugar, nos centraremos en algunas de las técnicas y problemas más comunes con estas estructuras de datos.

Tenga en cuenta que las preguntas sobre arrays y las preguntas sobre cadenas a menudo son intercambiables. Es decir, una pregunta de este libro que utiliza una matriz, puede formularse como una pregunta de cadena, y viceversa.

Hash Tables

Una tabla hash es una estructura de datos que asigna claves a valores para una búsqueda altamente eficiente. Hay una serie de formas de implementar esto. Aquí, describiremos una implementación simple pero común.

En esta implementación simple, usamos una matriz de listas vinculadas y una función de código hash. Para insertar una llave (que puede ser una cadena o esencialmente cualquier otro tipo de datos) y valor, hacemos lo siguiente:

1. Primero, calcule el código hash de la clave, que normalmente será un int o long. Tenga en cuenta que dos claves diferentes podrían tener el mismo código hash, ya que puede haber un número infinito de claves y un número finito de entradas.

2. Luego, asigne el código hash a un índice en la matriz. Esto se puede hacer con algo como hash (clave) % array_length. Por supuesto, dos códigos hash diferentes podrían correlacionarse con el mismo índice.

3. En este índice, hay una lista vinculada de claves y valores. Almacene la clave y el valor en este índice. Debemos usar una lista vinculada debido a colisiones(duplicados?): podría tener dos claves diferentes con el mismo código hash, o dos diferentes códigos hash que se asignan al mismo índice.

Para recuperar el par de valores por su clave, repita este proceso. Calcule el código hash de la clave y luego calcular el índice a partir del código hash. Luego, busque en la lista vinculada el valor con esta clave.

Si el número de colisiones es muy alto, el peor tiempo de ejecución es O (N), donde N es el número de claves. Sin embargo, generalmente asumimos una buena implementación que mantiene las colisiones al mínimo, en cuyo caso el tiempo de búsqueda es 0 (1).

Alternativamente, podemos implementar la tabla hash con un árbol de búsqueda binario balanceado. Esto nos da una O (log N) tiempo de búsqueda. La ventaja de esto es que potencialmente usa menos espacio, ya que ya no asignamos una matriz grande. Nosotros también puede iterar a través de las claves en orden, lo que a veces puede ser útil.

Arraylist y matrices redimensionables

En algunos lenguajes, las matrices (a menudo llamadas listas en este caso) se redimensionan automáticamente. La matriz o lista puede crecer a medida que agrega elementos. En otros lenguajes, como Java, las matrices tienen una longitud fija. El tamaño se define cuando creas la matriz.

Cuando necesite una estructura de datos similar a una matriz que ofrezca un cambio de tamaño dinámico, generalmente usaría una Arraylist.

Una Arraylist es una matriz que cambia de tamaño según sea necesario y, al mismo tiempo, proporciona acceso 0 (1). Una implementación típica es que cuando la matriz está llena, la matriz duplica su tamaño. Cada duplicación toma 0 (n) tiempo, pero sucede que raramente que su tiempo de inserción amortizado sea todavía O (1).

1 Arraylist<String> merge(String[ ] words, String[ ] more) {

2 Arraylist<String> sentence= new Arraylist<String>();

3 for (String w : words) sentence.add(w);

4 for (String w: more) sentence.add(w);

5 return sentence;

6 }

Esta es una estructura de datos esencial para las entrevistas. Asegúrese de sentirse cómodo con el tamaño variable dinámicamente matrices / listas en cualquier idioma con el que esté trabajando. Tenga en cuenta que el nombre de la estructura de datos también ya que el "factor de cambio de tamaño" (que es 2 en Java) puede variar.

¿Por qué el tiempo de ejecución de inserción amortizado es 0 (1)?

Suponga que tiene una matriz de tamaño N. Podemos trabajar hacia atrás para calcular cuántos elementos copiamos en cada aumento de capacidad. Observe que cuando aumentamos la matriz a K elementos, la matriz fue previamente la mitad de ese tamaño. Por lo tanto, necesitábamos copiar k/2 elementos

final capacity increase n/2 elements to copy previous capacity increase: n/4 elements to copy previous capacity increase: n/8 elements to copy previous capacity increase: n/16 elements to copy second c a pacity increase 2 elements to copy first capacity increase 1 element to copy

Por lo tanto, el número total de copias para insertar N elementos es aproximadamente Yi '+% +% +. . . + 2 + 1, que es un poco menos que N.

Si la suma de esta serie no es obvia para usted, imagine esto: suponga que tiene un kilómetro de largo caminar a la tienda. Caminas 0,5 kilómetros, luego 0,25 kilómetros, y luego 0,125 kilómetros, etcétera. Nunca superarás el kilómetro (aunque te acercarás mucho).

Por lo tanto, insertar N elementos requiere O (N) trabajo total. Cada inserción es 0 (1) en promedio, aunque algunas inserciones toman O (N) tiempo en el peor de los casos.

Constructor de Cadenas

Imagine que está concatenando una lista de cadenas, como se muestra a continuación ¿Cuál sería el tiempo de ejecución de este código? Para simplificar, suponga que todas las cadenas tienen la misma longitud (llamaremos a esto x) y hay n cadenas.

1 String joinWords(String[ ] words) {

2 String sentence = "";

3 for (String w: words) {

4 sentence = sentence + w;

5 }

6 return sentence;

7 }

En cada concatenación, se crea una nueva copia de la cadena y se copian las dos cadenas, caracter por caracter. La primera iteración requiere que copiemos x caracteres. La segunda iteración requiere copiar 2x caracteres. La tercera iteración requiere 3x, y así sucesivamente. Por tanto, el tiempo total es O (x + 2x + ... + Nx). Esto se reduce a O (xn2).

Por que es O(xn2)? Pues por que 1 + 2 + ... + n equals n(n+1)/2,orO(n2).

Un buen ejercicio para practicar cadenas, matrices y estructuras de datos generales es implementar su propia versión de StringBuilder, HashTable y Array List.

Lectura adicional: Resolución de colisiones de tablas hash (pág. 636), Búsqueda de subcadenas de Rabin-Karp (pág. 636).

[crackingthecodinginterviewes]

Hola.

Soy un programador junior que está traduciendo el libro “Cracking the Coding Interview” con fines didácticos.

En este blog iré subiendo los capítulos y sobre todo, los ejercicios.

Si les gusta este material, por favor compren el original.

Todo el material es propiedad de Gayle Laakmann McDowell.