NotABigFan
  • 3
Dzisiaj zadanie od Amazon:

Dana jest liczba k i napis s. Znajdź długość najdłuższego podłańcucha s, który składa się z najwyżej k różnych znaków.

np.:
dla s = "abcba", k = 2 wynikiem jest 3
  • 23
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
bladykiel
bladykiel
  • 1
@NotABigFan: Na szybko (byle działało) wyszło mi coś takiego :) Jak znajdę chwilkę czasu, to napiszę to lepiej :) (musi się dać to wykonać tylko z jednym forem)

private static String getMaxSubstring(String text, int k) {
char[] str = text.toCharArray();
String s = "";
Set set =
  • Odpowiedz
S.....s
S.....s
  • 1
@Frogof no ale zwykle w takich zadaniach jest a - z xd a przy słowniku też masz taką samą złożoność, ewentualnie ograniczoną przez n
Ale no dobra, w pewnych przypadkach słownik może zajmować mniej pamięci
  • Odpowiedz
NotABigFan
  • 3
Czołem Wielkiej Polsce! Dzisiaj zadanko od Stripe.

Dana jest tablica liczb całkowitych. Znajdź najmniejszą dodatnią liczbę całkowitą, której nie ma w tablicy. Tablica może zawierać duplikaty oraz liczby ujemne. Można modyfikować tablicę. Czas O(n), pamięć O(1)

np:

[]
  • 28
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
D.....n
D.....n
  • 6
@NotABigFan:
Dla kolejnych elementów tablicy robimy tak:
- jeśli tab[i] <= 0, to nic nie robimy (traktuję takie miejsca jako "puste")
- w p.p. bierzemy x = tab[i] i dalej
-- jeśli x > większe od rozmiaru tablicy, to je "usuwam", tzn. robię tab[i] = 0
-- w p.p. wrzucam x w tab[x], czyli chciałbym, żeby każdemu odpowiadało jego miejsce w tablicy, a tab[i] czyszczę (ustawiam
  • Odpowiedz
NotABigFan
  • 4
Wracam po banie (Ich bereue nichts) z następnym zadaniem od Airbnb:

Dany jest ciąg liczb całkowitych. Zwróć największą sumę niesąsiadujących ze sobą liczb z tego ciągu.

np:

[]
  • 24
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
exother
  • 1
@NotABigFan: Ogólnie powinno działać coś takiego: lecimy po kolei i dla każdej i-tej pozycji trzymamy maksymalną sumę, którą do tej pory udało się osiągnąć i teraz mamy dwie opcje: bierzemy i-tą liczbę albo nie, jeżeli bierzemy to aktualnie największą sumą jest wartość i-tej liczby + największa suma i-2, jeżeli nie to i-1 i z tych dwóch wartości bierzemy maxa. To puszczamy od i=2, ustawiamy max sumę dla i=0 i i=1
  • Odpowiedz
NotABigFan
  • 6
Piątunio, więc chill. Zadanko od Googla.

Dane są dwie acykliczne listy jednokierunkowe, które przecinają się w pewnym miejscu. Znajdź to miejsce (pierwszy węzeł wspólny dla obu list). Czas liniowy względem sumy długości list i pamięć stała. Można modyfikować listę.

#programowanie #dailycodingproblem
  • 31
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
Frogof
Frogof
  • 2
@NotABigFan: nie czytałem komentarzy. Dwa wskaźniki, wyprzedź ten z krótszej listy o różnice długości list. Przesuwaj wskaźniki, jak są równe to masz ten węzeł którego szukałeś.
  • Odpowiedz
NotABigFan
  • 3
Czwartek to mały piątek, dzisiaj zadanko z Googla.

Masz tablicę złożoną wyłącznie ze znaków 'R', 'G' lub 'B'. Posortuj tę tablicę tak, że każde 'R' jest przed 'G' i każde 'G' przed 'B'. Możesz tylko swapować elementy (czyli zliczanie odpada).

np. ['G', 'B', 'R', 'R', 'B', 'R', 'G'] -> ['R', 'R', 'R', 'G', 'G', 'B', 'B']

Czas
  • 18
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
D.....n
D.....n
  • 1
@NotABigFan: Bierzemy dwa wskaźniki: oba ustawiamy na początek listy, ew. jeśli jest tam prefiks składający się z R, to przesuwamy oba do momentu zakończenia listy albo znalezienia nie-R.

Jednym wskaźnikiem idziemy do przodu do momentu znalezienia R - wtedy swapujemy zawartość spod obu wskaźników i przesuwamy +1 ten, który był zostawiony na początku listy. W końcu dolecimy do końca listy, uzyskując w ten sposób prefiks składający się
  • Odpowiedz
NotABigFan
  • 3
Na wyluzowanie dzisiaj trochę prostsze. Zadawane przez Jane Street:

Niech cons(a, b) tworzy parę p i niech car(p) i cdr(p) zwracają kolejno pierwszy i drugi element pary. np.

car(cons(3, 4)) -> 3
cdr(cons(3, 4)) -> 4
  • 19
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
NotABigFan
  • 3
Kolejne zadanko na miło spędzone popołudnie. Tak jak poprzednie: nieco trikowe i również jak poprzednie zadawane m.in. przez Google na kochanych przez wszystkich whiteboardowych sesjach rekrutacyjnych.

Masz tablicę (powiedzmy xs) n liczb i liczbę k gdzie 1 <= k <= n. Oblicz maksymalną wartość dla kolejno każdego spójnego fragmentu tablicy o rozmiarze k.

np. xs=[10, 5, 2, 7, 8, 7] i k=3 -> [10, 7, 8,
  • 13
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
D.....n
D.....n
  • 1
@NotABigFan: Utrzymywać pomocniczą "kolejkę" elementów z obserwowanego okienka w taki sposób, że elementy w tej kolejce są w porządku nierosnącym. Tzn. elementem kolejki jest para (indeks, wartość), kolejne elementy są w stronę rosnących indeksów i malejących wartości. Taka kolejka ma maksymalnie k elementów. Może mieć mniej, jeśli obserwowane okienko nie jest złożone z elementów nierosnących, tylko ma ekstrema.

Mając taką pomocniczą strukturę, max z okienka to wartość pierwszego elementu kolejki.
  • Odpowiedz
D.....n
D.....n
  • 1
@NotABigFan: Zwizualizuj sobie tę kolejkę jako np. listę wskaźnikową. Max jest z lewej strony. Jak wywalisz maksymalny element, to drugi masz zaraz obok i nie musisz już niczego przestawiać (dzięki niezmiennikowi). O(1) operacja.

Jak pojawia się nowy element, to dla zachowania niezmiennika być może musisz coś wywalić z prawej strony. Wywalenie jednego elementu kosztuje O(1), potem wstawienie O(1). Łącznie masz max. n wstawień i usunięć, więc amortyzuje się do O(n).
  • Odpowiedz
NotABigFan
  • 11
Mam fajne zadanko, które ponoć występuje jako pytanie rekrutacyjne do Google.

Masz tablicę nieujemnych liczb całkowitych gdzie każda liczba występuje dokładnie 3 razy oprócz jednej która występuje dokładnie raz. Wskaż liczbę która występuje dokładnie raz. Czas O(n) i uwaga pamięć O(1).

np. dla [3, 1, 4, 1, 1, 3, 3] -> 4

#programowanie #dailycodingproblem
  • 16
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
NotABigFan
  • 4
const person = {
name: "Mirek",
greet() {
console.log("Cześć, nazywam się " + this.name + ".");
},
};

Co zostanie wypisane na konsolę?

  • Nic 10.3% (4)
  • błąd/wyjątek 35.9% (14)
  • Cześć, nazywam się Mirek. 17.9% (7)
  • Cześć, nazywam się undefined. 35.9% (14)

Oddanych głosów: 39

  • 16
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
NotABigFan
  • 7
function Person(name) {
this.name = name;
return "Mirabelka";
}

const person = new Person("Mirek");

Co będzie wypisane na konsolę?

  • Person { name: 'Mirek' } 39.1% (18)
  • Mirabelka 47.8% (22)
  • undefined 2.2% (1)
  • błąd/wyjątek 10.9% (5)

Oddanych głosów: 46

  • 6
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
Marmite
Marmite
via Wykop Mobilny (Android)
  • 1
@trevoz: ale wiesz, że te wyniki się zmieniają w czasie, a moja odpowiedź dotyczy pewnego konkretnego momentu, tzn. tego, w którym była pisana?
  • Odpowiedz
mazx
  • 6
@NotABigFan: kurde myślałem że uderzył pod kolano, tam gdzie każdemu może się złamać. A on tymczasem trafił w miękkie udo i mu się złamała, tragedia ten grubas.
A wystarczyłoby żeby matka nie piła w ciąży
  • Odpowiedz
C.....y
C.....y
  • 3
Ayende, Scott Allen, Scott Hanselman, Sound of Code, Martin Zikmund i Christian Nagel (raczej z przyzwyczajenia, bo XAMLami to teraz się raczej nie zajmuję), do tego blog ASP .NET i .NETa z MSu, to tak z pamięci
  • Odpowiedz
NotABigFan
  • 2
#programowanie #python #regexp
Powiedzmy, że mam sobie drzewo binarne liczb całkowitych zapisanych w stringu za pomocą nawiasów. Np.: "((- 1 -) 0 (((- 1 -) 1 (- 1 -)) 0 (- 0 -)))" czyli drzewo to "-" lub "(lewePoddrzewo liczba prawePoddrzewo)". Jest jakieś wyrażenie regularne które da mi trzy grupy dla niepustego drzewa tak, żeby się nawiasy zgadzały? Próbowałem czegoś takiego:
r'\((\(.+\)|-) (\d+) (\(.+\)|-)\)' ale dostałem
  • 12
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach

Osiągnięcia