Google-haastattelukysymykset dekonstruoitu: synonyymit kyselyt

Tervetuloa toiseen Google-haastatteluhaasteiden julkaisu -sarjaan, sarjaan, jossa esitän haastatteluongelmat, joita olen käyttänyt haastatteleessani Googlen ehdokkaita, kunnes heidät vuotanut ja kielletty käyttämästä haastatteluissa. Menetykseni on kuitenkin sinun hyötysi, koska kun he ovat poistuneet maailmasta, voin kirjoittaa ne ylös ja selittää ne sinulle.

Ennen sukellusta minulla on jännittäviä uutisia: Olen jättänyt Googlen! Olen innoissani ilmoittaessani, että olen liittynyt Redditiin suunnittelujohtajana NYC: ssä! Aion kuitenkin julkaista tämän sarjan, joten pysy kuulolla.

Vastuuvapauslauseke: Vaikka ehdokkaiden haastattelu on yksi ammatillisista velvollisuuksistani, tämä blogi edustaa henkilökohtaisia ​​huomautuksiani, henkilökohtaisia ​​anekdootiani ja mielipiteitäni. Älä erehdy tätä mistään virallisesta lausunnosta, jonka Google, Aakkoset, Reddit tai muut henkilöt tai organisaatiot ovat lähettäneet tai ovat puolesta.

Kysymys

Yksi kritiikoista, joita saan kahdessa viimeisessä viestissä kuvaamastani ritarin valitsijakysymyksestä, on, että se ei ole realistinen ongelma. Niin hyödyllistä kuin se voi olla, että koettelee ehdokkaan ajattelua, myönnän, että se on viime kädessä vähän epärealistinen tehtävä. (Minulla on joitain ajatuksia siitä, onko haastattelukysymysten ja todellisuuden välillä tärkeää olla yhteys, mutta aion tallentaa ne tulevaan viestiin. Voit olla varma, kommentoi osioita kaikkialla, kuulen sinut ja minulla on asioita sanottavaa. Vain ei nyt.)

Sillä välin, kun ritarin valitsin kiellettiin muutama vuosi sitten, otin palautteen sydämessäni ja yritin korvata sen kysymyksellä, joka on hiukan osuvampi Googlelle. Ja mikä voi olla Googlelle merkityksellisempää kuin hakukyselyjen mekaniikka? Löysin tämän kysymyksen ja käytin sitä pitkään, ennen kuin sitä myös vuoti ja kiellettiin. Kuten aikaisemmin, esitän kysymyksen, sukellaan sen selitykseen ja keskustelen sitten siitä, kuinka olen käyttänyt tätä kysymystä haastatteluissa ja miksi pidän siitä:

Kuvittele, että käytät suosittua hakukonetta ja lokissasi tarkkaillaan kahta kyselyä, sanotaan esimerkiksi ”Obaman hyväksymisarvostelut” ja “Obaman suositustaso”. (Jos muistan oikein, nämä olivat todellisia esimerkkejä haastatteluongelmatietokannasta, joka päivämäärä kysymys vähän ...) Nämä kaksi kyselyä ovat eri merkkijonoja, mutta luulen, että voimme kaikki olla yhtä mieltä siitä, että he etsivät periaatteessa samaa asiaa, ja niitä pitäisi pitää vastaavina kyselyjä laskettaessa, tuloksia näytettäessä jne. Kuinka voimme havaita sen kaksi kyselyä ovat synonyymejä?

Alustakaamme tämä. Oletetaan, että sinulle annetaan kaksi tuloa. Ensinnäkin luettelo merkkijonopareista, jotka edustavat synonyymejä, joissa parin kaksi merkkijonoa ovat synonyymejä toistensa kanssa. Toiseksi luettelo merkkijonopareista, jotka edustavat kyselyjä.

Tämän konkretisoimiseksi tässä on esimerkki tulosta havainnollistaaksesi:

Tehtäväsi on tulostaa luettelo boolean arvoista siten, että jokainen tulosteen merkintä osoittaa, vastaavatko vastaavat kyselyparit synonyymejä.

Kysymyksiä, kysymyksiä

