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
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?!
To chyba nie jest trudne zadanie :-)
OdpowiedzUsuńMożna załatwić to jedną linijka (w javie):
boolean czySaDuplikaty = new HashSet(Arrays.asList(tablica)).size() == tab.length;
pozdrawiam
Łukasz Sierant
Ha! Przejęzyczenie ;) Warunek musi być oczywiście odwrotny :)
OdpowiedzUsuń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ę. :)
OdpowiedzUsuńZe swojej strony dorzucam jeszcze wymaganie co do optymistycznej złożoności obliczeniowej algorytmu na poziomie O(2). :)
Pogłówkowałem trochę i udało mi się znaleźć algorytm, który spełnia wszystkie z warunków, czyli:
OdpowiedzUsuń* 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
Jeśli ktoś ma ochotę na kolejną zagadkę (ale już BEZ nagród!) to zapraszam na swój blog i opublikowaną zagadkę:
OdpowiedzUsuńhttp://adamwozniak.blogspot.com/2008/07/zagadka-algorytmiczna.html
:)
Ludzie, no przeciez to jest banalne zadanie... a zlozonosc to O(1), nie O(2), bez zadnych dodatkowych tablic...
OdpowiedzUsuńNo to oświeć mnie (nas), Bartek.
OdpowiedzUsuńMój algorytm działa w czasie O(N), więc ten Twój jest lepszy. Chętnie poznam ;)
hmm... troche zbyt pochopnie to napisalem, zwracam honor. Faktycznie zlozonosc to O(n) liniowo zalezna od wielkosci tablicy. Oczywiscie dalej problem jest banalny ;)
OdpowiedzUsuńBartek:
OdpowiedzUsuńA jak ze złożonością pamięciową?
I czy tablica pozostaje niezmieniona? ;)
hm, a czy zakladacie, ze tablica wejsciowa jest read-only ?
OdpowiedzUsuńJa założyłem, że nie jest read-only.
OdpowiedzUsuńZ resztą, gdyby była read-only to byłoby to napisane w treści zagadki.
OdpowiedzUsuńsadze, ze optymalne rozwiazanie zaklada, ze jest rean-only... do tego potrzeba pamieci pamieci na powiedzmy 2 elementy o typie elementow tablicy
OdpowiedzUsuń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ń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ńBartek: OK, to podeślij kod / albo pomysł na algorytm na adres znajdujący się na gmailDOTcom:
OdpowiedzUsuńyadaslawy (usuń literki 'y')
Ja Ci zwrotnie wyślę mój kod (jak w ogóle chcesz).
poszlo...
OdpowiedzUsuńa Twojego rozwiazania jestem ciekawy :)
O, dostałem od Ciebie propozycje rozwiązania :)
OdpowiedzUsuń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
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. :)
OdpowiedzUsuńCzy ktoś jest zainteresowany?
morisil:
OdpowiedzUsuńJa jestem zainteresowany:
Mój adres znajdujący się na gmailDOTcom:
yadaslawy (usuń literki 'y')
morisil:
OdpowiedzUsuń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'
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ńmajson: wszystko napisane jest w treści zadania.
OdpowiedzUsuń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
Byc moze, ale nie odpowiedziales na moje pytanie :) Nie jest jasno okreslone do jakiego zbioru naleza te liczby.
OdpowiedzUsuńA tak gwoli scislosci - piszac zbior mam na mysli np. zbior liczb naturalnych, calkowitych, rzeczywistych etc.
OdpowiedzUsuńFaktycznie, w treści zagadki nie jest sprecyzowane jakiego typu są to liczby ;)
OdpowiedzUsuń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.
... i w sumie - skoro typ danych w zagadce nie jest wyspecyfikowany - możemy podeprzeć się zasadą:
OdpowiedzUsuńReal programmers use integers.
;)
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ń@Adam
OdpowiedzUsuń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.
@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ńTen komentarz został usunięty przez autora.
OdpowiedzUsuńTen komentarz został usunięty przez autora.
OdpowiedzUsuń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 :)
OdpowiedzUsuńPzdr
no w O(n) to sie z rzeczywistymi moze nie dac ;)
OdpowiedzUsuń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...
Jeśli zakładamy, że w tabeli są liczby rzeczywiste, to zadanie robi się zauważalnie trudniejsze.
OdpowiedzUsuńBa, myślę, że chyba nie łatwo będzie znaleźć algorytm, który zadziała w czasie O(n) (w czasie liniowym).
Adam
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.
OdpowiedzUsuńpzdr
Nie ma czegoś takiego jak O(2) ;)
OdpowiedzUsuńProponuję coś takiego.(w pseudokodzie)
OdpowiedzUsuń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
I gdzie tu O(n)? Cos nie bangla.
OdpowiedzUsuńTen komentarz został usunięty przez autora.
OdpowiedzUsuń@Michał Bartyzel:
OdpowiedzUsuń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)?
Jako że zagadka cieszy się sporym zainteresowaniem, postanowiłem podejść do problemu systematycznie. :)
OdpowiedzUsuńMoże znajdzie się ktoś, kto zaproponuje rozwiązanie "optymalne", nie wymagające modyfikacji wejściowej tablicy.
A co sądzicie o poniższym algorytmie (pseudo-kod)?
OdpowiedzUsuń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..
ojej... widze, ze niektorzy mieli pracowity weekend ;)
OdpowiedzUsuń@querty - a co jak ten graf ma cykle?
np. 5 2 2 4 1
@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ń@Michał Bartyzel
OdpowiedzUsuń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...
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.
OdpowiedzUsuńPozdrawiam
Można tę zagadkę odwrócić ;)
OdpowiedzUsuń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
Przypomne tresc:
OdpowiedzUsuń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.
@Michał:
OdpowiedzUsuń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}) ;>
@Michal
OdpowiedzUsuń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 ;)