Interesanta intrebare cind insuccesul devine succes? si oare e posibil asa ceva? La moment parerea mea este "DA!", insuccesul poate deveni succes! Parerea mea este bazata pe recentele evenimente din domeniul angajarilor. Citeva minute in urma am avut un interview telefonic cu companai Amazon. Pot zice ferm ca nu am trecut la un urmator interview, adica am avut insucces, dar sunt sigur ca acest insucces ma va aduce la success pe viitor! Posibil nu voi fi angajatul companien Amazon, si probabil nu voi mai avea vreun interview cu aceasta companie, dar experienta pe care am primit-o astazi ma va ajut sa ajung la success pe viitor! CUM!? La interview au fost citeva intrebari din domeniul algoritmilor si estimarea complixitatii, un domeniu in care schiopatez destul de serios :( Acest insuccess ma motiveaza si mai mult sa ma apuc cit mai serios de algoritmi, sa-i studiez pe cei care nu-i cunosc si sa-mi readuc aminte acei algoritmi care nu i-am utilizat de ceva vreme. Dar pina a atinge succesul mai sunt doua piedeci: timpul si motivarea. Daca aceste doua piedeci vor avea un impact minim atunci successul l-a sigur va veni.
Acum sa povestesc ce a fost la interview.
Prima intrebare!
Este dat un sir de numere de lungimea N. In acest sir cifrele se repeta de doua ori, si doar o singura valoare nu se repeta. Care e algorimtul de depistare a acestei cifre?
Prima solutie:
Avem sirul A de lungimea N si sirul B de lungimea N. Acum traversam sirul A de la 0 la N. Daca valoare I analizata nu este prezenta in sirul B atunci o inseram, daca este prezenta atunci valoare o stergem din sirul B. Astfel cind se finizeaza traversarea sirului A in sirul B obtinem acele valori care se repeta doar o singura data.
Rezultat: Amazon nu a ramas satisfacut de solutie, cer alta!
Solutia a doua:
Sortam in ordine crescatoare sirul A, dupa il traversam de la 0 la N/2. La fiecare iteratie verificam daca I = I+1, si daca e atunci valoarea de pe pozitia I se repeta. Pasul de iterare este 2.
Rezultat: Amazon nu a ramas satisfacut de solutie, deoarece exista sortare si complixitatea algoritmului creste, defapt complixitatea este sporita si in prima solutie. Amazon cere o solutie de complixitate N.
Solutia trei (Solutia a fost ceva ghidata de persoana care mi-a facut inteview)
Se creaza un HashMap. Se traverseaza sirul A de la 0 la N. Daca valoarea I nu se gaseste in HashMap atunci se insereaza in acesta. Verificarea existentei valorii in HashMap se face dupa hash si este de o complexitate 1. Daca valoarea este gasita dupa hash, atunci ea se sterge din HashMap. Dupa traversarea sirului A in HashMap ramin doar valorile care nu se repeta.
Rezultat: Amazon este satisfacut!
Intrebarea 2 (Arbori binari)
A. Algoritmul de traversare in adincime.
Aici parca nu am avut probleme. Avem o metoda recursiva care si traverseaza tot arborele.
B. Traversarea arborelui in latime.
La inceput putin m-am complicat cu solutia, si pina acum nu sunt sigur daca e cea mai optimala (facut asa ceva tare demult si mi-a iesit din cap algoritmul), dar a fost acceptata! La intrebarea care e complixitatea algoritmului nu am putut raspunde :(, am aflat dupa, e tot N.
P.S. Interview-ul a fost condus de un indus. Si m-am convins inca odata, trebuie perfectionat vorbirea in engleza :( (o alta cale spre success :) ).
imi place ca esti ambitios si crezi in tine asta conteaza mai mult decat orice, mie imi displac oamenii care nu exploateaza darurile pe care le-au capatat si apoi mai si ascund asta dupa o masca de indiferenta dar tu pari sa fii realist si stii ca ai puncte slabe, e de apreciat asta pentru ca barbatii sunt de regula orgoliosi sau ma rog cei pe care i-am intalnit eu si mi-am format o asa parere.
ReplyDeleteSuccess in continuare, cred ca te-ai potrivi la Amazon pentru ca acolo cultura companiei este de a recruta numai oameni valorosi, mi-a explicat asta un tip care lucreaza la ei la HR si crede-ma ca stie despre ce vorbeste!