Tämä on yksinkertainen ongelma. Kuitenkin mitä lähemmäksi katsot, sitä monimutkaisemmaksi se tulee. Heti lepakon jälkeen käy selväksi, että tämä ongelma on melko aliarvioitu. Voiko sanoilla olla useita synonyymejä? Onko sanajärjestyksellä merkitystä? Ovatko synonyymisuhteet transitiivisiä, mikä tarkoittaa, että jos A on synonyymi B: lle ja B on synonyymi C: lle, tarkoittaako tämä, että A on synonyymi C: lle? Voivatko synonyymit kattaa useita sanoja, kuten kuinka "USA" on synonyymi "Yhdysvaltojen" tai "Yhdysvaltojen" kanssa?

Tämä epäselvyys antaa heille hyvät ehdokkaat heti mahdollisuuden erottua toisistaan. Ensimmäinen asia, jonka hyvä ehdokas tekee, on tuhota tällaiset epäselvyydet ja yrittää ratkaista ne. Tapa, jolla he tekevät, vaihtelee ehdokasta toiseen: jotkut astuvat taulun päälle yrittääkseen ratkaista tietyt tapaukset manuaalisesti, kun taas toiset katsovat kysymystä ja näkevät aukot heti. Joka tapauksessa näiden aiheiden varhainen tarkkailu on ensiarvoisen tärkeää.

Pidän erittäin tärkeänä tämän kysymyksen ”ongelman ymmärtämisen” vaihetta. Ohjelmistosuunnittelu on sitä, mitä haluan kutsua fraktaaliksi tieteenalaksi, tarkoittaen, että se jakaa laadun fraktaalien kanssa, jos lähentäminen paljastaa ylimääräistä monimutkaisuutta. Juuri kun luulet ymmärtävän ongelman, katsot tarkemmin ja huomaat, että on olemassa hienovaraisuus, johon olet huomannut, tai on olemassa toteutuksen yksityiskohtia, joita voit parantaa, tai on olemassa uusi tapa kehittää ongelma, joka paljastaa ylimääräisen käsityksen.

Mandelbrot-sarja

Suunnittelijan kaliiperi määräytyy pitkälti sen perusteella, kuinka syvästi he ymmärtävät ongelman. Epäselvän ongelmalausunnon muuttaminen yksityiskohtaisiksi vaatimuksiksi on askel nolla tässä prosessissa, ja ongelman tarkoituksenmukainen aliarviointi antaa minulle mahdollisuuden arvioida, kuinka hyvin ehdokas lähestyy uusia tilanteita.

Sivustossa on myös sellaisia ​​triviaaleja kysymyksiä, kuten ”onko isoilla kirjaimilla merkitystä?”, Jotka, ehdokkaan tietämättä, eivät vaikuta ydinalgoritmisiin ongelmiin. Näihin kysymyksiin annan aina minkä tahansa ehdokkaalle helpoimman vastauksen (tässä tapauksessa "oletetaan, että kaikki on jo esikäsitelty pieniksi").

Osa 1: (Ei niin) yksinkertainen tapaus

Ehdokkaiden saapuessa näihin kysymyksiin he väistämättä lopulta kysyvät minulta vastausta, ja aloitan aina yksinkertaisimmalla mahdollisella tapauksella: sanoilla voi olla useita synonyymejä, järjestysasiat, synonyymit eivät ole transitiivisiä, ja synonyymit voivat kuvata vain yhdestä sanasta toiselle. Tämä tekee melko rajoitetusta ominaisuudesta hakukoneessa, mutta siinä on enemmän kuin tarpeeksi hienostuneisuutta kiinnostuneen haastattelua koskevan kysymyksen tekemiseen.

Korkean tason yleiskatsaus ratkaisuun on seuraava: jaa kysely sanoiksi (välilyöntiä jakaa hienosti) ja vertaa vastaavien sanojen pareja nähdäksesi, ovatko ne joko identtisiä vai synonyymejä toistensa kanssa. Visuaalisesti se näyttää seuraavalta:

Toteutuksessa se näyttää hiukan tältä:

Helppoa, eikö? Algoritmisesti tämä on melko yksinkertaista. Ei dynaamista ohjelmointia, ei rekursiota, ei hankalia tietorakenteita jne. Vain yksinkertainen, suoraviivainen manipulointi vakiokirjastoon ja lineaarinen aikaalgoritmi, eikö niin?

