[Powered by Google Translate] [Seminari: Entrevistes Tècnics] [Kenny Yu, Harvard University] [Aquesta és CS50.] [CS50.TV] Hola a tots, sóc Kenny. Actualment sóc un jove ciència que estudia informàtica. Sóc un ex TF CS, i m'agradaria tenir això quan era un underclassman, i és per això que poso a aquest seminari. Així que espero que us agradi. Aquest seminari tracta d'entrevistes tècniques, i tots els meus recursos es poden trobar en aquest enllaç, aquest enllaç aquí, un parell de recursos. Així que vaig fer una llista de problemes, en realitat, força problemes. També una pàgina de recursos en general on podem trobar consells sobre com preparar-se per una entrevista, consells sobre el que ha de fer durant una entrevista real, així com la forma d'abordar els problemes i els recursos per a futures referències. És tot en línia. I només per prologar aquest seminari, un descàrrec de responsabilitat, com això no hauria - la seva preparació de l'entrevista no s'ha de limitar a aquesta llista. Això només pretén ser una guia, ia més s'hauria de prendre tot el que dic amb un gra de sal, sinó també utilitzar tot el que solia ajudar-lo en la seva preparació de l'entrevista. 

Vaig a accelerar a través de les següents diapositives pel que podem arribar als estudis de casos reals. L'estructura d'una entrevista per a un Postion enginyeria de programari, típicament és de 30 a 45 minuts, múltiples rondes, depenent de la companyia. Sovint se li codificació en un tauler blanc. Així que una pissarra blanca com aquesta, però sovint en un format més petit. Si tens una entrevista telefònica, vostè probablement va a utilitzar ja sigui collabedit o un document de Google Docs perquè vegin vostès viuen codificació mentre que vostè està sent entrevistat per telèfon. Una entrevista en si és de 2 o 3 problemes prova els teus coneixements d'informàtica. I serà gairebé definitivament involucrar codificació. Els tipus de preguntes que es veuen són en general les estructures de dades i algoritmes. I en fer aquest tipus de problemes, li preguntaran, com, quin és el temps i la complexitat de l'espai, gran O? Sovint, també demanen més alt nivell preguntes, així, el disseny d'un sistema, Com dissenyar el codi? Què interfícies, el que les classes, els mòduls que el que té en el seu sistema, i com aquestes interactuen entre si? Així que les estructures de dades i algoritmes, així com sistemes de disseny. 

Alguns consells generals Abans d'aprofundir en els estudis de casos. Crec que la regla més important és sempre estar pensant en veu alta. L'entrevista se suposa que és la seva oportunitat per mostrar el seu procés de pensament. L'objectiu de l'entrevista és que l'entrevistador per avaluar com pensa i com vostè va a través d'un problema. La pitjor cosa que pots fer és estar en silenci durant tota l'entrevista. Això és gens bo. Quan se li dóna a una pregunta, vostè també vol assegurar-se que entén la pregunta. Així que repeteixo la pregunta de nou en les seves pròpies paraules i tractar de treballar a fons alguns casos de prova senzills per assegurar-se que entén la pregunta. Treballant a través d'un parell de casos de prova també li donarà una intuïció sobre com resoldre aquest problema. Fins i tot podria descobrir alguns patrons per ajudar a resoldre el problema. La seva gran consell és no sentir-se frustrat. No es frustri. Les entrevistes són un repte, però el pitjor que es pot fer, a més de ser silenciosa, es visiblement frustrat. No vol donar aquesta impressió a un entrevistador. Una cosa que vostè - així, moltes persones, quan van a una entrevista, en el seu intent de tractar de trobar la millor solució primer, quan en realitat, en general hi ha una solució òbvia. Pot ser que sigui lent, pot ser ineficient, sinó que només ha de dir-ho, només pel que té un punt de partida per treballar millor. També, assenyalant la solució és lent, en termes de O gran complexitat de temps o la complexitat de l'espai, mostrarà l'entrevistador que vostè entén aquests problemes en escriure codi. Així que no tingui por d'arribar amb el primer algorisme més simple i després treballar millor des d'allà. Qualsevol pregunta fins ara? Bé. 

