09 lipca 2008

NetBeans IDE 6.5M1 dostępny i algorytmiczna oferta pracy z Mój Startup

Niektórzy mają wakacje, jeszcze niektórym zechciało się pisać wpisy na blogu, a jeszcze niektórzy robią coś pożytecznego i wytrwale programują. W zespole NetBeans praca zdaje się, że wre na całego, czego dowodem jest kolejna wersja NetBeans IDE. Jeszcze nie ostygła wersja 6.1, a już mamy NetBeans IDE 6.5 Milestone 1 (NetBeans IDE 6.5M1). Wspominałem o programie NetBeans Community Acceptance Test (NetCAT) dotyczącym wersji 6.5 w Umiędzynarodowienie w JBoss Seam, NetCAT 6.5 oraz nowa grupa oferty-pracy-java, w którym można wyrazić swoją opinię o tym wydaniu i...jeszcze zgarnąć nagrodę (poza sławą i chwałą). Nie pozostaje nic innego, jak tylko przyłączyć się do zespołu NetCAT 6.5 i wyrazić, co człowiekowi leży na sercu, w kontekście tego wydania (inne sprawy sercowe nie są obsługiwane ;-)) Pewnie nie dla wszystkich jest to The only IDE you need! (za reklamą NetBeans IDE 6.5). W ogłoszeniu napisano:

This stabilized development build contains the following new & noteworthy features:
  • PHP
    • Enhanced Code Completion
    • Database-related code snippets
    • Multiple project configurations
    • Find Usages
  • Ajax
    • JavaScript Debugger
    • JavaScript Library Manager
    • Bundled JavaScript Libraries
  • Groovy
    • Editor
    • Java SE Project Integration
    • Grails support
  • Java
    • Javadoc Anlyzer
    • Call Hierarchy
    • CamelCase code completion
  • Debugger
    • New Multithreaded Debugging Support
    • Debugging Window
    • Current Thread Chooser
  • Additional enhancements have been made to
    • Web Frameworks (Spring, Hibernate, JSF, JSF CRUD Generator, JPA)
    • Ruby
    • Database
    • Mobility
    • GUI Builder
    • Web Services
    • Improvements to XML and Schema Tools
Note: The UML feature is not available in Milestone 1, but is planned for Beta. The development team is migrating UML to the NetBeans Visual Library, to make UML completely open source. Please see UML Current Projects for additional information.

Get more details about these features and additional New and Noteworthy Features http://wiki.netbeans.org/NewAndNoteWorthy available in the release. The final NetBeans IDE 6.5 release is planned for Fall 2008. We welcome and encourage feedback about your experience using the NetBeans IDE.

Bardzo imponująca lista funkcjonalności, nieprawdaż?

Jestem stałym czytelnikiem bloga Mój Startup, w którym pojawiła się niezwykle ciekawie przedstawiona oferta pracy dla programisty java zawierająca zadanko na znajomość algorytmiki. Ciekawym Waszych rozwiązań.

Napisz funkcję (w dowolnym języku programowania), która mają tablicę o długości N zawierającą liczby z zakresu 1 do N stwierdzi, czy występują w niej duplikaty (czy da się to rozwiązać w czasie liniowym? przy stałej pamięci? bez niszczenia zawartości tablicy?)

Czas liniowy jak najbardziej (współczynniki kosztów poszczególnych algorytmów będą różne), stała pamięć jak najbardziej zakładając, że N jest dowolne acz ustalone przed uruchomieniem (tutaj może pojawić się klucz do zmniejszenia kosztu) i ostatecznie nie niszczymy zawartości tablicy, gdyż tworzymy jej kopię gwarantując, że jej rozmiar nie będzie zależny od rozmiaru danych wejściowych (gwarancja algorytmu w miejscu). Czas napisania takiego algorytmu sądzę, że udałoby się zamknąć w 15 minutach. Są chętni do podjęcia pracy? Nawet, jeśli niekoniecznie samej pracy, to może samego zadania? Bardzo spodobała mi się tak przedstawiona oferta pracy. Gratuluję pomysłu. Sądzę, że może być ich więcej na dopiero co założonej grupie oferty-pracy-java, gdzie tego typu oferty powinny być normą. Czyżby nowa jakość na polskim rynku ofert pracy?!