Luulisi, mutta täällä on enemmän hienovaraisuutta kuin mitä ensi silmäyksellä näit. Tämän yksinkertaisen algoritmin vaikein komponentti on synonyymivertailu. Vaikka synonyymien vertailukomponentti on helppo ymmärtää ja kuvata, se voi mennä pieleen. Tarkastelen joitain yleisimpiä, joita olen nähnyt täällä.

Selvyyden vuoksi mikään näistä virheistä ei ole mielestäni syrjäyttävä; Jos ehdokas tuottaa toteutuksen virheellisellä tavalla, haluaisin vain huomauttaa sen, he mukauttavat ratkaisuaan ja me jatkamme. Haastattelu on kuitenkin ennen kaikkea taistelu aikaa vastaan. Virheiden tekeminen, havaitseminen ja korjaaminen on odotettavissa, mutta se vie paljon aikaa, joka voitaisiin käyttää muualle, esimerkiksi optimaalisen ratkaisun tuottamiseen. Hyvin harvat ehdokkaat eivät tee virheitä, mutta vähemmän ehdokkaat edistyvät enemmän vain siksi, että viettävät vähemmän aikaa itsensä puhdistamiseen.

Tästä syystä pidän tästä ongelmasta: toisin kuin ritarin valintakiekko, joka vaatii algoritmisen näkemyksen välähdyksen ja (toivottavasti) yksinkertaisen toteutuksen, tämä kysymys vaatii useita pieniä, askeleita oikeaan suuntaan. Jokainen askel edustaa pientä estettä, jonka yli ehdokas voi joko hypätä sulavasti tai kompastua ja joutua palautumaan. Hyvät ehdokkaat välttävät nämä pienet sudenkuopat käyttämällä kokemustaan ​​ja intuitioonsa, ja heille palkitaan tarkempi ja oikeampi ratkaisu, kun taas heikommat ehdokkaat kuluttavat aikaa ja energiaa virheisiin, ja heillä on yleensä vikakoodi.

Vaikka jokaisessa haastattelussa nähtiin erilainen sekoitus hyppyjä ja lihaksia, tässä on pieni näyte yleisimmistä virheistä, joita näin.

Tahattomat Runtime Killers

Ensinnäkin jotkut ehdokkaat toteuttivat synonyymitunnistuksen käyttämällä yksinkertaista synonyymit-luettelon läpi:

Se näyttää olevan kohtuullinen. Kun tarkastellaan tarkemmin, tämä on erittäin, erittäin huono idea. Niille teistä, jotka eivät tiedä Pythonia, avainsanana on syntaktinen sokeri a-menetelmälle, ja se toimii kaikissa vakiona olevissa Python-säilöissä. Tämä on tässä ongelma, koska synonym_words on luettelo, joka toteuttaa avainsanassa lineaarista hakua käyttämällä. Python-käyttäjät olivat erityisen alttiita tälle virheelle, koska kieli piilottaa tyypit, mutta C ++- ja Java-käyttäjät tekivät toisinaan samanlaisia ​​virheitä.

Koko urani aikana olen kirjoittanut vain koodin, joka käyttää lineaarista hakua kourallinen kertaa, ja joka kerta se sisälsi luetteloita, jotka olivat enintään kaksi tusinaa elementtiä pitkä, ja silloinkin sisällytin siihen pitkän kommentin, jotta kerroin lukijoille, miksi valitsi tällaisen näennäisesti suboptimaalisen lähestymistavan. Epäilen syytä, jonka jotkut ehdokkaat käyttivät siihen, koska he eivät yksinkertaisesti tienneet Python-standardikirjastoa riittävän hyvin tietääkseen, kuinka avainsana toteutetaan luetteloiden yli. Se on helppo virhe tehdä, eikä se ole maailman loppua, mutta valitsemasi kielen tuntemattomuuden osoittaminen ei ole hyvä näkö.

Käytännön neuvojen kannalta tämä on todella helppo välttää virhe. Ensinnäkin, älä koskaan unohda objektityyppejäsi, vaikka käytät kirjoittamatonta kieltä, kuten python! Toiseksi, muista, että kun käytät luettelossa avainsanaa, se on lineaarinen haku. Ellei tämän luettelon taata olevan aina hyvin pieni, siitä tulee suorituskykytappari.