Així que anem a bussejar en el nostre primer problema. "Donada una matriu d'enters n, escriu una funció que estudia la matriu en lloc de tal manera que totes les permutacions dels n enters són igualment probables. " I se suposa que té disponible un generador de nombre enter aleatori que genera un nombre enter en l'interval de 0 a i, rang mitjà. Tothom entén aquesta pregunta? Et dono una matriu d'enters n, i vull que barájalo. En el meu directori, vaig escriure uns quants programes per demostrar el que vull dir. Vaig a estudiar una matriu de 20 elements, -10 A 9, i vull donar sortida a una llista com aquesta. Així que aquesta és la meva matriu ordenada d'entrada, i vull que barájalo. Anem a fer-ho de nou. Tothom entén la pregunta? Bé. Així que li toca a vostè. Quines són algunes idees? Pot fer-ho com n ^ 2, n log n, n? Obert a suggeriments. Bé. Així que una idea, suggerida per l'Emmy, és calcular primer un nombre aleatori, sencer aleatori, en un rang de 0 a 20. Així que assumir la nostra matriu té una longitud de 20. En el nostre diagrama de 20 elements, aquesta és la nostra matriu d'entrada. I ara, el seu suggeriment és crear una nova matriu, de manera que aquesta serà la matriu de sortida. I basat en l'i retornat per rand - així que si jo estava, diguem, 17, copiar l'element 17 en la primera posició. Ara hem d'eliminar - hem de canviar tots els elements aquí de manera que tenim un buit a l'extrem i no hi ha forats en el medi. I ara repetim el procés. Ara triem un nombre enter aleatori entre 0 i 19. Tenim una i nou aquí, i copiem aquest element en aquesta posició. Llavors canviem articles una i repetim el procés fins que tinguem la nostra nova matriu completa. Quin és el temps d'execució d'aquest algorisme? Bé, anem a considerar l'impacte d'això. Estem canviant cada element. Quan eliminar aquesta i, que estan canviant tots els elements després que a l'esquerra. I aquesta és una operació O (n) Cost perquè el que si s'elimina el primer element? Així, per cada retir, remenem - cada retir incorre en una operació O (n), i ja que tenim n mudances, això condueix a una operació O (n ^ 2) shuffle. Bé. Així bon començament. Bon començament. 

Un altre suggeriment és utilitzar alguna cosa conegut com el shuffle Knuth, o la confusió Fisher-Yates. I en realitat és un shuffle temps lineal. I la idea és molt similar. Un cop més, tenim la nostra matriu d'entrada, però en lloc d'utilitzar dues matrius per a la nostra entrada / sortida, s'utilitza la primera part de la matriu per seguir la pista de la nostra part estudiat, i fem un seguiment, i després deixar la resta de la nostra gamma per a la part unshuffled. Això és el que vull dir. Comencem amb - triem una i, una matriu a partir de 0 a 20. El nostre actual del punter apunta al primer índex. Triem alguns i aquí i ara canviem. Així que si això era 5 i això va ser 4, la matriu resultant tindrà 5 aquí i 4 aquí. I ara observem un marcador d'aquí. Tot a l'esquerra s'estudien, i tot el que està a la dreta unshuffled. I ara podem repetir el procés. Triem un índex aleatori entre 1 i 20 ara. Així que suposem que el nostre nou jo aquí. Ara canviem això i amb la nostra nova posició actual aquí. Així que fer un intercanvi d'anada i tornada així. Permetin-me que aparegui el codi perquè sigui més concret. Comencem amb la nostra elecció d'i - comencem amb i igual a 0, triem un lloc a l'atzar j a la part unshuffled de la matriu, i a n-1. Així que si sóc aquí, triar un índex aleatori entre aquí i la resta de la matriu, i intercanviem. Aquest és tot el codi necessari per barrejar la teva matriu. Alguna pregunta? 

