[Metaliop]

Mirki z #programowanie #programista15k #java i #dotnet Pamieta ktos z Was, albo ma przykładowe zadanie/a jakie można dostać przed/na/po rozmowie kwalifikacyjnej?
Dodam, że jestem początkujący i mają sprawdzić moje umiejętności. Trudne są te zadania, czy coś pokroju programow na ciąg Fibonacciego albo wyznaczanie liczb pierwszych z sita Eratostenesa?

[y.....l]

@Metaliop: Masz listę o nieznanej długości i masz podać jaki element jest na pozycji np. 5 od końca. Trzeba to zrobić jak najmniejszym kosztem. Listę możesz przejechać maksymalnie raz.

[sometwo]

@yggdrasil: nie programuję w javie, ale w wielu językach można to zrobić $var = $list[-5] ; > można też zrobić coś w rodzaju $elemCount = count($list); $var = $list[$elemCount-5]

[Wyrewolwerowanyrewolwer]

@Metaliop:

Trochę o sortowaniach tych nietrywialnych

Masz plik z liczbami o rozmiarze kilkuset GB/TB/cokolwiek (chodzi o to że w cholerę danych). Podać n-największych wartości z tego pliku w czasie niższym niż

[y.....l]

@sometwo Ale to nie jest optymalnie i chodzi o to, żeby powiedzieć algorytm.

[sometwo]

@yggdrasil: w takim razie co jest optymalne i jaki jest do tego algorytm bo nie bardzo rozumiem ? :> Wydaje mi się, że wykorzystanie funkcji języka jest najbardziej optymalne. Pisanie własnego algorytmu to okrężna droga i jest na pewno mniej wydajne.

[nachteil]

@sometwo: Optymalnie byłoby utrzymywać dwa wskaźniki w odległości 5 i gdy ostatni dojdzie do końca, odczytać wartość z wcześniejszego. Plus obsługa przypadków, gdy lista jest krótsza, niż 5, pusta i tak dalej. Skoro nie znamy z góry rozmiaru listy, to i tak musimy co najmniej raz przejść ją całą, więc O(n) jest optymalne.

[radoslaw_rumian]

@nachteil: Czyli w javie dobrym rozwiązaniem byłoby iterować po kolejnych elementach arraya (z zapamiętaniem elementu 5 pozycji wstecz - oczywiście z obsługą list mniejszych niż 5 elementów) i w przypadku wystąpienia ArrayIndexOutOfBoundsException przechwycić wyjątek i wyprintować zapamiętany element? Łapanie takiego wyjątku jest chyba złą praktyką, ale w takim algorytmicznym podejściu może być ok?

[sometwo]

@nachteil: nie rozumiem co jest w tym rozwiązaniu optymalnego. To nic innego jak skomplikowanie nie-skomplikowanego problemu... a i może okazać się mniej wydajne niż użycie zwykłego indexu -5

[qbol1234]

@sometwo: W zadaniach algorytmicznych nie chodzi o to żeby użyć ficzerów danego języka. Chodzi o demonstracje umiejętności rozwiązywania problemów. Wyobraź sobie, ze ta lista którą dostajesz to nie zwykły ArrayList np tylko jakaś egzotyczna struktura danych która nie ma metody size(). Wtedy musisz wymyśleć coś mądrzejszego niż jechanie do końca listy by znaleźć jej długość, jak kolega @yggdrasil powiedział.

[qbol1234]

@Metaliop: Ja np dostałem zadanie z teorii grafów na rozmowie do Amazona. Polecam ksiażkę Cracking the Coding Interview

[sometwo]

@qbol1234: no spoko rozumiem ; > tylko nie nazywałbym tego optymalnym rozwiązaniem ;> to mnie zmyliło

[qbol1234]

@sometwo: P.S. Gdy nie znasz długości listy, to JEST optymalne rozwiązanie. W takiej sytuacji twoje rozwiązanie ma time complexity ~N (~ to takie big O które bierze pod uwagę stałe) a nie ~2N. Czyli jest dwa razy szybsze niż naiwne zliczanie listy.

[sometwo]

Optymalnie byłoby utrzymywać dwa wskaźniki w odległości 5 i gdy ostatni dojdzie do końca, odczytać wartość z wcześniejszego.

@qbol1234: moglbys pokazac implementacje takiego rozwiazania? a juz najlepiej by bylo gdybys zestawil to z tym co zaproponowalem + benchmarki tych rozwiazan :) Wiem, ze o wiele prosze, ale po prostu nie dowierzam co slysze xD

[sometwo]

@qbol1234: i tez nie rozumiem w jaki sposob dojsc do tego ktory element jest -5 na liscie. Bo skoro ma sie 2 wskazniki, i jeden z nich dochodzi do konca to nie ozancza wcale ze poprzedni wskazuje na element -5 z listy.

[y.....l]

@nachteil Brawo! Zdałeś. :)

[sometwo]

@yggdrasil: @nachteil: czy może ktoś z was zaprezentować rozwiązanie tego? właśnie napisałem coś takiego w PHP i ten sposób wychodzi wielokrotnie mniej wydajnie niż zwykłe $element = $list[count($list)-5] , zastanawiam się czy ja coś źle zrobiłem czy po prostu jednak to nie jest optymalne, czy też zależy w dużym stopniu od języka

[y.....l]

@sometwo Nie znam PHP ale pewnie trzyma listę w całości i od razu wie co jest gdzie. Trzeba to sprawdzić na linked listach które są np. w eliksirze.

[sometwo]

@yggdrasil: właśnie zacząłem się zagłębiać w ten temat i najwyraźniej tak właśnie jest - PHP w momencie deklaracji listy zapisuje od razu ilość jej elementów, dlatego później odwołanie $list[count($list)-5] nie jest czasochłonne w żaden sposób. Gdyby patrzeć na zadanie z strony czysto algorytmicznej to faktycznie to rozwiązanie jest dobre, teraz to rozumiem kiedy nie patrzę na to przez pryzmat PHP.

Nawet wpadłem na pomysł jak to zrobić jeszcze lepiej -

[qbol1234]

@sometwo: Nieźle! Ale zauważasz że struktura danych musi supportować przeskok o dowolną ilość elementów. Zwykle w takim zadaniu algorytmicznym chodzi o linked list (lista łączona? nie wiem jak to po polsku) a tam możesz iść tylko o jeden (w obie strony albo nie, zależy jaka lista). https://en.wikipedia.org/wiki/Linked_list Ogólnie polecam algorytmikę, bo robi z ciebie dobrego programistę :)

[qbol1234]

@Wyrewolwerowanyrewolwer:

Masz plik z liczbami o rozmiarze kilkuset GB/TB/cokolwiek (chodzi o to że w cholerę danych). Podać n-największych wartości z tego pliku w czasie niższym niż O(n)

U, a to mnie zagięło. Moja pierwsza myśl to priority queue, ale to jest O(n), bo trzeba przejść przez cały plik. Jakaś podpowiedź? :)