Algoritmi

Posted by ela on mai 27, 2010
Filed Under Muncă | 23 Comments

1. Scrie o metoda care primeste un array de N elemente si un numar K, si intoarce al K-lea cel mai mic element (e.g. find_kth(3, { 5,4,3,1,2,1,2,7,6,9,4,5} ) trebuie sa intoarca “2″. (sirul sortat ar fi 1,1,2,2,3,4,4,[...], al 3-lea element din sirul sortat e “2″).Gaseste un algoritm de complexitate mai mica de O(n log n) (ex: mai rapid decat “sortare + indexare”).

2. Sa se calculeze numarul T(n) al cuvintelor de lungime n folosind alfabetul {A,B,C,D} care contin secventa ABBD.
Ex.:

Intrare Iesire
n=4 1
n=5 8

3. Se dă un sir de N <= 10000 numere naturale distincte. Se cere găsirea unui set oarecare de 4 numere din acest sir, fie ele a b c d astfel încât a + b + c = d.Ex: pentru sirul „21 5 7 13 9 6 3 2″ o solutie corectă este setul (a=6, b=13, c=2, d=21) – problema oferita de InfoArena

4. Pentru un numar natural nenul N se noteaza cu S(N) cifra obtinuta prin urmatorul procedeu: se calculeaza suma cifrelor lui N si se obtine un numar, apoi se calculeaza suma cifrelor acestui numar si se obtine alt numar, s.a.m.d pana cand rezultatul insumarii cifrelor este mai mic strict decat 10.(ex.: N=2481 suma cifrelor este 2+4+8+1=15, iar 1+5=6<10, deci S(2481)=6). Sa se implementeze un algoritm eficient (complexitate temporala si spatiala optime) care primeste ca intrare vectorul de cifre ale unui numar natural N si calculeaza S(N).
Ex.:

Intrare Iesire
v=[1,2,3,4]   1
v=[9,7,8]   6
Share

Comments

23 Responses to “Algoritmi”

  1. Sorin Cracana on mai 27th, 2010 17:22

    la pr 1 trebuie trimis doar codul functiei, sau si un program de test ?

  2. Aura on mai 27th, 2010 17:50

    Rezolvarile trebuie sa fie intr-un limbaj anume sau pseudocod?

  3. mihai on mai 27th, 2010 17:51

    La problema 3 cat de mari sunt numerele?

  4. master_blaster on mai 27th, 2010 18:26

    La problema 1 care e dimensiunea maxima pentru N?

  5. randunel on mai 27th, 2010 20:20

    Sorin, dureaza 5-10 minute sa faci o interfata de test. Fa-o :)

    Aura, din moment ce este internship pentru Adobe, iar echipa va face o aplicatie in Flex/Flash, cred ca e de preferat AS3.

    mihai, oricat de mari, nu cred ca exista limita (limita de Number)

    master_blaster, nu cred ca exista limita :P

  6. ionut on mai 27th, 2010 20:42

    o intrebare cam stupida totusi…partea de algoritmi trebuie implementata obligatoriu in AS sau C e de ajuns?:))

  7. Lucian on mai 27th, 2010 22:17

    putem folosi algoritmi aleatori?(in special la problema 3)

  8. ciprian on mai 27th, 2010 22:25

    la problema 4 banuiesc ca stim lungimea vectorului…

  9. Lucian on mai 27th, 2010 23:04

    la problema 3 se considera doar cazul in care toate numerele sunt diferite,sau pot fi si aceleasi? (Ex: 3 + 3 + 7 = 13)

  10. randunel on mai 28th, 2010 00:24

    Lucian, citeste atent: “3. Se dă un sir de N <= 10000 numere naturale distincte." Reciteste ultimul cuvant :D

    Ciprian, din moment ce ti se scrie vectorul, poti afla…. vector.length :)

  11. Ciprian on mai 28th, 2010 00:26

    …Cum le uploadam? :)

  12. ciprian on mai 28th, 2010 00:31

    S-a pus o intrebare mai sus deloc stupida, putem rezolva problemele si in alte limbaje(de exemplu C) sau trebuie obligatoriu in actionscript ?
    Inteleg ca este de preferat AS, dar … ni se testeaza capacitatea de a compune/scrie un algoritm sau cunostintele de actionscript ?

  13. randunel on mai 28th, 2010 00:33

    Daca ne luam dupa ce a fost anul trecut, rezolvati-le in orice limbaj preferati.

    Personal, recomand AS3 ca pe asta e internshipul :D

  14. Adrian on mai 28th, 2010 07:29

    Exista proiecte de internship care *nu* au nici cea mai mica treaba cu AS3. Stiu ca precizarea mea e un pic tardiva, asta e.

    Chiar daca internshipurile ar implica toate ActionScript, tot nu ar conta.

    Bafta!

  15. Ciprian on mai 28th, 2010 09:20

    deci…cum uploadam?

  16. twist on mai 28th, 2010 09:38

    @Ciprian: Citez “asteptam raspunsurile voastre pana maine, 28 mai 2010, ora 13.30, pe adresele educatie@adobe.com si hr-romania@adobe.com” :P

  17. ela on mai 28th, 2010 09:43

    @Sorin: codul este necesar, aplicatia de test e un nice to have :)

  18. Bogdan on mai 28th, 2010 09:44

    Salut,

    Exercitiile se pot rezolva in orice limbaj, si cu orice biblioteci credeti.

    Ne este util daca descrieti si algoritmul folosit, in cuvinte/pseudocod sau commentarii la inceputul fisierului, eventual un readme.

  19. Bogdan on mai 28th, 2010 09:52

    @Mihai – numere intregi, incap pe 32 biti.

  20. BogdanD on mai 28th, 2010 09:54

    Desi sunt convins ca e destul de tarziu, uitati cateva detalii:
    - orice limbaj de programare e ok; conteaza algoritmul in primul rand.
    - cand nu se specifica o limita pentru datele de intrare, nu degeaba nu se specifica.
    - legat de “algoritmi aleatori” : voi puteti folosi ce algoritmi vreti voi, dar in principiu “there’s a good way and there’s a bad way”.

  21. master_blaster on mai 28th, 2010 12:48

    Cred ca ar fi fost mai bine pentru toata lumea daca ati fi organizat in weekend concursul asta care a fost destul de interesant.

  22. Iuri Tovcaci on mai 28th, 2010 13:01

    +1 master_blaster, in weekend ar fi fost mai interesant :)

  23. numa on octombrie 10th, 2010 16:15

    SUNTETI VARZA CAUTAM ALTCV

Leave a Reply