Doncs bé, un necessita pregunta és, per què és això correcte? Per què totes les permutacions igualment probable? I no vaig a passar per la prova d'això, però molts problemes en ciències de la computació pot ser provat a través de la inducció. Quants de vostès estan familiaritzats amb la inducció? Bé. Cool. Així que vostè pot demostrar l'exactitud d'aquest algorisme per simple inducció, on la hipòtesi d'inducció seria assumir que meva baralla torna cada permutació mateixa probabilitat als elements per primera vegada. Ara, considerem i + 1. I per la manera com triem el nostre índex j per intercanviar, això porta a - i després es treballa en els detalls, almenys una prova completa de per què aquest algorisme retorna totes les permutacions amb una probabilitat igualment probables. 

Tot problema dreta, al costat. Així que "donat un conjunt de nombres enters, postive, zero, negatiu, escriure una funció que calcula la suma màxima de qualsevol submatriu continueous de la matriu d'entrada. " Un exemple aquí és, en el cas que tots els nombres són positius, a continuació, en l'actualitat la millor opció és prendre tot el conjunt. 1, 2, 3, 4, és igual a 10. Quan vostè té alguns aspectes negatius d'allà, en aquest cas només volem els dos primers perquè triar -1 i / o -3 farà que la nostra suma cap avall. De vegades pot ser que hàgim de començar al mig de la matriu. De vegades hem de triar res en absolut, és millor que no tenir res. I de vegades és millor prendre la caiguda, perquè després del que és super gran. Llavors, alguna idea? (Estudiant, inintel · ligible) >> Si. Suposem que jo no prenc -1. Llavors, o trio 1.000 i 20.000, o m'acaba de triar els 3 milions de dòlars. Bé, la millor opció és prendre tots els números. Aquesta -1, tot i ser negatiu, la suma total és millor que jo no fos a prendre -1. Així que un dels consells que he esmentat abans va anar a dir el obvi clarament i la solució de força bruta primer. Quina és la solució de força bruta en aquest problema? Sí? [Jane] Bé, crec que la solució de força bruta seria la de sumar totes les combinacions possibles (inintel · ligible). [Yu] Bé. Així que la idea de Jane és prendre cada possible - Estic parafrasejant - és prendre cada submatriu continu possible, calcular la seva suma, i després prendre el màxim de tots els subconjunts possibles contínues. El que identifica de manera exclusiva una submatriu al meu matriu d'entrada? Com, què dues coses que necessito? Sí? (Estudiant, inintel · ligible) Dret >>. Un límit inferior en l'índex i l'índex del límit superior determina de manera única una submatriu contínua. [Estudiant Dona] Estem estimant que és una sèrie de nombres únics? [Yu] No tant el dubte és, estem assumint la nostra àmplia - és la nostra matriu tots els nombres únics, i la resposta és no. 

Si utilitzem la nostra solució de força bruta, llavors els índexs d'inici / fi únicament determina la nostra subarray contínua. Així que si iterar per a totes les entrades d'inici possibles, i per a totes les entrades finals> o = per començar, i n <, a calcular la suma, i després prenem la suma màxima que hem vist fins ara. Està clar? Quina és la gran O d'aquesta solució? TimeWise. No del tot n ^ 2. Recordeu que iterar des de 0 a n, així que això és un bucle for. Ens iterar de nou gairebé des de l'inici fins al final, per un altre bucle. I ara, dins d'això, hem de resumir cada entrada, així que això és un altre bucle for. Així que tenim tres bucles for niats, n ^ 3. Bé. Això va com punt de partida. La nostra solució no és pitjor que n ^ 3. Tots entenen la solució de força bruta? 

