Índice del contenido[Esconder][Espectáculo]
- 1. ¿Cómo se define una matriz?
- 2. Matrices dinámicas: ¿qué son? ¿Qué los diferencia de los arreglos básicos?
- 3. ¿Cómo varían entre sí una matriz y un diccionario?
- 4. Enumere algunos de los beneficios y desventajas de los arreglos.
- 5. ¿A qué se refiere “Sparse Array”?
- 6. ¿Cuándo elegiría una lista enlazada en lugar de una matriz?
- 7. ¿Qué distingue a un arreglo indexado de un arreglo asociativo?
- 8. ¿Qué ventajas tiene Heap sobre las matrices ordenadas?
- 9. ¿Podemos definir el tamaño de la matriz como negativo?
- 10. ¿Cómo localiza el entero que falta en una matriz de 1 a 100 elementos?
- 11. ¿Cómo encuentras el índice de un elemento en una matriz?
- 12. ¿Cómo puedes deshacerte de un elemento específico de una matriz?
- 13. ¿Cómo se puede verificar la igualdad de dos arreglos?
- 14. Cuando hablamos de arreglos, ¿qué quiere decir con las frases "Dimensión" y "Subíndice"?
- Preguntas de la entrevista de codificación
- 15. Busque un par en una matriz que tenga la suma especificada
- 16. Clasificación de matriz binaria con tiempo lineal
- 17. Encuentra el producto de dos enteros más grande en una matriz.
- 18. Cómo desplazar todos los ceros de la matriz al final
- 19. Cómo ordenar una matriz con dos entradas que se intercambian en una sola operación.
- 20. Cómo combinar dos arreglos ordenados en su lugar.
- 21. ¿Cómo reordenar una serie de artículos en posiciones altas y bajas alternas?
- 22. ¿Cómo sustituir cada elemento de un arreglo sin usar un operador de división con el producto de cada elemento del arreglo?
- 23. Encuentra el elemento más extraño en una matriz en tiempo logarítmico
- 24. ¿Cómo obtener el siguiente elemento más grande para cada elemento en una matriz circular?
- 25. ¿Encontrar el conteo de inversión de una matriz?
- 26. ¿Cuál es el problema de atrapamiento de agua de lluvia?
- Conclusión
Las entrevistas de codificación contienen una serie de preguntas DSA. Debe ser hábil con las matrices si se está preparando para su próxima entrevista técnica con FAANG u otra empresa tecnológica de nivel 1.
En la mayoría de las entrevistas de codificación, ocupa el segundo lugar después de Strings. Una matriz es una agrupación de elementos de datos relacionados que se mantienen muy cerca unos de otros en la memoria.
Como están conectados a todos los lenguajes de programación, como C, C++, Java, Python, Perl y Ruby, están en todas partes. Continúe leyendo para practicar algunos desafíos de codificación y entrevistar preguntas y respuestas basadas en matrices.
Python se usará en esta publicación para abordar los problemas de codificación porque es fácil de usar, comprender y debe ser familiar para la mayoría de nosotros.
Vamos a empezar.
1. ¿Cómo se define una matriz?
- Un grupo de tipos de datos relacionados es una matriz.
- Las matrices siempre son fijas.
- Los objetos de matriz almacenan el mismo tipo de variable en varios lugares.
- Los tipos primitivos y las referencias a objetos son compatibles con él.
2. Matrices dinámicas: ¿qué son? ¿Qué los diferencia de los arreglos básicos?
El escalado automático que proporcionan las matrices dinámicas (también denominadas matrices ampliables, matrices redimensionables, matrices cambiables o ArrayLists en Java) es una ventaja significativa.
Siempre debe saber cuántos elementos almacenará su matriz por adelantado, ya que las matrices tienen un tamaño fijo. Una matriz dinámica, por otro lado, crece a medida que agrega miembros adicionales, por lo que no necesita saber su tamaño exacto de antemano.
3. ¿Cómo varían entre sí una matriz y un diccionario?
Esta es una serie de preguntas de entrevista basadas en fundamentos que se hacen regularmente. Las siguientes son las distinciones clave entre matrices y diccionarios:
- Una matriz es una lista ordenada de elementos similares. El diccionario, por otro lado, tiene pares clave-valor.
- Los tamaños de matriz pueden cambiar dinámicamente. Tales ideas dinámicas no existen en los diccionarios.
- Antes de utilizar una matriz, se debe especificar su tamaño. No es necesario personalizar los tamaños de los diccionarios.
- Use la instrucción Redim si desea expandir el tamaño de la matriz. En los diccionarios, un elemento se puede agregar sin una declaración.
4. Enumere algunos de los beneficios y desventajas de los arreglos.
Ventajas:
- Las matrices pueden ordenar varios elementos simultáneamente.
- Otro estructuras de datos, como pilas, colas, listas enlazadas, árboles, gráficos, etc., se pueden implementar en una matriz.
- Se puede usar un índice para llegar a un elemento de una matriz.
Desventajas:
- El tamaño de una matriz debe declararse por adelantado. Sin embargo, en el momento de la declaración de la matriz, es posible que no seamos conscientes del tamaño que necesitamos.
- La estructura de la matriz es estática. Implica que el tamaño de la matriz siempre es fijo y que la asignación de memoria no se puede aumentar ni disminuir.
5. ¿A qué se refiere “Sparse Array”?
Una matriz dispersa es una matriz de datos que tiene muchas entradas con valores cero. Por el contrario, una matriz densa contiene la mayoría de sus elementos con valores distintos de cero. Los índices de una matriz dispersa, que convierte números en objetos, pueden incluir espacios. En comparación con un HashMap, son más eficientes en memoria.
6. ¿Cuándo elegiría una lista enlazada en lugar de una matriz?
Cuando use listas enlazadas en lugar de arreglos, considere:
- No necesita ningún elemento para tener acceso aleatorio.
- Donde la previsibilidad temporal es esencial, necesita inserciones y eliminaciones de tiempo constante de la lista.
- Para crear una cola de prioridad, es posible que deba colocar elementos en el centro de la lista.
- No tienes idea de cuán larga será la lista. Si el tamaño de la matriz aumenta, debe volver a declarar y duplicar la memoria, al igual que con las matrices simples.
7. ¿Qué distingue a un arreglo indexado de un arreglo asociativo?
Las distinciones principales entre matrices asociativas e indexadas se enumeran en la siguiente tabla.
- Se utiliza un par clave-valor en formato de texto o numérico para ordenar una matriz asociativa. Las claves de la matriz indexada son todas numéricas y cada clave está conectada a un valor distinto.
- En una matriz asociativa, la clave podría ser una cadena. Matriz indexada con claves enteras que comienzan en 0.
- Una tabla de dos columnas imita el comportamiento de una matriz asociativa. Las matrices indexadas son similares a una tabla de una sola columna.
- Los mapas son un tipo de matriz asociativa. Una matriz de índice no es un mapa.
8. ¿Qué ventajas tiene Heap sobre las matrices ordenadas?
La eficiencia de tiempo de utilizar Heap sobre Arrays ordenados es el beneficio clave. Si bien las operaciones de montón son más rápidas, ordenar una matriz requiere mucho tiempo. Un montón puede descubrir el elemento más pequeño considerablemente más rápido de lo que se puede ordenar una matriz.
Una colección dada de números se puede organizar de una de dos maneras utilizando matrices ordenadas. Por otro lado, para una colección dada de números, puede haber más de un montón potencial.
9. ¿Podemos definir el tamaño de la matriz como negativo?
No, no podemos definir un entero negativo para que tenga el tamaño de una matriz. No habrá un error de tiempo de compilación si declaramos. En tiempo de ejecución, sin embargo, encontraremos una NegativeArraySizeException.
10. ¿Cómo localiza el entero que falta en una matriz de 1 a 100 elementos?
El total de la serie se puede calcular aplicando la siguiente función: n (n + 1) / 2
Solo si la matriz no tiene duplicados o falta más de un número entero, funcionará esta función. Si una matriz tiene elementos duplicados, puede ordenar la matriz para ver si hay elementos equivalentes.
11. ¿Cómo encuentras el índice de un elemento en una matriz?
El índice de un elemento se puede descubrir a través de una búsqueda lineal o binaria. Hasta que localiza la coincidencia del elemento requerido, una función de búsqueda lineal recorre todos y cada uno de los elementos de una matriz. Devuelve el índice una vez que localiza el elemento coincidente. En consecuencia, la complejidad temporal de la búsqueda lineal es O. (n). Tanto una matriz ordenada como una no ordenada pueden utilizar la búsqueda lineal.
Usando una búsqueda binaria, que continuamente divide la matriz por la mitad hasta que la mediana del intervalo coincida con el elemento requerido y proporcione el índice, puede obtener el índice del elemento si la matriz está ordenada. En consecuencia, la complejidad temporal de la búsqueda binaria es O. (log n).
12. ¿Cómo puedes deshacerte de un elemento específico de una matriz?
Dado que no puede simplemente eliminar elementos de la matriz original, ya que son conjuntos fijos con un tamaño definido, el entrevistador está buscando que sugiera un enfoque diferente y aborde el problema que plantea la pregunta. El mejor curso de acción es crear una nueva matriz para eliminar un elemento. Puede duplicar los elementos de la primera matriz en esta matriz y solo incluir el elemento que desea eliminar.
Otra estrategia implica encontrar el elemento de destino en la matriz y luego invertir el orden de todos los elementos que están a la derecha del elemento de destino.
13. ¿Cómo se puede verificar la igualdad de dos arreglos?
Primero debe verificar las longitudes de las dos matrices proporcionadas. Los elementos coincidentes de ambas matrices se comparan cuando sus longitudes son iguales. Las dos matrices se considerarán iguales. si cada par de componentes en cada correspondencia es igual. No se recomienda este enfoque para verificar la igualdad de dos matrices si las matrices son de gran tamaño, ya que llevará mucho tiempo. También puede usar el método equals() incluido en la clase Arrays, sin embargo, si el entrevistador le pide que compare dos matrices sin utilizar métodos integrados, esta forma será útil.
14. Cuando hablamos de arreglos, ¿qué quiere decir con las frases "Dimensión" y "Subíndice"?
La "dimensión" de una matriz es el número de índices o subíndices necesarios para identificar a cada miembro individual. Los subíndices y las dimensiones pueden no estar claros. Una dimensión es una descripción del rango de claves permitidas, mientras que un subíndice es un número. Solo se requiere un subíndice para cada dimensión de matriz.
Por ejemplo, la matriz arr[10][5] tiene dos dimensiones. Tallas 10 en uno y 5 en el otro. Para abordar sus componentes, necesita dos subíndices. Ambos están entre 0 y 4; uno entre 0 y 9, ambos inclusive.
Preguntas de la entrevista de codificación
15. Busque un par en una matriz que tenga la suma especificada
Por ejemplo,
Entrada:
- números = [8, 7, 2, 5, 3, 1]
- objetivo = 10
Salida:
- Par encontrado (8, 2)
- Or
- Par encontrado (7, 3)
Entrada:
- números = [5, 2, 6, 8, 1, 9]
- objetivo = 12
Salida:
- Par no encontrado
16. Clasificación de matriz binaria con tiempo lineal
Ordenar una matriz binaria en tiempo lineal y en un área fija. La salida debe mostrar todos los ceros primero, luego todos los unos.
Por ejemplo,
- Entrada: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Salida: { 0, 0, 0, 0, 1, 1, 1, 1 }
Un enfoque sencillo sería calcular el número total de 0 del arreglo, digamos k, y luego llenar los primeros k índices del arreglo con 0 y los índices restantes con 1. Como alternativa, podríamos calcular cuántos 1 hay en total en el matriz k, rellene los últimos k índices de la matriz con 1 y deje el resto de los índices rellenos con 0.
El enfoque dado tiene una complejidad de tiempo O(n) y no utiliza almacenamiento adicional, donde n es el tamaño de la entrada.
17. Encuentra el producto de dos enteros más grande en una matriz.
Encuentra el mayor producto de dos números en una matriz de enteros.
Piense en la matriz 10 3 5 6 2 como ejemplo. El par (-10, -3) o (5, 6) es el producto más alto.
Pensar en cada combinación de elementos y descubrir su producto es un enfoque tonto. Si el producto del par actual es mayor que el producto máximo obtenido hasta el momento, actualice el producto máximo. Imprime los componentes del producto final al final.
La solución anterior, donde n es la cantidad de la entrada, tiene una complejidad temporal de O(n2) y no ocupa más espacio.
18. Cómo desplazar todos los ceros de la matriz al final
Mueva todos los ceros en una matriz de enteros hasta el final. La respuesta debe evitar el uso de espacios constantes y preservar el orden relativo de los componentes de la matriz.
Entrada: {1,2,3,0,8,0,4,7}
La salida será {1,2,3,8,4,7,0,0}
Coloque el elemento en la siguiente posición disponible en la matriz si el elemento actual no es cero. Rellene todos los índices restantes con 0 una vez que se hayan procesado todos los elementos de la matriz.
La solución anterior tiene una complejidad de tiempo O(n), donde n es el tamaño de la entrada.
19. Cómo ordenar una matriz con dos entradas que se intercambian en una sola operación.
Ordene una matriz en el tiempo lineal dados dos elementos intercambiados y una matriz con todos sus elementos dispuestos en orden ascendente. Suponga que la matriz no contiene duplicados.
Entrada:= [1,9,3,4,7,2] o [9,3,7,2,1,4] o [2,4,1,7,3,9]
Salida: = [1,2,3,4,7,9]
Comenzando con el segundo elemento de la matriz, el objetivo es comparar cada elemento con su predecesor. La posición de la disputa se almacena tomando dos punteros, x e y.
Actualice x al índice del elemento anterior e y al índice del elemento actual si el primero es mayor que el segundo. Actualice y al índice del elemento actual si resulta que el elemento anterior es mayor que el elemento actual.
Finalmente, cambie los elementos en los índices x e y una vez que hayamos terminado de procesar cada par de elementos adyacentes.
Debido al hecho de que el método mencionado anteriormente solo realiza un único escaneo de la matriz de entrada de tamaño n, su complejidad temporal es O(n). No se necesita espacio adicional para la solución.
20. Cómo combinar dos arreglos ordenados en su lugar.
Combine los elementos de los arreglos X[] e Y[], dos arreglos ordenados de tamaño m y n cada uno, conservando el orden ordenado, es decir, llenando X[] con los primeros m elementos más pequeños y llenando Y[] con el elementos restantes.
Si un elemento en la matriz X[] ya está en la posición correcta (es decir, el que es el más pequeño entre los elementos restantes), ignórelo; de lo contrario, reemplácelo con el elemento más pequeño, que también resulta ser el primer miembro de Y[]. Para conservar el orden de clasificación después del intercambio, transfiera el elemento (ahora en Y[0]) a su ubicación adecuada en Y[].
El tamaño de la primera matriz es my el tamaño de la segunda matriz es n, y la complejidad de tiempo es O (mn).
21. ¿Cómo reordenar una serie de artículos en posiciones altas y bajas alternas?
Reorganice una matriz de enteros para que cada miembro subsiguiente sea más grande que los elementos anteriores y siguientes. Suponga que la matriz no incluye ningún elemento duplicado.
Ordenar la matriz o utilizar espacio adicional no es necesario para un enfoque efectivo. El plan es, para empezar, el segundo miembro de la matriz y subir en dos para cada iteración del ciclo.
Intercambia los componentes si el último elemento excede al primero. De manera similar, cambie ambos elementos si el siguiente elemento es más grande que el elemento actual. Obtendremos la matriz deseada que cumpla con las restricciones especificadas al finalizar el ciclo.
22. ¿Cómo sustituir cada elemento de un arreglo sin usar un operador de división con el producto de cada elemento del arreglo?
Sin usar el operador de división, reemplace cada elemento en una matriz de enteros con el producto de todos los demás elementos.
En tiempo lineal y espacio constante, podemos utilizar la recursividad para abordar este problema. Calcular recursivamente los productos de cada elemento en el subarreglo derecho y pasar el producto del subarreglo izquierdo como parámetros de función es la noción.
La complejidad del tiempo es O(n).
23. Encuentra el elemento más extraño en una matriz en tiempo logarítmico
Dada una matriz de enteros en la que todos menos uno de los miembros tienen números pares de ocurrencias, el problema es determinar cuántas veces aparece este elemento. Encuentre el elemento que aparece impar en tiempo logarítmico y espacio constante si los mismos elementos aparecen en pares en la matriz y nunca puede haber más de dos instancias de un elemento dado en una fila.
La operación XOR nos permite resolver este problema en tiempo lineal. El objetivo es XOR cada elemento de la matriz. Solo los elementos que ocurren impares permanecen después de que los elementos que ocurren pares se cancelan entre sí.
Este problema puede incluso resolverse en tiempo O(log(n)).
24. ¿Cómo obtener el siguiente elemento más grande para cada elemento en una matriz circular?
Se debe ubicar el siguiente elemento más grande para cada elemento en una matriz circular de enteros. El primer entero más grande después de un elemento x en la matriz es el siguiente elemento mayor de ese elemento.
De derecha a izquierda, podemos operar en los elementos de la matriz. El objetivo es hacer un bucle para cada elemento x hasta que la pila esté vacía o tengamos un elemento superior encima. Configure el siguiente elemento más grande de x para que aparezca en la parte superior de la pila cuando lo haga.
25. ¿Encontrar el conteo de inversión de una matriz?
Encuentre el número total de inversiones de una matriz. Se dice que un par I j) es una inversión de un arreglo A si I j) y (A[i] > A[j]). Debemos contar cada par de estos en la matriz.
Contar todos los miembros de la matriz que son menos que él a su derecha y agregar el resultado a la salida es un enfoque sencillo.
Esta solución tiene una complejidad O(n2), donde n es el tamaño de la entrada.
26. ¿Cuál es el problema de atrapamiento de agua de lluvia?
Encontrar la mayor cantidad de agua que se puede atrapar en un conjunto dado de barras con un ancho de una unidad cada una se conoce como el problema de la "lluvia atrapada".
El objetivo es determinar la barra más alta que se puede colocar a la izquierda y derecha de cada barra. El mínimo de las barras principales a izquierda y derecha, menos la altura de la barra actual, es la cantidad de agua que se almacena encima de cada barra.
Conclusión
En comparación con otros temas de estructura de datos, las matrices son más simples. Para dominar las preguntas de la entrevista de matriz, debe tener una comprensión fundamental de las matrices.
Debe revisar exhaustivamente los fundamentos de los arreglos, incluidas las operaciones de arreglos (desde declarar/crear un arreglo hasta acceder a/modificar elementos del arreglo), así como conceptos de programación como bucles, recursividad y operadores básicos para responder con éxito las preguntas de la entrevista sobre arreglos. Reconoce el problema por completo.
Debe solicitar una aclaración si tiene alguna duda. Piense en dividir el problema en partes más manejables. Asegúrese de tener el algoritmo en mente antes de comenzar a programar; escríbalo o visualícelo en un diagrama de flujo. luego comience a escribir código.
Deje un comentario