|
|
 Up |
|
|
  |
Author: mariuszmariusz Date: May 9, 2008 06:06
Witam!
Na rozmowie kwalifikacyjnej dostałem pytanie:
Jest plik, który zawiera informacje o urządzeniach rozmieszczonych
gdzieś po świecie. Każda linijka w tym pliku zawiera adres domenowy
urządzenia i nazwę kraju w którym to urządzenie się znajduje. Plik ma
powiedzmy 500 tyś rekordów. Pytanie brzmiało:
Do jakiej struktury danych najlepiej załadować takie dane z pliku aby
jak najszybciej (jak najmniejsza ilość porównań) wyszukać kraj na
podstawie podanego adresu domenowego.
Powiem szczerze że jak na razie nic sensownego nie przychodzi mi do
głowy i stąd pytam się na grupie.
Z góry dzieki
|
| |
|
| | 35 Comments |
|
|
Author: Stachu 'Dozzie' K.Stachu 'Dozzie' K. Date: May 9, 2008 06:12
On 09.05.2008, mariusz nospam.com> wrote:> Witam!
>
> Na rozmowie kwalifikacyjnej dostałem pytanie:
>
> Jest plik, który zawiera informacje o urządzeniach rozmieszczonych
> gdzieś po świecie. Każda linijka w tym pliku zawiera adres domenowy
> urządzenia i nazwę kraju w którym to urządzenie się znajduje. Plik ma
> powiedzmy 500 tyś rekordów. Pytanie brzmiało:
> Do jakiej struktury danych najlepiej załadować takie dane z pliku aby
> jak najszybciej (jak najmniejsza ilość porównań) wyszukać kraj na
> podstawie podanego adresu domenowego.
>
> Powiem szczerze że jak na razie nic sensownego nie przychodzi mi do
> głowy i stąd pytam się na grupie.
No cóż, nie każdy musi pracować jako programista. Odpowiedź jest
trywialna dla każdego, kto miał kiedykolwiek przedmiot "algorytmy
i struktury danych".
|
| Show full article (0.89Kb) |
|
| | no comments |
|
|
Author: Micha³ 'Khorne' RzechonekMicha³ 'Khorne' Rzechonek Date: May 9, 2008 07:06
On May 9, 3:12 pm, "Stachu 'Dozzie' K."
wrote:
> Odpowiedź jest
> trywialna dla każdego, kto miał kiedykolwiek przedmiot "algorytmy
> i struktury danych".
Czy ja wiem czy taka trywialna... zależy np. ile się ma pamięci itd.
Bentley w "perełkach" ma fajne przypadki "trywialnych" zadań.
pozdr
Khorne
|
| |
| no comments |
|
|
Author: Stachu 'Dozzie' K.Stachu 'Dozzie' K. Date: May 9, 2008 07:22
On 09.05.2008, Michał 'Khorne' Rzechonek gmail.com> wrote:> On May 9, 3:12 pm, "Stachu 'Dozzie' K."
> wrote:
>> Odpowiedź jest
>> trywialna dla każdego, kto miał kiedykolwiek przedmiot "algorytmy
>> i struktury danych".
>
> Czy ja wiem czy taka trywialna... zależy np. ile się ma pamięci itd.
Michał, do pytania jakie zostało zadane to już jest sztuczne szukanie
utrudnień.
> Bentley w "perełkach" ma fajne przypadki "trywialnych" zadań.
--
Secunia non olet.
Stanislaw Klekot
|
| |
| no comments |
|
|
Author: Krzysztof HalasaKrzysztof Halasa Date: May 9, 2008 17:26
"Stachu 'Dozzie' K." writes:
>> Jest plik, który zawiera informacje o urządzeniach rozmieszczonych
>> gdzieś po świecie. Każda linijka w tym pliku zawiera adres domenowy
>> urządzenia i nazwę kraju w którym to urządzenie się znajduje. Plik ma
>> powiedzmy 500 tyś rekordów. Pytanie brzmiało:
>> Do jakiej struktury danych najlepiej załadować takie dane z pliku aby
>> jak najszybciej (jak najmniejsza ilość porównań) wyszukać kraj na
>> podstawie podanego adresu domenowego.
> No cóż, nie każdy musi pracować jako programista. Odpowiedź jest
> trywialna dla każdego, kto miał kiedykolwiek przedmiot "algorytmy
> i struktury danych".
Trywialna moze tak, ale niekoniecznie poprawna.
Mozna to zaladowac do kilku roznych struktur przy koszcie log2(n),
np. do (zrownowazonego) drzewa binarnego, albo do posortowanej
tablicy. Zaleznie od n lepsze moze byc skorzystanie z tablicy hashow
itd. Przy 500 tys. rekordow "ASCII", jesli nie zalezy nam za bardzo na
pamieci, wielka tablica hashow bedzie na pewno lepsza, wystarczy 0
porownan :-)
|
| Show full article (1.22Kb) |
| no comments |
|
|
Author: Micha³ 'Khorne' RzechonekMicha³ 'Khorne' Rzechonek Date: May 10, 2008 05:11
On May 9, 3:22 pm, "Stachu 'Dozzie' K."
wrote:
> Michał, do pytania jakie zostało zadane to już jest sztuczne szukanie
> utrudnień.
Wiem :)
pozdr
Khorne
|
| |
| no comments |
|
|
Author: mariuszmariusz Date: May 11, 2008 23:46
Stachu 'Dozzie' K. pisze:
>
> No cóż, nie każdy musi pracować jako programista. Odpowiedź jest
> trywialna dla każdego, kto miał kiedykolwiek przedmiot "algorytmy
> i struktury danych".
>
No cóż, nie każdy programista musi się znać na wszystkim. Tak się
złożyło że kilka lat temu miałem przedmiot "algorytmy i struktury
danych" ale nie najlepiej poprowadzony bo akurat nie przypominam sobie
aby ktoś tam wspominał o hashmapach.
Twoja odpowiedź nic mi nie pomogła no ale trudno. Inni użytkownicy
okazali się bardziej pomocni dlatego już wiem gdzie dalej szukać. Tak to
jest na grupach dyskusyjnych że czasem trzeba przyjąć też słowa krytyki
zamiast pomoc.
W każdym razie dzięki
Mariusz
|
| |
| no comments |
|
|
Author: Stachu 'Dozzie' K.Stachu 'Dozzie' K. Date: May 12, 2008 01:04
On 12.05.2008, mariusz nospam.com> wrote:> Stachu 'Dozzie' K. pisze:
>>
>> No cóż, nie każdy musi pracować jako programista. Odpowiedź jest
>> trywialna dla każdego, kto miał kiedykolwiek przedmiot "algorytmy
>> i struktury danych".
>>
>
> No cóż, nie każdy programista musi się znać na wszystkim. Tak się
> złożyło że kilka lat temu miałem przedmiot "algorytmy i struktury
> danych" ale nie najlepiej poprowadzony bo akurat nie przypominam sobie
> aby ktoś tam wspominał o hashmapach.
Jeśli chcesz wiedzieć, to haszmapy występują w Perlu, Pythonie, Tclu
i Rubym jako typ wbudowany w język, a w C++ i Javie jako element
biblioteki standardowej, tak więc twoje tłumaczenie "bo mi na zajęciach
nie mówili" wydaje się trochę głupie.
|
| Show full article (1.11Kb) |
| no comments |
|
|
Author: Jedrzej DudkiewiczJedrzej Dudkiewicz Date: May 12, 2008 01:12
Stachu 'Dozzie' K. wrote:
> Jeśli chcesz wiedzieć, to haszmapy występują w Perlu, Pythonie, Tclu
> i Rubym jako typ wbudowany w język, a w C++ i Javie jako element
> biblioteki standardowej,
Uściślenie: w C++ dopiero będą występować. Ale już teraz dostępne są w
większości implementacji jako rozszerzenie.
JD
|
| |
| no comments |
|
|
|
|
|
Author: Stachu 'Dozzie' K.Stachu 'Dozzie' K. Date: May 12, 2008 01:15
On 12.05.2008, Jedrzej Dudkiewicz gmail.com.bez.pl> wrote:> Stachu 'Dozzie' K. wrote:
>> Jeśli chcesz wiedzieć, to haszmapy występują w Perlu, Pythonie, Tclu
>> i Rubym jako typ wbudowany w język, a w C++ i Javie jako element
>> biblioteki standardowej,
>
> Uściślenie: w C++ dopiero będą występować.
Fakt. W bibliotece standardowej są mapy z wyszukiwaniem binarnym, nie
haszmapy. Ale interfejs jest ten sam, tylko gwarancje na czas wykonania
są inne.
> Ale już teraz dostępne są w
> większości implementacji jako rozszerzenie.
--
Secunia non olet.
Stanislaw Klekot
|
| |
| no comments |
|
RELATED THREADS |
|
|
|
|
|
|