Bé. Una solució millor és utilitzar una idea anomenada de programació dinàmica. Si vostè pren CS124, que és Algorismes i Estructures de Dades, et tornaràs molt familiaritzat amb aquesta tècnica. I la idea és, intentar construir solucions als problemes més curts primer. Què vull dir amb això és que en l'actualitat s'ha de preocupar de dues coses: d'inici i fi. I això és molest. I si poguéssim desfer d'un d'aquests paràmetres? Una idea és - estem donat al nostre problema original, trobar la suma màxima de qualsevol submatriu en un interval [O, n-1]. I ara tenim un nou subproblema, on sabem, al nostre actual índex i, sabem que hem de concloure allà. La nostra subarray ha d'acabar en l'índex actual. Així que el problema que queda és, On hauríem de començar el nostre subarray? Té això sentit? Bé. Així que he codificat això, i anem a veure el que això significa. Al codirectory, hi ha un programa anomenat subarray, i es triga nombre d'elements, i torna la suma subarray màxim en la cistella arrossegant els peus. Així que en aquest cas, el nostre subarray màxima és de 3. I això ha pres simplement usant 2 i 1. Anem a córrer de nou. També és 3. Però aquesta vegada, tingui en compte com hem arribat fins al 3. Ens prenem el - que acabem de prendre la 3 es perquè està envoltat de negatius en ambdós costats, que aportarà una suma <3. Anem a córrer en 10 articles. Aquesta vegada es tracta de 7, prenem el líder 3 i 4. Aquesta vegada és 8, i obtenim que prenent 1, 4 i 3. Així que per donar-li una intuïció sobre com podem resoldre aquest problema transformat, anem a fer una ullada al subgrup. Ens donen la matriu d'entrada, i sabem que la resposta és 8. Prenem l'1, 4, i 3. Però donem una ullada a com en realitat ens van donar aquesta resposta. Fem una ullada a la submatriu màxim que va desembocar en cada un d'aquests índexs. Quina és la submatriu màxima que ha d'acabar en la primera posició? [Estudiant] Zero. >> Zero. Això sí, no es prenen el -5. Aquí serà 0 també. Sí? (Estudiant, inintel · ligible) [Yu] Oh, ho sento, és un -3. Així que aquest és un 2, aquest és un -3. Bé. Així -4, quina és la submatriu màxim per posar fi a aquesta posició on -4 és en? Zero. Un? 1, 5, 8. Ara, he de acabar en el lloc on es troba a -2. Així 6, 5, 7, i l'última és 4. Sabent que aquests són les meves entrades per al problema transformat en la qual ha d'acabar en cada un d'aquests índexs, llavors la meva resposta final és simplement, prendre un escombrat a través, i prendre el nombre màxim. Així que en aquest cas és 8. Això implica que la submatriu màxima acaba en aquest índex, i va començar en algun lloc abans d'ella. Tothom entén aquesta submatriu transformat? 

Bé. Bé, anem a esbrinar la recurrència d'això. Anem a considerar només les primeres entrades. Així que aquí era 0, 0, 0, 1, 5, 8. I després estava un -2 aquí, i això la va portar a 6. Així que si dic a l'entrada en la posició i subproblema (i), Com puc utilitzar la resposta a un subproblema anterior Per respondre a aquesta subproblema? Si miro, diguem, però aquesta entrada. Com puc calcular la resposta 6 per mirar una combinació d'aquesta matriu i les respostes a subproblemes anteriors d'aquesta matriu? Sí? [Estudiant Dona] Vostè pren la matriu de sumes en la posició correcta abans d'ella, de manera que la 8, a continuació, afegir el subproblema actual. [Yu] Així que el suggeriment és mirar a aquests dos nombres, aquest nombre i aquest nombre. Així que aquest 8 es refereix a la resposta per al subproblema (i - 1). I anem a trucar al meu matriu d'entrada A. Per tal de trobar una submatriu màxima que acaba en la posició i, Tinc dues opcions: o bé pot continuar la submatriu que va acabar en l'índex anterior, o començar una nova matriu. Si jo fos a continuar la submatriu que es va iniciar en l'índex anterior, llavors la suma màxima que pot assolir és la resposta a l'anterior subproblema a més de l'entrada de la matriu actual. Però, també té l'opció d'iniciar un nou subconjunt, en aquest cas la suma és 0. Així que la resposta és, com a màxim de 0, subproblema i - 1, a més de l'entrada de la matriu actual. ¿Aquesta repetició té sentit? La nostra recurrència, com acabem de descobrir, és subproblema i és igual al màxim de la subproblema anterior més la meva entrada de la matriu actual, el que significa seguir la submatriu anterior, o 0, començar una nova submatriu al meu índex actual. I un cop que hem construït aquesta taula de solucions, llavors la nostra resposta final, acaba de fer un escombrat lineal a través de la matriu subproblema i prendre el nombre màxim. Es tracta d'una aplicació exacta del que acabo de dir. Així que vam crear una matriu subproblema nou subproblemes. La primera entrada és o bé 0 o la primera entrada, la màxima de les dues. I per a la resta dels subproblemes fem servir la repetició exacta que acaba de descobrir. Ara es calcula el màxim de la nostra àmplia subproblemes, i aquesta és la nostra resposta final. 

