Taula de continguts[Amaga][Espectacle]
- 1. Com es defineix un Array?
- 2. Arrays dinàmics: què són? Què els diferencia dels Basic Arrays?
- 3. Com varien una matriu i un diccionari?
- 4. Enumereu alguns dels avantatges i inconvenients de les matrius.
- 5. A què fa referència "Sparse Array"?
- 6. Quan triaríeu una llista enllaçada sobre una matriu?
- 7. Què distingeix una matriu indexada d'una matriu associativa?
- 8. Quins avantatges té Heap respecte a les matrius ordenades?
- 9. Podem definir que la mida de la matriu sigui negativa?
- 10. Com localitzeu l'enter que falta en una matriu d'1 a 100 elements?
- 11. Com es troba l'índex d'un element en una matriu?
- 12. Com pots desfer-te d'un element concret d'una matriu?
- 13. Com es pot verificar la igualtat de dues matrius?
- 14. Quan parlem de matrius, què vols dir amb les frases "Dimensió" i "Subíndex"?
- Preguntes d'entrevista de codificació
- 15. Busca una parella en una matriu que tingui la suma especificada
- 16. Ordenació de matrius binàries amb temps lineal
- 17. Trobeu el producte de dos int més gran d'una matriu.
- 18. Com moure tots els zeros de la matriu fins al final
- 19. Com ordenar una matriu amb dues entrades que es canvien en una operació.
- 20. Com combinar dues matrius ordenades al seu lloc.
- 21. Com reordenar una sèrie d'elements en posicions altes i baixes alternant?
- 22. Com substituir cada element d'una matriu sense utilitzar un operador de divisió pel producte de cada element de la matriu?
- 23. Troba l'element més estrany d'una matriu en temps logarítmic
- 24. Com obtenir l'element més gran posterior per a cada element en una matriu circular?
- 25. Trobar el recompte d'inversions d'una matriu?
- 26. Quin és el problema de l'atrapament de l'aigua de pluja?
- Conclusió
Les entrevistes de codificació contenen una sèrie de preguntes DSA. Hauríeu de ser hàbil amb les matrius si us esteu preparant per a la vostra pròxima entrevista tecnològica amb FAANG o una altra empresa tecnològica de nivell 1.
A la majoria de les entrevistes de codificació, se situa en segon lloc a Strings. Una matriu és una agrupació d'elements de dades relacionats que es mantenen molt a prop els uns dels altres a la memòria.
Com que estan connectats a tots els llenguatges de programació, com ara C, C++, Java, Python, Perl i Ruby, estan a tot arreu. Continueu llegint per obtenir alguns reptes de pràctica de codificació i preguntes i respostes d'entrevistes basades en matrius.
En aquesta publicació s'utilitzarà Python per abordar els problemes de codificació perquè és senzill d'utilitzar, entendre i ha de ser familiar per a la majoria de nosaltres.
Anem a començar.
1. Com es defineix un Array?
- Un grup de tipus de dades relacionats és una matriu.
- Les matrius sempre són fixes.
- El mateix tipus de variable s'emmagatzema en diversos llocs mitjançant objectes de matriu.
- Els tipus primitius i les referències d'objectes són compatibles amb ell.
2. Arrays dinàmics: què són? Què els diferencia dels Basic Arrays?
L'escala automàtica que proporcionen les matrius dinàmiques (també conegudes com a matrius augmentables, matrius redimensionables, matrius canviables o ArrayLists a Java) és un avantatge important.
Sempre heu de saber quants elements emmagatzemarà la vostra matriu per endavant, ja que les matrius tenen una mida fixa. Una matriu dinàmica, d'altra banda, creix a mesura que hi afegeixes membres addicionals, de manera que no cal que conegui la seva mida exacta per endavant.
3. Com varien una matriu i un diccionari?
Es tracta d'una sèrie de preguntes d'entrevista basada en conceptes bàsics que es fan regularment. Les següents són les distincions clau entre matrius i diccionaris:
- Una matriu és una llista ordenada d'elements similars. El diccionari, en canvi, té parells clau-valor.
- Les mides de la matriu poden canviar dinàmicament. Aquestes idees dinàmiques no existeixen als diccionaris.
- Abans d'utilitzar una matriu, cal especificar-ne la mida. Les mides del diccionari no cal que es personalitzin.
- Utilitzeu la instrucció Redim si voleu ampliar la mida de la matriu. Als diccionaris, es pot afegir un element sense declaració.
4. Enumereu alguns dels avantatges i inconvenients de les matrius.
Avantatges:
- Les matrius poden ordenar diversos elements simultàniament.
- un altre estructures de dades, com ara piles, cues, llistes enllaçades, arbres, gràfics, etc., es poden implementar en una matriu.
- Es pot utilitzar un índex per arribar a un element d'una matriu.
Desavantatges:
- La mida d'una matriu s'ha de declarar per endavant. En el moment de la declaració de la matriu, és possible que, però, no siguem conscients de la mida que necessitem.
- L'estructura de la matriu és estàtica. Implica que la mida de la matriu sempre és fixa i que l'assignació de memòria no es pot augmentar ni reduir.
5. A què fa referència "Sparse Array"?
Una matriu dispersa és una matriu de dades que té moltes entrades amb valors zero. En canvi, una matriu densa conté la majoria dels seus elements amb valors diferents de zero. Els índexs d'una matriu dispersa, que converteix nombres en objectes, poden incloure buits. En comparació amb un HashMap, són més eficients en memòria.
6. Quan triaríeu una llista enllaçada sobre una matriu?
Quan utilitzeu llistes enllaçades en lloc de matrius, tingueu en compte:
- No necessiteu cap element per tenir accés aleatori.
- Quan la predictibilitat temporal és essencial, necessiteu insercions i eliminacions en temps constant de la llista.
- Per crear una cua de prioritats, potser haureu de col·locar elements al centre de la llista.
- No tens ni idea de quant de llarga serà la llista. Si la mida de la matriu augmenta, heu de tornar a declarar i duplicar la memòria, igual que amb les matrius simples.
7. Què distingeix una matriu indexada d'una matriu associativa?
Les distincions principals entre matrius associatives i indexades es mostren a la taula següent.
- S'utilitza un parell clau-valor en format text o numèric per ordenar una matriu associativa. Les claus de la matriu indexada són totes numèriques i cada clau està connectada a un valor diferent.
- En una matriu associativa, la clau pot ser una cadena. Matriu indexada amb claus senceres que comencen a 0.
- Una taula de dues columnes imita el comportament d'una matriu associativa. Similars a una taula d'una sola columna són les matrius indexades.
- Els mapes són un tipus de matriu associatiu. Una matriu d'índexs no és un mapa.
8. Quins avantatges té Heap respecte a les matrius ordenades?
L'eficiència temporal d'utilitzar Heap over Sorted Arrays és el benefici clau. Tot i que les operacions de pila són més ràpides, ordenar una matriu requereix molt de temps. Un munt pot descobrir l'element més petit considerablement més ràpidament del que es pot ordenar una matriu.
Una col·lecció de números determinada es pot organitzar d'una de dues maneres mitjançant Sorted Arrays. D'altra banda, per a una determinada col·lecció de nombres, pot haver-hi més d'un munt potencial.
9. Podem definir que la mida de la matriu sigui negativa?
No, no podem definir un nombre enter negatiu com a mida d'una matriu. No hi haurà un error en temps de compilació si declarem. En temps d'execució, però, ens trobarem amb una NegativeArraySizeException.
10. Com localitzeu l'enter que falta en una matriu d'1 a 100 elements?
El total de la sèrie es pot calcular aplicant la funció següent: n (n + 1) / 2
Aquesta funció només funcionarà si la matriu no té duplicats o li falta més d'un nombre enter. Tant si una matriu té elements duplicats, podeu ordenar la matriu per veure si hi ha elements equivalents.
11. Com es troba l'índex d'un element en una matriu?
L'índex d'un element es pot descobrir mitjançant una cerca lineal o binària. Fins que localitza la coincidència de l'element requerit, una funció de cerca lineal fa un bucle sobre tots i cadascun dels elements d'una matriu. Retorna l'índex un cop localitza l'element coincident. En conseqüència, la complexitat temporal de la cerca lineal és O. (n). Tant una matriu ordenada com una no ordenada poden utilitzar la cerca lineal.
Mitjançant una cerca binària, que divideix contínuament la matriu per la meitat fins que la mediana de l'interval coincideix amb l'element requerit i proporciona l'índex, podeu obtenir l'índex de l'element si la matriu està ordenada. En conseqüència, la complexitat temporal de la cerca binària és O. (log n).
12. Com pots desfer-te d'un element concret d'una matriu?
Com que no podeu esborrar simplement elements de la matriu original, ja que són conjunts fixos amb una mida definida, l'entrevistador busca que suggereixeu un enfocament diferent i abordeu el problema que planteja la pregunta. El millor curs d'acció és crear una matriu nova per eliminar un element. Podeu duplicar els elements de la primera matriu d'aquesta matriu i incloure només l'element que voleu suprimir.
Una altra estratègia consisteix a trobar l'element objectiu a la matriu i després invertir l'ordre de tots els elements que es troben a la dreta de l'element objectiu.
13. Com es pot verificar la igualtat de dues matrius?
Primer heu de verificar les longituds de les dues matrius proporcionades. Els elements coincidents d'ambdues matrius es comparen quan les seves longituds són iguals. Les dues matrius es consideraran iguals. si cada parell de components de cada correspondència és igual. Aquest enfocament no es recomana comprovar la igualtat de dues matrius si les matrius són grans, ja que trigarà molt de temps. També podeu utilitzar el mètode equals() inclòs a la classe Arrays, però, si l'entrevistador us demana que compareu dues matrius sense utilitzar mètodes integrats, aquesta manera serà útil.
14. Quan parlem de matrius, què vols dir amb les frases "Dimensió" i "Subíndex"?
La "Dimensió" d'una matriu és el nombre d'índexs, o subíndexs, necessaris per identificar cada membre individual. És possible que els subíndexs i les dimensions no estiguin clars. Una dimensió és una descripció de l'interval de claus permeses, mentre que un subíndex és un nombre. Només cal un subíndex per a cada dimensió de matriu.
Per exemple, la matriu arr[10][5] té dues dimensions. Talles 10 d'una i 5 de l'altra. Per abordar els seus components, necessiteu dos subíndexs. Tots dos estan entre 0 i 4; un entre 0 i 9, inclosos.
Preguntes d'entrevista de codificació
15. Busca una parella en una matriu que tingui la suma especificada
Per exemple,
entrada:
- nombres = [8, 7, 2, 5, 3, 1]
- objectiu = 10
sortida:
- Parell trobat (8, 2)
- Or
- Parell trobat (7, 3)
entrada:
- nombres = [5, 2, 6, 8, 1, 9]
- objectiu = 12
sortida:
- No s'ha trobat la parella
16. Ordenació de matrius binàries amb temps lineal
Ordena una matriu binària en temps lineal i en una àrea fixa. La sortida hauria de mostrar primer tots els zeros, després tots els uns.
Per exemple,
- Entrada: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Sortida: {0, 0, 0, 0, 1, 1, 1, 1}
Un enfocament senzill seria calcular el nombre total de 0s de la matriu, per exemple k, i després omplir els primers k índexs de la matriu amb 0 i els índexs restants amb 1. Com a alternativa, podríem calcular quants 1 són totals a la matriu. matriu k, ompliu els darrers k índexs de la matriu amb 1 i deixeu la resta d'índexs amb 0.
L'enfocament donat té una complexitat de temps O(n) i no utilitza cap emmagatzematge addicional, on n és la mida de l'entrada.
17. Trobeu el producte de dos int més gran d'una matriu.
Troba el producte més gran de dos nombres en una matriu enter.
Penseu en la matriu 10 3 5 6 2 com a exemple. El parell (-10, -3) o (5, 6) és el producte més alt.
Pensar en cada combinació d'elements i descobrir el seu producte és un enfocament absurd. Si el producte de la parella actual és més gran que el producte màxim obtingut fins ara, actualitzeu el producte màxim. Imprimeix per últim els components del producte final.
La solució anterior, on n és la quantitat de l'entrada, té una complexitat temporal de O(n2) i no ocupa més espai.
18. Com moure tots els zeros de la matriu fins al final
Mou tots els zeros d'una matriu d'enters fins al final. La resposta hauria d'evitar utilitzar espai constant i preservar l'ordre relatiu dels components de la matriu.
Entrada: {1,2,3,0,8,0,4,7}
La sortida serà {1,2,3,8,4,7,0,0}
Posa l'element a la següent posició disponible a la matriu si l'element actual no és zero. Ompliu tots els índexs restants amb 0 un cop s'hagin processat tots els elements de la matriu.
La solució anterior té una complexitat temporal O(n), on n és la mida de l'entrada.
19. Com ordenar una matriu amb dues entrades que es canvien en una operació.
Ordena una matriu en el temps lineal donat dos elements intercanviats i una matriu amb tots els seus elements disposats en ordre ascendent. Fingir que la matriu no conté duplicats.
Entrada:= [1,9,3,4,7,2] o [9,3,7,2,1,4] o [2,4,1,7,3,9]
Sortida: = [1,2,3,4,7,9]
Començant pel segon element de la matriu, l'objectiu és comparar cada element amb el seu predecessor. La posició de la disputa s'emmagatzema prenent dos punters, x i y.
Actualitzeu x a l'índex de l'element anterior i y a l'índex de l'element actual si el primer és més gran que el segon. Actualitzeu y a l'índex de l'element actual si resulta que l'element anterior és més gran que l'element actual.
Finalment, canvieu els elements als índexs x i y un cop hàgim acabat de processar cada parell d'elements adjacents.
A causa del fet que el mètode esmentat només realitza una sola exploració de la matriu d'entrada de mida n, la seva complexitat temporal és O(n). No es necessita espai addicional per a la solució.
20. Com combinar dues matrius ordenades al seu lloc.
Combineu els elements de les matrius X[] i Y[], dues matrius ordenades de mida m i n cadascuna, mantenint l'ordre ordenat, és a dir, omplint X[] amb els primers m elements més petits i omplint Y[] amb el elements restants.
Si un element de la matriu X[] ja es troba a la posició correcta (és a dir, el que és el més petit entre els elements restants), ignoreu-lo; en cas contrari, substituïu-lo per l'element més petit, que també passa a ser el primer membre de Y[]. Per mantenir l'ordre ordenat després de l'intercanvi, transferiu l'element (ara a Y[0]) a la seva ubicació correcta a Y[].
La mida de la primera matriu és m i la mida de la segona matriu és n, i la complexitat del temps és O(mn).
21. Com reordenar una sèrie d'elements en posicions altes i baixes alternant?
Reorganitza una matriu d'enters de manera que cada membre posterior sigui més gran que els elements anteriors i següents. Suposem que la matriu no inclou cap element duplicat.
Ordenar la matriu o utilitzar espai addicional no és necessari per a un enfocament eficaç. El pla és, per començar, el segon membre de la matriu i puja dos per cada iteració del bucle.
Canvia els components si l'últim element supera el primer. De manera similar, canvieu els dos elements si l'element següent és més gran que l'element actual. Obtenim la matriu desitjada que compleixi amb les restriccions especificades al final del bucle.
22. Com substituir cada element d'una matriu sense utilitzar un operador de divisió pel producte de cada element de la matriu?
Sense utilitzar l'operador de divisió, substituïu cada element d'una matriu sencer pel producte de tots els altres elements.
En temps lineal i espai constant, podem utilitzar la recursivitat per abordar aquest problema. La noció és calcular recursivament els productes de cada element del subbarrat dret i passar el producte del subbarrat esquerre com a paràmetres de funció.
La complexitat temporal és O(n).
23. Troba l'element més estrany d'una matriu en temps logarítmic
Donada una matriu sencer en què tots els membres menys un tenen nombres parells d'ocurrències, el problema és determinar quantes vegades apareix aquest element. Trobeu l'element estrany en temps logarítmic i espai constant si els mateixos elements apareixen en parells a la matriu i mai no hi pot haver més de dues instàncies d'un element donat en una fila.
L'operació XOR ens permet resoldre aquest problema en temps lineal. L'objectiu és XOR tots els elements de la matriu. Només queden els elements que ocorren senars després que els elements parells es cancel·lin mútuament.
Aquest problema fins i tot es pot resoldre en temps O(log(n)).
24. Com obtenir l'element més gran posterior per a cada element en una matriu circular?
S'ha de localitzar el següent element més gran per a cada element d'una matriu d'enteres circulars. El primer nombre enter més gran després d'un element x de la matriu és l'element més gran posterior d'aquest element.
De dreta a esquerra, podem operar amb elements de matriu. L'objectiu és fer un bucle per a cada element x fins que la pila estigui buida o tinguem un element superior al damunt. Estableix el següent element més gran de x perquè aparegui a la part superior de la pila quan ho faci.
25. Trobar el recompte d'inversions d'una matriu?
Trobeu el nombre total d'inversions d'una matriu. Un parell I j) es refereix a una inversió d'una matriu A si I j) i (A[i] > A[j]). Hem de comptar cada parell d'aquests a la matriu.
Comptar tots els membres de la matriu que són menys que ell a la seva dreta i afegir el resultat a la sortida és un enfocament senzill.
Aquesta solució té una complexitat O(n2), on n és la mida de l'entrada.
26. Quin és el problema de l'atrapament de l'aigua de pluja?
Trobar la màxima aigua que es pot atrapar en un conjunt determinat de barres amb una amplada d'una unitat cadascuna es coneix com el problema de la "pluja atrapada".
L'objectiu és determinar la barra més alta que es pot col·locar a l'esquerra i a la dreta de cada barra. El mínim de les barres davanteres a l'esquerra i a la dreta, menys l'alçada de la barra actual, és la quantitat d'aigua que s'emmagatzema a la part superior de cada barra.
Conclusió
En comparació amb altres temes d'estructura de dades, les matrius són més senzilles. Per respondre a les preguntes d'entrevista de matriu, heu de tenir una comprensió fonamental de les matrius.
Hauríeu de revisar àmpliament els fonaments de les matrius, incloses les operacions de matriu (des de la declaració/creació d'una matriu fins a l'accés/modificació d'elements de matriu), així com conceptes de programació com bucles, recursivitat i operadors bàsics per respondre amb èxit a les preguntes de l'entrevista de matriu. Reconeix el problema completament.
Hauríeu de demanar aclariments si teniu cap consulta. Penseu a dividir el problema en parts més manejables. Assegureu-vos de tenir l'algoritme en ment abans de començar a programar; Anoteu-lo o visualitzeu-lo en un diagrama de flux. després comenceu a escriure codi.
Deixa un comentari