Ehdokkaiden muistuttaminen siitä, että syöttörakenne on luettelo, yleensä riittää herättämään heidät. Se mitä tapahtuu sen jälkeen kun olen antanut vihjeen, on erittäin informatiivinen. Paremmat ehdokkaat ajattelevat heti prosessoida synonyymit jonkin verran, mikä on hyvä alku. Tämä lähestymistapa ei kuitenkaan ole ilman aukkoja ...

Käytä oikeaa tietorakennetta

Yllä olevan koodin perusteella on heti selvää, että tämän algoritmin toteuttamiseksi lineaarisessa ajassa tarvitaan vakioajan synonyymihaku. Ja b jokaisen vakioaikaisen haun takana on aina hashmap tai hashset.

Mikä näistä kahdesta ehdokkaasta valitsee, on minulle vähemmän mielenkiintoinen kuin se, mitä he esittävät. (Muuten, älä koskaan käytä totta tai vääriä menevää dikttiä / hasmappia. Sitä kutsutaan sarjaksi.) Useimmat ehdokkaat asettuvat jonkinlaiseen dikttiin / hashmapiin. Yleisin virhe, jonka näen, on alitajuinen oletus siitä, että jokaisella sanalla voi olla enintään yksi synonyymi:

En todellakaan rankaise ehdokkaita tämän virheen tekemisestä. Esimerkkisyöttö on tarkoituksellisesti suunniteltu niin, ettei muisteta, että sanoilla voi olla useita synonyymejä, ja joillain ehdokkaista ei yksinkertaisesti ole ollut tällaista reunatapausta heille. Nopein korjata itsensä, kun olen huomauttanut tämän virheen. Hyvät ehdokkaat pelastavat ongelmansa huomaamalla sen aikaisin, mutta se ei yleensä ole suuri ajan menetys.

Hieman vakavampi ongelma ei ole ymmärtää, että synonyymisuhde menee molemmin puolin. Huomaat, että yllä oleva koodi tekee tämän. Tämän korjaaminen voi kuitenkin olla altis virheille. Harkitse seuraavaa lähestymistapaa tämän ominaisuuden toteuttamiseen:

Miksi suorittaa kaksi lisäystä ja käyttää kaksinkertaista muistia, kun et voi käyttää ylimääräistä muistia ja suorittaa kaksi tarkistusta?

Ota mukaan: kysy aina itseltäsi, voitko tehdä vähemmän töitä! Jälkikäteen etsinnän jatkaminen on ilmeinen tapa säästää aikaa, jos etsit sitä, mutta optimaalisen toteutuksen käyttäminen ehdottaa, että ehdokas ei ajatellut etsiä tapoja optimoida. Annan jälleen mielelläni vinkin, mutta olisi parempi, jos minun ei tarvitsisi.

Lajittelu?

Jotkut älykkäämpiä ehdokkaat ajattelevat lajitellaan synonyymit-luettelon ja määrittävät sitten binaarisen haun avulla, ovatko kaksi sanaa synonyymejä. Tällä lähestymistavalla on itse asiassa suurin etu, koska se ei vaadi ylimääräistä tilaa syötteiden synonyymiluettelon lisäksi (olettaen, että syöttöluettelon muuttaminen on hyväksyttävää).

Valitettavasti ajan monimutkaisuus ei ole suuri: synonyymiluettelon järjestämiseen kuluu Nlog (N) aikaa ja sitten kirjataan (N) aikaa kunkin synonyymiparin etsimiseen, kun taas edellä kuvattu esikäsittelyratkaisu tapahtuu lineaarisena ja sitten vakiona. Lisäksi se, että ehdokkaalle asetetaan sekä lajittelu että binaarinen haku taululle, on ei-ei kirjassani, koska 1. lajittelualgoritmit ovat hyvin tunnettuja, joten tiedän, että ehdokas saattaa regurgitoitua uudelleen, ja 2. nämä algoritmit ovat pahoin hankala saada oikein, ja usein jopa parhaat ehdokkaat tekevät virheitä, jotka eivät kerro minulle mitään heidän kykystään ohjelmoida.

Aina kun ehdokas tarjosi tämän ratkaisun, kysyisin suorituksen monimutkaisuutta ja kysyisin, pystyvätkö he parempaan. Sivun kohdalla: jos haastattelija kysyy, voitko tehdä paremmin, vastaus on yleensä “kyllä”. Jos kysyn sinulta kyseisen kysymyksen, vastaus on aina “kyllä”.