51 komentarzy:

  1. To chyba nie jest trudne zadanie :-)
    Można załatwić to jedną linijka (w javie):

    boolean czySaDuplikaty = new HashSet(Arrays.asList(tablica)).size() == tab.length;

    pozdrawiam
    Łukasz Sierant

    OdpowiedzUsuń
  2. Ha! Przejęzyczenie ;) Warunek musi być oczywiście odwrotny :)

    OdpowiedzUsuń
  3. Oczywiście możliwych implementacji jest wiele. Przy formułowaniu tych "zaostrzonych" kryteriów chodziło Markowi o uzyskanie algorytmu "optymalnego", czyli takiego, który będzie klasy O(n), a równocześnie wykorzysta "stałą, niezależną od N, ilość pamięci na struktury pomocnicze". Zatem tworzenie kopii tablicy nie wchodzi w grę. :)

    Ze swojej strony dorzucam jeszcze wymaganie co do optymistycznej złożoności obliczeniowej algorytmu na poziomie O(2). :)

    OdpowiedzUsuń
  4. Pogłówkowałem trochę i udało mi się znaleźć algorytm, który spełnia wszystkie z warunków, czyli:
    * działa w czasie O(n)
    * korzysta ze stałej (niezależnej od N) ilości pamięci
    * nie niszczy tablicy wejściowej

    Nie wklejam tu rozwiązanie, aby nie psuć innym zabawy :)

    Jacek, podsyłam do Ciebie ten kod (na email). I szacun dla Ciebie, Jacek ;) Mi wymyślenie tego algorytmu i jego implementacja zajęła dłużej niż 15 minut ;)

    Pozdrawiam,
    Adam Woźniak

    OdpowiedzUsuń
  5. Jeśli ktoś ma ochotę na kolejną zagadkę (ale już BEZ nagród!) to zapraszam na swój blog i opublikowaną zagadkę:
    http://adamwozniak.blogspot.com/2008/07/zagadka-algorytmiczna.html

    :)

    OdpowiedzUsuń
  6. Ludzie, no przeciez to jest banalne zadanie... a zlozonosc to O(1), nie O(2), bez zadnych dodatkowych tablic...

    OdpowiedzUsuń
  7. No to oświeć mnie (nas), Bartek.
    Mój algorytm działa w czasie O(N), więc ten Twój jest lepszy. Chętnie poznam ;)

    OdpowiedzUsuń
  8. hmm... troche zbyt pochopnie to napisalem, zwracam honor. Faktycznie zlozonosc to O(n) liniowo zalezna od wielkosci tablicy. Oczywiscie dalej problem jest banalny ;)

    OdpowiedzUsuń
  9. Bartek:
    A jak ze złożonością pamięciową?
    I czy tablica pozostaje niezmieniona? ;)

    OdpowiedzUsuń
  10. hm, a czy zakladacie, ze tablica wejsciowa jest read-only ?

    OdpowiedzUsuń
  11. Z resztą, gdyby była read-only to byłoby to napisane w treści zagadki.

    OdpowiedzUsuń
  12. sadze, ze optymalne rozwiazanie zaklada, ze jest rean-only... do tego potrzeba pamieci pamieci na powiedzmy 2 elementy o typie elementow tablicy

    OdpowiedzUsuń
  13. No to ten algorytm, które ja znalazłem (i wyżej już opisałem) nie zakłada, że wejściowa tablica jest read-only. Ciekawe jakie rozwiązanie znalazłeś. Podziel się "jakoś" (jednocześnie nie psując zabawy innym:).

    OdpowiedzUsuń
  14. to moge napisac na pw najwyzej, jezeli mam nie psuc zabawy ;) Wystarczajaca podpowiedzia jest to, ze w tablicy o rozmiarze N mamy liczby od 1 do N i co z tego wynika dla matematyka...

    OdpowiedzUsuń
  15. Bartek: OK, to podeślij kod / albo pomysł na algorytm na adres znajdujący się na gmailDOTcom:
    yadaslawy (usuń literki 'y')

    Ja Ci zwrotnie wyślę mój kod (jak w ogóle chcesz).

    OdpowiedzUsuń
  16. poszlo...
    a Twojego rozwiazania jestem ciekawy :)

    OdpowiedzUsuń
  17. O, dostałem od Ciebie propozycje rozwiązania :)
    Jak już zdążyłem na priv Tobie odpisać - z tą propozycją się nie zgadzam, ha ha ;)
    Ok - już wysyłam Tobie mój kod.
    Pozdrowienia,
    Adam Woźniak

    OdpowiedzUsuń
  18. Pośród wielu rozwiązań tego algorytmu mam też jedną opierającą się na arytmetyce, i nie chodzi tu o sumę elementów ciągu arytmetycznego. :)

    Czy ktoś jest zainteresowany?

    OdpowiedzUsuń
  19. morisil:
    Ja jestem zainteresowany:
    Mój adres znajdujący się na gmailDOTcom:
    yadaslawy (usuń literki 'y')

    OdpowiedzUsuń
  20. morisil:
    ok, ja tez jestem ciekawy - moj email jest w profilu
    chociaz obliczanie jakiejs tam wartosci z calego ciagu i porownanie z oczekiwana raczej nie ma szans byc 'bullet proof'.

    Rozwiazanie z uzyciem dodatkowej struktury (tablicy pomocniczej np. ) jest proste, ciekawy jestem tego 'arytmetycznego'

    OdpowiedzUsuń
  21. Takie jedno pytanie mi sie nasuwa - o jakim zakresie mowimy w tym problemie? A konkretnie z jakiego zbioru pochodza liczby znajdujace sie w tablicy?

    OdpowiedzUsuń
  22. majson: wszystko napisane jest w treści zadania.
    Ale jeszcze raz: jeśli tablica wejściowa jest długości N, to w każdej z komórek może być dowolna liczba L, gdzie:
    1 <= L <= N

    OdpowiedzUsuń
  23. Byc moze, ale nie odpowiedziales na moje pytanie :) Nie jest jasno okreslone do jakiego zbioru naleza te liczby.

    OdpowiedzUsuń
  24. A tak gwoli scislosci - piszac zbior mam na mysli np. zbior liczb naturalnych, calkowitych, rzeczywistych etc.

    OdpowiedzUsuń
  25. Faktycznie, w treści zagadki nie jest sprecyzowane jakiego typu są to liczby ;)
    Możesz napisać do tej firmy, że znalazłeś bug-a w dokumentacji do zagadki ;)
    Adam
    PS.
    Ja założyłem, że są to liczby typu całkowitego.

    OdpowiedzUsuń
  26. ... i w sumie - skoro typ danych w zagadce nie jest wyspecyfikowany - możemy podeprzeć się zasadą:
    Real programmers use integers.

    ;)

    OdpowiedzUsuń
  27. moim zdaniem skoro nie ma tego jasno w tresci zadania, nie powinnismy wprowadzac swoich warunkow - czyli rozwiazanie nie powinno opierac sie na zalozeniu, ze wartosci za np. ze zbioru liczb rzeczywistych.

    OdpowiedzUsuń
  28. @Adam
    No wlasnie stad moje pytanie. Dla typu calkowitego liniowka jest stosunkowo latwa do wymyslenia w rozsadnym czasie (tj. takim np. ktory podal Jacek), natomiast nad liniowym rozwiazaniem dla rzeczywistych glowilem sie dluzsza chwile i dlatego postanowilem zapytac.
    W sumie ten post dal mi dobitnie do zrozumienia, ze trzeba wrocic do zadanek w stylu OPSSa, wypadlem z obiegu :)

    @Bartek
    W tym momencie sam wprowadziles swoje warunki ;)

    @Jacek (czyli slodzenie na koniec, co by autor nie poczul sie pominiety)
    Fajny blog, juz od jakiegos czasu odwiedzam, choc nigdy nie starcza mi czasu przebrnac do konca kazdego posta - SA STRASZNIE DLUGASNE :)

    Pozdrawiam.

    OdpowiedzUsuń
  29. @majson - zalozenie, zeby nie wprowadzac wlasnych warunkow, ograniczajacych uniwersalnosc rozwiazania, jest wprowadzaniem warunkow? Jak widze rozwiazanie, ktore dziala np. tylko dla liczb calkowitych to moje pierwsze pytanie brzmi - no dobrze, a co z rzeczywistymi? To jest zadanie na algorytm, nie na implementacje dzialajaca w przy jakims szczegolnym przypadku... Chociaz istotnie, autorow zadowoli takie z tego co wiem:) Ja chcialem podejsc do zabawy bardziej akademicko ;) Sprobuj napisac ten algorytm w jakims pseudo-jezyku - a nie w Javie czy C, to zobaczysz czy musisz dokladac swoje zalozenia...

    OdpowiedzUsuń
  30. Ten komentarz został usunięty przez autora.

    OdpowiedzUsuń
  31. Ten komentarz został usunięty przez autora.

    OdpowiedzUsuń
  32. To byl zart... Gdybym nie mial podobnego podejscia to chyba nie padloby to pytanie, prawda? Zalozylbym z gory, ze "real programmers use integers" i koniec tematu ;) Rzecz w tym, ze algorytm ktory mi szybko wpadl do glowy dziala przy zalozeniach, ze operujemy na liczbach calkowitych z przedzialu [1,N]. Pisalem to na kartce w pseudo-jezyku :) (i nie jest to nic zwiazanego z zasugerowanym powyzej sumowaniem). A algorytmy swoja droga, przyjmuja jakies zalozenia dot. dziedziny problemu (najkrotsze sciezki np.), i moje pytanie wlasnie tego dotyczylo. Nie twierdze przeciez, ze nie da sie w O(n) zweryfikowac tablicy z liczbami rzeczywistymi. Chociaz ciagle tego rozwiazania nie widze :)

    Pzdr

    OdpowiedzUsuń
  33. no w O(n) to sie z rzeczywistymi moze nie dac ;)
    Jest trudniej, nie da sie ukryc. Ale sadze, ze w zamysle zadania bylo jednak zalozenie, ze te liczby sa calkowite nieujemne (naturalne) i dalo sie wartosciami tez inteksowac tablice... Ale za to mamy teraz nowe trudne zadanie - napisac ten algorytm dla liczb rzeczywistych! i jest zabawa...

    OdpowiedzUsuń
  34. Jeśli zakładamy, że w tabeli są liczby rzeczywiste, to zadanie robi się zauważalnie trudniejsze.
    Ba, myślę, że chyba nie łatwo będzie znaleźć algorytm, który zadziała w czasie O(n) (w czasie liniowym).
    Adam

    OdpowiedzUsuń
  35. No wlasnie... stad mnie to optymistyczne O(n) zadziwilo bez doprecyzowania o jakiego rodzaju liczby chodzi :) I w ogole, ze proste... O(2) [swoja droga co to jest? ;)]... i tak dalej.
    pzdr

    OdpowiedzUsuń
  36. Proponuję coś takiego.(w pseudokodzie)

    tablica
    tmpMapa

    for i in tablica {
    tmpMap.put( tablica[i], tablica[i] )
    }
    if (tmpMap.size() == tablica.length) {
    //nie ma powtórzeń
    } else {
    //są powtórzenia
    }

    zajęło mi mniej niż 15 min:) i algorytm działa w czasie liniowym bo dla N-długiej tablicy potrzeba N (z dokładnością co do stałej) operacji do zakończenia algorytmu

    pozdrawiam,
    mb

    OdpowiedzUsuń
  37. Ten komentarz został usunięty przez autora.

    OdpowiedzUsuń
  38. @Michał Bartyzel:
    Przyłączam się do pytania majsona:
    I gdzie tu O(n)?

    Lub - zadając to samo pytanie za pośrednictwem innych słów - jaka struktura danych kryje się za 'tmpMapa', że Twój algorytm działa w czasie O(n)?

    OdpowiedzUsuń
  39. Jako że zagadka cieszy się sporym zainteresowaniem, postanowiłem podejść do problemu systematycznie. :)

    Może znajdzie się ktoś, kto zaproponuje rozwiązanie "optymalne", nie wymagające modyfikacji wejściowej tablicy.

    OdpowiedzUsuń
  40. A co sądzicie o poniższym algorytmie (pseudo-kod)?

    1. index_of_1 <- indeks liczby 1 w tablicy lub jeśli jej nie ma, konczymy funkcję zwracając "false"

    2. index_of_N <- indeks liczby N w tablicy jeśli jest

    3. counter = 1

    4. zaczynając od index_of_1 "przechodzimy" przez całą tablicę traktując całą tablicę jako graf. tzn. wykorzystujemy liczbę znajdującą się pod wskazanym elementem tablicy jako indeksem, który następnie sprawdzamy. W każdym kroku zwiększamy zmienną counter o 1 oraz sprawdzając czy counter jest < N. Jeśli counter = N sprawdzamy, czy jesteśmy pod indeksem index_of_N. Jeśli nie, zwracamy "false", jeśli tak - "true".

    Analizowałem ten algorytm jedynie w głowie i jakoś (dotąd) nie mogłem znaleźć nań kontrprzykładu..

    OdpowiedzUsuń
  41. ojej... widze, ze niektorzy mieli pracowity weekend ;)
    @querty - a co jak ten graf ma cykle?
    np. 5 2 2 4 1

    OdpowiedzUsuń
  42. @Bartek - Ups, racja :( bez zaznaczania poszczególnych elementów jako już odwiedzonych się nie obejdzie, a to pociąga za sobą wykorzystanie dodatkowej pamięci...

    OdpowiedzUsuń
  43. @Michał Bartyzel

    Twoje rozwiazanie mialoby O(N) zlozonosci obliczeniowej, ale pod warunkiem, ze uzyjesz pomocniczej tablicy o tej samej wielkosci co oryginalna. Wtedy jednak bedzie wieksza zlozonosc pamieciowa - O(N). Nie psujemy wtedy tej wejsciowej i mozna to rozwiazac nie wprowadzajac zalozenia, ze tablica moze przechowywac cos innego poza liczbami 1..N.
    Oczywiscie to wszystko dla liczb naturalnych...

    OdpowiedzUsuń
  44. Mnie udało się znaleźć jedynie rozwiązanie mające O(N) złożoności obliczeniowej oraz do użycia tablicy pomocniczej O(N) - tylko dla liczb naturalnych, bez psucia tablicy wejściowej - jest to chyba to samo rozwiązanie o którym pisze Jacek Laskowski. Myślałem jeszcze nad jakimiś zależnościami ciągów arytmetycznego i geometrycznego do uzyskania stałej złożoności pamięci ale na razie wszystkie próby spełzły na niczym.

    Pozdrawiam

    OdpowiedzUsuń
  45. Można tę zagadkę odwrócić ;)
    Udowodnij, że nie ma algorytmu rozwiązującego ten problem (algorytmiki kwantowej nie uwzględniamy;), że (jednocześnie) spełnione są warunki:
    * działa w czasie O(n)
    * zużywa jedynie O(1) dodatkowej pamięci
    * tablice wejściową traktuje jako read-only
    Pozdrawiam

    OdpowiedzUsuń
  46. Przypomne tresc:

    Napisz funkcję (w dowolnym języku programowania), która mają tablicę o długości N zawierającą liczby z zakresu 1 do N stwierdzi, czy występują w niej duplikaty (czy da się to rozwiązać w czasie liniowym? przy stałej pamięci? bez niszczenia zawartości tablicy?)

    To sugeruje liczby naturalne. Widze 2 rozwiazania:
    1. Suma wszystkich elementow powinna byc rowna 2*N -> wystarczy zsumowac elementy i stwierdzic tak/nie

    Zlozonosc O(n)

    2. Mozna uzyc tablicy pomocniczej o dlugosci N (np. boolean dla zminimalizowania pamieci - zainicjowane elementy na false). Przy iteracji po orginalnej do pomocniczej o indexie N wstawiac info: true (wystapila juz). Jesli przed kopiowanie bylo true - liczba sie powturzyla i koniec sprawdzania.

    Max zlozonosc: O(n)


    Dostep do tablic jest staly, if-y sa stale - wiec nie podbijaja zlozonosci O(n) - liniowej
    Gdyby pod spodem (pomocnicza tablica) byla lista, wtedy zlozonosc roznie, bo dostep do N-tego elementu listy nie jest staly.

    OdpowiedzUsuń
  47. @Michał:
    Ad. 1:
    Wystarczy zsumować i stwierdzić, że jest równe 2*N? ;>
    Przecież ten Twój algorytm nie działa nawet dla jednoelementowej tablicy (czyli {1}) ;>

    OdpowiedzUsuń
  48. @Michal
    Ad. 1: kazde podobne rozwiazanie nie ma sensu - to bylaby proba utworzenia krotkiego 'hashcode' dla zbioru liczb i ten 'hashcode' mialby jednoznacznie identyfikowac ten zbior... To nie jest mozliwe, niestety.
    Ad. 2: nie jest takie zle ale widze tam powazny blad ;)

    OdpowiedzUsuń