Llavors, quant espai estem fent servir en aquest algorisme? Si només has pres CS50, llavors no podria haver discutit molt espai. Bé, una cosa a tenir en compte és que vaig trucar a malloc aquí amb mida n. Què és el que et suggereix? Aquest algorisme utilitza l'espai lineal. Podem fer-ho millor? Hi ha res que et dones compte que no és necessari per calcular la resposta final? Crec que una millor pregunta és, ¿quina informació no hem de portar tot el camí fins al final? Ara bé, si ens fixem en aquestes dues línies, que només es preocupen pel subproblema anterior, i que només es preocupen per el màxim que he vist fins ara. Per calcular la nostra resposta final, no necessitem tota la matriu. Només necessitem el darrer número, els dos últims números. De l'últim número de la matriu subproblema, i l'últim número de la màxima. Així, de fet, es pot fusionar aquests bucles junts i van des de l'espai lineal a l'espai constant. Suma fins al moment actual, aquí, reemplaça el paper del subproblema, la nostra àmplia subproblema. Així suma actual, fins ara, és la resposta a la subproblema anterior. I aquesta suma, fins ara, ocupa el lloc del nostre màx. Calculem el màxim a mesura que avancem. I així anem des de l'espai lineal constant en l'espai, i també tenim una solució al nostre problema lineal submatriu. 

Aquest tipus de preguntes que vostè rebrà durant una entrevista. Quina és la complexitat de temps, el que és la complexitat de l'espai? Es pot fer millor? Hi ha coses que no són necessàries per mantenir en tot? Ho vaig fer per posar en relleu les anàlisis que s'ha de prendre pel seu compte com el que està treballant a través d'aquests problemes. Sempre que s'estigui preguntant, "¿Puc fer-ho millor?" De fet, podem fer alguna cosa millor que això? Una espècie de pregunta capciosa. No pots, perquè cal almenys llegir l'entrada al problema. Així que el fet que vostè necessita com a mínim llegir l'entrada al problema significa que no es pot fer res millor que el temps lineal, i no es pot fer res millor que un espai constant. Així que aquest és, de fet, la millor solució per aquest problema. Preguntes? Bé. 

Stock problema del mercat: "Donada una matriu d'enters n, positiu, zero o negatiu, que representen el preu d'una acció més de n dies, escriure una funció per calcular el benefici màxim que es pot fer tenint en compte que vostè compra i venda de valors en exactament 1 núm aquests dies. " Essencialment, volem comprar barat, vendre car. I volem esbrinar el millor benefici que podem fer. Tornant al meu consell, quin és el clar immediatament, resposta més simple, però és lent? Sí? (Estudiant, inintel · ligible) >> Sí >> Pel que s'acaba d'anar bé i mirar els preus de les accions en cada punt en el temps, (inintel · ligible). [Yu] Bé, pel que la seva solució - el suggeriment de la computació el més baix i el més alt computar no funciona necessàriament perquè la més alta podria passar abans de la més baixa. Llavors, quina és la solució de força bruta per aquest problema? Quines són les dues coses que necessito per determinar unívocament el benefici que faig? Dreta. La solució de força bruta és - oh, per la qual cosa, el suggeriment de George és que només necessiten dos dies per determinar unívocament el benefici d'aquests dos dies. Així de calcular cada parell, com compra / venda, calcular el benefici, que pot ser negatiu o positiu o zero. Calculeu el guany màxim que fem després de iterar sobre tots els parells de dies. Aquesta serà la nostra resposta final. I que la solució serà O (n ^ 2), perquè no hi ha n triar dos parells - de dies que es pot triar entre els dies finals. Molt bé, així que no vaig a anar sobre la solució de força bruta aquí. Jo et diré que hi ha una solució log n n. Què algorisme veu actualment sabem que és n log n? No és una pregunta capciosa. 