Lopuksi ratkaisu

Toivottavasti tässä vaiheessa ehdokas on tuottanut jotain oikeaa ja optimaalista. Tässä on lineaarinen aika, lineaarinen tilan toteutus tälle johdantokappaleelle:

Muutama supernopea muistiinpano:

  • Huomaa dict.get (): n käyttö. Voit kirjoittaa "tarkista, onko avain diktissä ja saada se sitten" -toimenpiteen, mutta se on sotkuista. Tällä tavoin voit osoittaa tietosi standardikirjastosta.
  • En henkilökohtaisesti ole fani koodista, joka käyttää paljon jatkoa, ja jotkut tyylioppaat kieltävät tai estävät niiden käytön. Olin todella ottanut käyttöön virheen tämän koodin ensimmäisessä toteutuksessa jättämällä jatkamatta kyselyn pituuden tarkistuksen jälkeen. Se ei ole huono, tiedä vain, että se on alttiina virheille.

Osa 2: Kovenee!

Hyvien ehdokkaiden kanssa minusta tuntuu usein olevan vähintään kymmenen tai viisitoista minuuttia jäljellä. Onneksi voin kysyä paljon vastauskysymyksiä, mutta emme todennäköisesti saa paljon koodia kirjoitettuina tuona aikana. Päivän lopussa, vaikka mielestäni minun ei tarvitse. Haluan tietää kaksi asiaa ehdokkaasta: Voivatko suunnitella algoritmeja? ja: voivatko ne koodata? Ritarin kellotaulu vastaa ensin algoritmin suunnittelukysymykseen ja tutkii koodausta sen jälkeen, kun taas tähän kysymykseen saadaan vastauksia päinvastaisessa järjestyksessä.

Siihen mennessä, kun ehdokas on suorittanut kysymyksen ensimmäisen osan, he ovat jo ratkaisseet (yllättävän ei-triviaalisen) koodausongelman. Tässä vaiheessa voin luottaa siihen, että he kykenevät suunnittelemaan alkeellisia algoritmeja ja kääntämään heidän ideansa koodiksi, samoin kuin heidän tuntemuksensa suosikkikielestään ja standardikirjastosta. Kysymyksestä tulee sitten minulle paljon hauskempi, koska koodausvaatimuksia voidaan lieventää ja voimme sukeltaa algoritmisiin komponentteihin.

Palataan tätä varten ensimmäisen osan perusoletuksiin: sanajärjestyksellä on merkitystä, synonyymisuhteet eivät ole väliaikaisia, eikä synonyymeillä voi olla useita sanoja. Haastattelun edetessä käännän kaikki nämä rajoitukset, ja tässä uudessa jälkikoodausvaiheessa ehdokas ja minulla on puhtaasti algoritminen keskustelu. Tuotan koodinäytteitä havainnollistaakseni, mutta varsinaisessa haastattelussa puhun puhtaasti algoritmisella tavalla.

Ennen sukellusta selitän odotukseni sanomalla, että seuranta on pohjimmiltaan "ylimääräistä hyvitystä". Henkilökohtainen lähestymistapani tähän kysymykseen on antaa ehdokkaille, jotka ehdottomasti naulaa ensimmäiseen osaan "vuokraus", ja käyttää Seuraava jakso erottaa ”vuokraus” ehdokkaat “vahvan vuokrauksen” ehdokkaat. ”Vuokraus” -luokitus on vahva luokitus, joka sanoo ”Uskon, että tämä henkilö on tarpeeksi hyvä työskentelemään täällä”, kun taas ”Vahva vuokraus” sanoo “Uskon, että tämä henkilö on erinomainen ja hänen palkkaaminen merkitsisi yritykselle suurta voittoa. ”

Transitiivisyys: Naiivi lähestymistapa

Ensimmäinen rakkaus, josta haluan rentoutua, on transitiivisyyden ympärillä, mikä tarkoittaa, että jos sanat A ja B ovat synonyymejä ja jos sanat B ja C ovat synonyymejä, sanat A ja C ovat synonyymejä. Terävät ehdokkaat ymmärtävät nopeasti pystyvänsä mukauttamaan aikaisemman ratkaisunsa tämän ratkaisemiseksi, koska he määrittävät edelleen, edustavatko yksinkertaiset sanaparit synonyymit pareja, kun taas muut relaksaatiot tekevät kelvottomiksi aiemman algoritmin ydologian.

