[NotABigFan]

Zadanie od Amazon:

RLE jest prostą metodą kodowania ciągów znaków. Każdy maksymalny podciąg (w sensie substring) tekstu wejściowego złożony wyłącznie z k znaków c jest kodowany jako "kc".
np. "AAAABBBCCDAA" zakodowany RLE to "4A3B2C1D2A"

Zaimplementuj kodowanie i dekodowanie RLE. Możesz założyć, że napis do zakodowania będzie złożony wyłącznie z małych i dużych liter alfabetu. Możesz też założyć, że napis do zdekodowania jest poprawnym kodowaniem RLE.

#dailycodingproblem #programowanie

[glonstar]

@NotABigFan: To na pewno Amazon, a nie informatyka w podstawówce?

[NotABigFan]

@glonstar: dostosowują poziom do tego co dostają ( ͡° ͜ʖ ͡°) zadanie może nie jest trudne ale pokazuje jaki kod piszesz, jak chcesz sobie urozmaicić to napisz to w lispie albo haskellu

[Przegrywek123]

@NotABigFan: to jest w sumie dość proste, i o ile się nie mylę tego algorytmu używa wszystko co kompresuje pliki.

[Saly]

@NotABigFan: na drugim semestrze mialem to samo do napisania, tylko że w asemblerze xd

[Saly]

@Przegrywek123: nie. RLE słabo radzi sobie z rzeczywistymi danymi, przykładowo mając takiego jsona: [{"ala":"ma kota"}, ... 10000 powtórzeń dalej ..., {"ala":"ma kota"}] możemy zauważyć, że plik mocno kompresowalny, natomiast RLE w tym wypadku nic nie robi.

[Przegrywek123]

@Saly: W sumie mówiąc wszystko miałem na mysli winrara, mój błąd xD

[Wyrewolwerowanyrewolwer]

@glonstar: @NotABigFan: wtf
A jeszcze 3 lata temu Amazon pytał mnie o sortowanie szybciej niż O(n) ( ͡° ʖ̯ ͡°)( ͡° ʖ̯ ͡°)( ͡° ʖ̯ ͡°)( ͡° ʖ̯ ͡°)

[NotABigFan]

@Wyrewolwerowanyrewolwer: to chyba nie jednym rdzeniem ( ͡° ͜ʖ ͡°)

[Wyrewolwerowanyrewolwer]

@NotABigFan: Jednym jednym ( ͡° ͜ʖ ͡°)

[NotABigFan]

@Wyrewolwerowanyrewolwer: Ale co miałeś jakieś ciekawe ograniczenia? Bo nie da się szybciej niż n lg n przez porównywanie elementów i szybciej niż O(n) jak masz ograniczenie na wielkość przez zliczanie

[Wyrewolwerowanyrewolwer]

@NotABigFan: Nie mogę zbyt wiele powiedzieć.

Powiem tylko że:

Bo nie da się szybciej niż n lg n przez porównywanie elementów i szybciej niż O(n) jak masz ograniczenie na wielkość przez zliczanie

Da się, jeżeli możesz się delikatnie pomylić.
Teraz już chyba proste.

[NotABigFan]

Nie mogę zbyt wiele powiedzieć.

@Wyrewolwerowanyrewolwer: Haha tajny algorytm służb specjalnych ( ͡° ͜ʖ ͡°)
Nawet sprawdzenie czy tablica jest posortowana zajmuje O(n) więc muszą być ograniczenia lub nawet to nie chodzi o tablice. Co to znaczy delikatnie pomylić? można odpalić shell sorta dla paru gapów ale to nie zmniejszy złożoności o cały rząd.

[Wyrewolwerowanyrewolwer]

@NotABigFan nie haha tajny algorytm tylko umowa.
Tak, przeiterowanie po tablicy zajmuje n.
Ale to w momencie kiedy masz juz tablice.
A co gdyby po przyjrzeniu się danym okazało się że mają jakiś rozkład albo w pewien charakterystyczny sposób zmieniają swoje wartości?
Albo inaczej - co gdyby dało się określić ze a[i] z jakimś niezerowym prawdopodobieństwem plasuje się w x% największych wartości zbioru?

[Wyrewolwerowanyrewolwer]

@NotABigFan tak, myślę że daje skoro ma ostry nacisk na nda.

Do tych warunków musiałem dojść/dopytać w trakcie rozmowy, nic nie było podane na tacy.
Zacząłem rozmowę praktycznie od poziomu identycznego co mój pierwszy post tutaj.