Combinar tipus. Merge sort és n log n, i, de fet, una forma de resoldre aquest problema és utilitzar una mena de barreja tipus d'idea es diu, en general, dividir i conquerir. I la idea és la següent. Vol calcular la millor compra / venda parella a la meitat esquerra. Troba el millor benefici que vostè pot fer, només amb el núm primera de dos dies. Llavors vostè vol oompute la millor compra / venda parella a la meitat dreta, de manera que el n duren més de dos dies. I ara la pregunta és, com podem combinar aquestes solucions de tornar a estar junts? Sí? (Estudiant, inintel · ligible) >> Okay. Així que permetin-me fer un dibuix. Sí? (George, inintel · ligible) >> Exactament. Solució de George és exactament correcte. Així que el seu suggeriment és, en primer lloc calcular millor la compra / venda parell, i que es produeix en la meitat esquerra, així que anomenarem a aquesta esquerra, esquerra. La millor compra / venda una que es produeix en la meitat dreta. Però si només es comparen aquests dos nombres, estem perdent el cas on comprar i vendre aquí en algun lloc de la meitat dreta. Comprem a la meitat esquerra, vendre a la meitat dreta. I la millor manera de calcular millor la compra / venda una que s'estén per les dues meitats és calcular el mínim aquí i calcular el màxim aquí i prendre la seva diferència. Així que els dos casos en què la parella de compra / venda es produeix només aquí, només aquí, o en ambdues meitats està definida per aquests tres nombres. Així que el nostre algorisme per combinar les nostres solucions de nou junts, volem calcular millor la compra / venda parella on comprem a la meitat esquerra i vendre a la meitat dreta. I la millor manera de fer-ho és calcular el preu més baix en el primer temps, el preu més alt en la meitat dreta, i prendre la seva diferència. Els beneficis resultants tres, aquests tres nombres, es pren el màxim dels tres, i aquest és el millor benefici que vostè pot fer durant aquests primers dies i al final. Aquí les línies importants estan en vermell. Aquesta és una crida recursiva per calcular la resposta en la meitat esquerra. Aquesta és una crida recursiva per calcular la resposta en la meitat dreta. Aquests dos bucles per calcular el mínim i el màxim del medi a l'esquerra i la dreta, respectivament. Ara puc calcular el benefici que s'estén per les dues meitats, i la resposta final és el màxim d'aquests tres. Bé. 

Així que, sí, tenim un algorisme, però la pregunta més gran, Quina és la complexitat de temps d'això? I la raó per la qual he esmentat tipus de combinació és que aquesta forma de dividir la resposta en dos i després la fusió de les nostres solucions de nou junts és exactament el tipus d'espècie de barreja. Així que permetin-me anar a través de la durada. Si es defineix una funció de t (n) ser el nombre de passos per an dies, nostres dues trucades recursives són cadascun costarà t (n / 2), i hi ha dues d'aquestes trucades. Ara he de calcular el mínim de la meitat esquerra, que puc fer en n / 2 hora, més el màxim de la meitat dreta. Així que això és només n. I després, a més d'un treball constant. I aquesta equació de recurrència és exactament l'equació de recurrència de tipus de mescla. I tots sabem quin tipus de mescla és log n n temps. Per tant, el nostre algorisme és també n log n temps. ¿Aquesta iteració té sentit? Només una breu recapitulació del següent: T (n) és el nombre de passos per calcular el màxim benefici en el transcurs de n dies. La manera com ens separem les nostres crides recursives està trucant a la nostra solució en els primers dies de n / 2, així que això és una crida, i després trucar de nou a la segona meitat. Així que això és una crida a una altra. I llavors ens trobem amb un mínim en la meitat esquerra, el que podem fer en el temps lineal, trobar el màxim de la meitat dreta, el que podem fer en temps lineal. Així que n / 2 + n / 2 és n. Llavors tenim un treball constant, que és com fer aritmètica. Aquesta equació de recurrència és exactament l'equació de recurrència per tipus de mescla. Per tant, el nostre algoritme de shuffle és també n log n. Llavors, quant espai estem utilitzant? Tornem al codi. 