Tätä varten miten me teemme sen? Yksi yleinen lähestymistapa on ylläpitää täydellistä synonyymiä jokaiselle sanalle transitiivisten suhteiden perusteella. Joka kerta kun lisäämme sanan synonyymijoukkoon, lisäämme sen myös vastaaviin joukkoihin kaikille kyseisessä sarjassa oleville sanoille:

Tämä ratkaisu toimii, mutta se on kaukana optimaalisesta. Selvitäksesi miksi, harkitse tämän ratkaisun tilan monimutkaisuutta. Joka kerta kun lisäämme synonyymin, meidän ei tarvitse vain lisätä aloitussanan joukkoon, vaan myös joukkoihin, jotka kuuluvat kaikkiin sanoihin, joiden kanssa kyseinen sana on synonyymi. Jos se on yhden sanan mukainen, meidän on lisättävä yksi merkintä. Jos se merkitsee viittäkymmentä sanaa, meidän on lisättävä vielä viisikymmentä merkintää. Kuvitettu, se näyttää tältä:

Huomaa, että olemme siirtyneet 3 näppäimestä ja 6 merkinnästä 4 näppäimeen ja 12 merkintään. 50 synonyymin sana vaatisi 50 avainta ja melkein 2500 merkintää. Yhden sanan esittämiseen tarvittava tila kasvaa neliömäisesti sen synonyymijoukon koon kanssa, mikä on aika tuhlaa.

On olemassa muitakin ratkaisuja, mutta avaruuteen liittyvissä asioissa en aio sukeltaa niihin liian pitkälle. Mielenkiintoisimpaan sisältyy synonyymitietorakenteen käyttäminen suunnatun kuvaajan rakentamisessa ja sitten leveys-ensimmäisen haun avulla selvittää, onko kahden sanan välillä polku. Tämä on hieno ratkaisu, mutta haku muuttuu lineaariseksi sanan synonyymijoukon koosta. Koska suoritamme haun useita kertoja jokaiselle kyselylle, tämä lähestymistapa on hyvin epäoptimaali.

Transitiivisyys: Disjoint-sarjan käyttäminen

Osoittautuu, että voimme etsiä synonyymisuhteita (melkein) vakioaikana käyttämällä tietorakennetta, jota kutsutaan disjoint-joukkoksi. Tätä rakennetta kutsutaan joukkoksi, mutta se tarjoaa jonkin verran erilaisia ​​ominaisuuksia kuin mitä useimmat ihmiset ajattelevat kuuleessaan sanan “set”.

Tavallinen joukkorakenne (hajautus, puisarja) on säiliö, jonka avulla voit nopeasti selvittää, onko esine kyseisessä ryhmässä vai siitä. Hajotettu joukko ratkaisee hyvin erilaisen ongelman: Sen sijaan, että tarkasteltaisiin sitä, onko tietty esine sarjassa, sen avulla voit määrittää, kuuluvatko kaksi kohtaa samaan joukkoon. Lisäksi se tekee tämän sokeasti nopealla O (a (n)) -jaksolla, jossa a (n) on Ackerman-funktion käänteinen arvo. Ellet ole käynyt syventävää algoritmikurssia, sinulle voidaan antaa anteeksi, että hän ei tiedä tätä toimintoa, ja kaikille kohtuullisille syöttöille se on käytännössä yhtä suuri kuin vakioaika.

Korkealla tasolla algoritmi toimii seuraavasti. Sarjoja edustavat puut, joissa jokaisella esineellä on vanhempi. Koska jokaisella puulla on juuri (tarkoittaen omaa vanhempaa alkiota), voimme selvittää, kuuluvatko kaksi kohtaa samaan joukkoon seuraamalla vanhempiaan, kunnes löydämme kumpikin juurelementin. Jos kahdella elementillä on sama juuri, niiden on kuuluttava samaan joukkoon. Sarjojen yhdistäminen on myös helppoa: me vain löydämme juurelementit ja teemme yhdestä toisen juuren.

Toistaiseksi niin hyvä, mutta silmämääräisesti ei vielä ole sokeuttavaa esitystä. Tämän rakenteen nero on menettelyssä, jota kutsutaan tiivistykseksi. Oletetaan, että sinulla on seuraava puu:

Kuvittele haluavasi tietää, ovatko ”nopea” ja “kiireinen” synonyymejä. Kummastakin käydään läpi vanhempien suhteet ja huomaat, että molemmat jakavat “nopean” juurisolmuna, siksi niiden on oltava synonyymejä. Oletetaan nyt, että haluat tietää, ovatko ”nopea” ja ”nopea” synonyymejä. Aloittaisit jälleen jokaisesta solmusta ja kulkeisit eteenpäin, kunnes saavut ”nopeaan”, mutta tällä kertaa saatat huomata, että olet monistanut poikittaisen ”nopealle”. Voitko välttää tämän päällekkäisen työn?

Kyllä voit, käy ilmi. Tavallaan jokaisen tämän puun elementin on tarkoitus saavuttaa "nopea". Sen sijaan, että kuljettaisit puuta useita kertoja, miksi et yksinkertaisesti vaihda jokaisen elementin vanhempaa matkalla "nopeaan" ja pelastaa itsellemme työn? Tätä prosessia kutsutaan tiivistykseksi, ja hajotetussa ryhmässä se on rakennettu juurihakuoperaatioon. Esimerkiksi sen jälkeen kun olemme selvittäneet, ovatko ”nopea” ja “kiireinen” synonyymejä, yllä oleva puu näyttää tältä:

Jokaisen sanan ”nopea” ja ”nopea” välillä vanhemmat päivitettiin, ja sama tapahtui “hätäisestä” pikaiseksi.

Nyt kaikki myöhemmät käyttökerrat tapahtuvat vakiona, koska jokainen tämän puun solmu osoittaa "nopealle". Tämän rakenteen toimintojen asianmukaisen aikakompleksiisuuden analysointi on ei-triviaalia: se ei oikeastaan ​​ole vakio, koska se riippuu puiden syvyydestä, mutta se ei ole kovinkaan huonompi kuin vakio, koska asiat sulautuvat vakioaikaan nopeasti. Analysointia varten teemme laiskaosan ja kutsumme sitä vain vakioajaksi.

Kun tämä konsepti on käsillä, tässä on irrotettu joukko toteutusta, joka tarjoaa tarkalleen toiminnot, joita tarvitsemme tähän ongelmaan:

Tätä rakennetta käyttämällä voimme esikäsitellä synonyymit ja ratkaista tämä ongelma lineaarisessa ajassa.

Arviointi ja huomautukset

Tässä vaiheessa olemme saavuttaneet rajan siihen, mitä olen nähnyt tekemäni haastattelun 40–45 minuutissa. Annoin jokaiselle ehdokkaalle, joka suoritti johdanto-osan ja edistyi merkittävästi disjoint-sarjan ratkaisun kuvaamisessa (ei toteuttamisessa) ”Vahva vuokra” -luokituksen, ja jatkoin heidän antavan minulle kysymyksiä. En ole koskaan nähnyt ehdokkaan pääsemään näin pitkälle paljon aikaa varaa.

Tämä antaa meille vielä muutaman seurannan: version tästä kysymyksestä, jossa sanajärjestyksellä ei ole merkitystä, ja sellaisen, jossa synonyymit voivat kattaa useita sanoja. Ratkaisut jokaiselle näistä ovat haastavia ja ilahduttavia, mutta avaruuden vuoksi käsittelen niitä jatkoviestinä.