Una millor pregunta és, quants marcs de pila és el que sempre tenen en un moment donat? Ja que estem utilitzant recursivitat, el nombre de marcs de pila determina el nostre ús de l'espai. Anem a considerar n = 8. Cridem a estudiar els dies 8, que cridarà a estudiar a les primeres quatre entrades, que cridarà a una baralla en les primeres dues entrades. Així que la nostra pila és - aquesta és la nostra pila. I llavors cridem a estudiar de nou els dies 1, i això és el que el nostre escenari base és, per la qual cosa tornar immediatament. Tenim alguna vegada té més de marcs de pila aquesta gent? No Com que cada vegada que fem una invocació, una invocació recursiva per barrejar, dividim la nostra mida a la meitat. Així que el nombre màxim de marcs de pila mai tenim en un moment donat és de l'ordre dels marcs de registre núm pila. Cada marc de pila disposa d'espai constant, i per tant la quantitat total d'espai, la quantitat màxima d'espai que ha consumit alguna vegada és O (log n) espai on n és el nombre de dies. 

Ara bé, sempre et preguntes, "Podem fer-ho millor?" I en particular, ¿es pot reduir a un problema que ja hem resolt? Un consell: només discuteixen dos problemes abans d'això, i que no serà aleatori. Podem convertir aquest problema en el mercat de valors problema subarray màxima. Com podem fer això? Un de vostès? Emmy? (Emmy, inintel · ligible) [Yu] Exactament. Així que el problema subarray màxima, estem buscant a una suma sobre una submatriu contínua. I Emmy suggeriment per al problema accions, considerar els canvis o deltes. I una foto d'això és - aquest és el preu d'una acció, però si prenem la diferència entre cada dia consecutiu - així veiem que el preu màxim, el benefici màxim que podíem fer és que si anem a comprar aquí i vendre aquí. Però donem una ullada a la contínua - veurem el problema submatriu. Així que aquí, podem fer - anar des d'aquí fins aquí, tenim un canvi positiu, i després anar des d'aquí fins aquí tenim un canvi negatiu. Però després, en passar d'aquí fins aquí tenim un canvi positiu enorme. I aquests són els canvis que es volen sumar a aconseguir el nostre benefici final. Llavors tenim més canvis negatius aquí. La clau per reduir el nostre problema d'estoc al nostre problema subarray màxim és considerar els deltes entre els dies. Així que vam crear una nova matriu anomenada deltes, inicialitzar la primera entrada sigui 0, i després per a cada delta (i), deixi que sigui la diferència de la meva entrada array (i), i la matriu (i - 1). Llavors diem al nostre procediment de rutina per a un subconjunt maximal passant per una sèrie de Delta. I perquè subarray màxim és el temps lineal, i aquesta reducció, el procés de creació d'aquesta matriu delta, També és un temps lineal, llavors la solució final per les accions és O (n) el treball més O (n) el treball, segueix sent O (n) el treball. Així que tenim una solució en temps lineal al nostre problema. Tothom entén aquesta transformació? 

En general, una bona idea que vostè sempre ha de tenir és tractar de reduir un problema nou que s'està veient. Si sembla familiar a un vell problema, intentar reduir-la a un vell problema. I si es pot utilitzar totes les eines que he fet servir a l'antic problema per resoldre el nou problema. Així que per acabar, entrevistes tècniques són desafiants. Aquests problemes són probablement alguns dels problemes més difícils que es poden veure en una entrevista, així que si vostè no entén tots els problemes que acabem de cobrir, està bé. Aquests són alguns dels problemes més difícils. Pràctica, pràctica, pràctica. Em va donar un munt de problemes en el volant, així que definitivament comprovar aquests cap a fora. I bona sort en les seves entrevistes. Tots els meus recursos es publiquen en aquest enllaç, i un dels meus amics grans s'ha ofert a fer simulacres d'entrevistes tècniques, així que si vostè està interessat, un eMail Yao en aquesta direcció de correu electrònic. Si té algunes preguntes, em pots preguntar. Vostès tenen preguntes específiques relacionades amb entrevistes tècniques o d'altres problemes que hem vist fins ara? Bé. Bé, bona sort en les seves entrevistes. [CS50.TV]