Tämä kysymys on hyödyllinen, koska se antaa ehdokkaille mahdollisuuden tehdä virheitä. Päivittäinen ohjelmistosuunnittelu koostuu loputtomasta analysointi-, toteuttamis- ja parannusjaksosta. Tämä ongelma tarjoaa ehdokkaille mahdollisuuden osoittaa hallitsevansa jokaisen näistä vaiheista. Harkitse taitoja, jotka tarvitset ansaitaksesi "Vahvan vuokrauksen" tässä kysymyksessä:

  • Analysoi ongelmalausunto ja tunnista, missä se on epäselvä ja alimääritelty, selventämällä tarvittaessa yksiselitteisen ongelmalausunnon kehittämistä. Jatka tämän tekemistä ratkaisun edetessä ja kohtaat uusia kysymyksiä. Maksimaalisen tehokkuuden saavuttamiseksi tee niin suuri osa tästä vaiheesta kuin mahdollista, koska virheistä toipuminen tulee kalliimmaksi työn edetessä.
  • Kehitä ongelma tavalla, joka helpottaa lähestymistapaa ja ratkaisemista. Tässä tapauksessa tärkein kohta on huomautus, että voit rivittää vastaavat sanat kyselyihin.
  • Toteuta ratkaisusi. Tähän kuuluu optimaalisen tietorakenteen ja algoritmien valitseminen sekä logiikan suunnittelu niin, että se on luettavissa ja helppo muokata tulevaisuudessa.
  • Ympyrä takaisin ja yritä havaita virheet ja virheet. Nämä voivat olla todellisia virheitä, kuten kuinka unohdin lisätä yllä olevan “jatka” -ilmoituksen, tai suoritusvirheitä, kuten väärän tietorakenteen käyttäminen.
  • Kun ongelman määritelmä muuttuu, toista tämä prosessi ja mukauta ratkaisuasi aina tarvittaessa ja romuta se muualle kuin ei. Se, miten molemmat tehdään, on kriittinen taito sekä haastattelussa että todellisessa maailmassa.
  • Pidä tietorakenteet ja algoritmitietosi hyppysissäsi. Hajoitettu joukko tietorakenne ei ole tarkalleen yleinen rakenne, mutta se ei oikeastaan ​​olekaan niin harvinainen ja hienostunut. Ainoa tapa varmistaa, että tiedät työvälineen, on oppimalla niin paljon kuin pystyt.

Mitään näistä taitoista ei voi oppia oppikirjoista (paitsi ehkä tietorakenteiden ja algoritmien osalta). Ainoa tapa hankkia nämä taidot on säännöllinen ja laaja käytäntö, joka vastaa hyvin sitä, mitä yritykset haluavat: ehdokkaat, jotka hallitsevat taitonsa ja ovat riittävän harjoitellut soveltaa niitä tehokkaasti. Näiden ihmisten havaitseminen on haastattelun piste, ja tämä kysymys palveli minua hyvin pitkään.

Odotan innolla

Kuten voit todennäköisesti päätellä kirjoittaessani tätä viestiä, myös tästä kysymyksestä tuli lopulta vuoto. Siitä lähtien olen käyttänyt useita kysymyksiä mielialastani (yhden kysymyksen esittäminen koko ajan tulee tylsää) ja siitä, mitä ehdokkaan aikaisemmat haastattelijat olivat kysyneet. Jotkut niistä ovat edelleen käytössä, joten pidän heidät salassa, mutta osa ei! Voit odottaa näkeväni myöhemmät tulevissa viesteissä.

Lyhyellä aikavälillä minulla on kuitenkin kaksi muuta virkaa, jotka tulevat hauen alas. Ensinnäkin, kuten yllä luvattiin, kirjoitan ja julkaiseen kaksi jäljelle jäävää seurantaa tähän kysymykseen. Ei siksi, että he olisivat koskaan tulleet haastatteluihin, vaan koska he ovat mielenkiintoisia itsessään. Jaan myös ajatuksiani ja henkilökohtaisia ​​mielipiteitäni tekniikkamaailman palkkausprosessista, mikä on erityisen mielenkiintoista minulle nyt, kun palkan insinöörejä omaan tiimiini Redditissä.

Kuten aina, jos haluat pysyä ajan tasalla tämän sarjan kanssa, seuraa minua Twitterissä tai Mediumissa. Jos pidit tästä viestistä, muista taputtaa tai jättää kommentti. Rakastan palautetta ja käytän sitä kertomaan, mikä toimii ja mikä ei.

Kiitos lukemisesta!

Päivitys: Nyt kun minulla on useita viestejä, tässä on luettelo kaikista muista tämän sarjan viesteistä:

  • esittely
  • Knight's Dialer
  • Knight's Dialer -seuranta
  • Suhteiden etsijä

P.S .: Voit tarkistaa koodin tämän sarjan GitHub-repo-ohjelmassa tai pelata koodilla live-tilassa hyvien ystävieni kautta repl.it: