[nad__czlowiek]

#programowanie #programista15k #programista25k #it #pracait #pracbaza #korposwiat

Ja #!$%@?, jak zrobić takie zadanie?

Dzisiaj byłem na rekrutacji i dostałem do zrobienia na kartce w 30 minut. Podobno większość to rozwiązała a ja nawet nie wiedziałem jak to gówno zacząć xD

Jakby ktoś pytał to takie zadanka teraz dają dla Senior Java Spring Boot CRUD developera z AWS, kubernetesem i terraformem w stacku, stawka 21 000 zł netto b2b + VAT (bez urlopów, hybryda 2 dni z biura). Co to w ogóle jest jakieś modulo?

Given two positive integers low and high represented as strings, find the count of stepping numbers in the inclusive range [low, high].

A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.

Return an integer denoting the count of stepping numbers in the inclusive range [low, high].

Since the answer may be very large, return it modulo 10^9 + 7.

Note: A stepping number should not have a leading zero.

Constraints:

1 <= int(low) <= int(high) < 10^100

1 <= low.length, high.length <= 100

low and high consist of only digits.

low and high don't have any leading zeros.

Example 1:

Input: low = "1", high = "11"

Output: 10

Example 2:

Input: low = "90", high = "101"

Output: 2

[PolishPsycho]

@Creamfields: @nad__czlowiek No przecież nie będziesz iterował po tak ogromnych liczbach które mają 100 znaków (po to zostały podane te ograniczenia). Zaczynasz np. od węzła 1 i lecisz albo BFS albo DFS, czyli analogicznie BFS:
101, 121, 123.
lub DFSem w głąb.

z węzła 1 możesz iść do 2 lub do 0, z 9 tylko do 8 itp.

[dwukropekD]

@nad__czlowiek: nie chcę cię dołować, ale tego typu zadania rozwiązuje się na pierwszym roku informatyki na polibudzie xD

[walokid]

@nad__czlowiek: https://onlinegdb.com/C76dCJSon

Nie zastanawialem się nad corner casami ( ani nad złożonością)

[slgdfhsdhjfbs]

nie chcę cię dołować, ale tego typu zadania rozwiązuje się na pierwszym roku informatyki na polibudzie xD

@dwukropekD: Ale to nie jest rekrutacja na studenta informatyki ani kolos na zaliczenie semestru, tylko rekrutacja do pracy :P widocznie studenci lepiej sobie z tym poradzą. Też bym wymiękł (senior java dev z 9 latami stażu here).

[unlucky_]

@dwukropekD
Co z tego? Myślisz, ze ja po 6 latach na bieżąco sobie przypominam algorytmy ze studiów? xD
Albo zaawansowana matematykę? XD

Ja po 6 latach od zrobienia mgr na polibudzie nic z tego nie pamiętam. Wiedza wyparowała, bo nie była mi potrzebna

[Creamfields]

@PolishPsycho: na razie nie padło żadne ograniczenie na złożoność obliczeniową

[unlucky_]

@Creamfields: dla gimnazjalisty, a dałbym low = 1, high 10^100 to by sie #!$%@? na tym twoim algorytmie XD

[sierramikebravo]

@nad__czlowiek: Zadania nie zrobię, ale jak programista nie wie co to modulo, to trochę słabo.

[Creamfields]

@unlucky_: a to niby dlaczego?

[keksoa]

@nad__czlowiek:

no a najgorsze że podobno masa kuców takie zadania robi bez żadnego przygotowania xD

To raczej bzdura.

Najbardziej gnije że pewnie i tak klepanie cruda, miałem szefa co lubił się znęcać nad ludźmi algorytmami, a robota?

[Dalamar]

@nad__czlowiek: uwielbiam takie zadania, które nigdy nie mają nic wspólnego z faktyczną pracą xD

po pierwsze musiałbym się dowiedzieć czym są stepujące liczby, a pewnie googla używać nie wolno xD

po drugie nie wiem do czego miałoby służyć modulo 10^9 + 7, poza sprawdzeniem czy delikwent zna na pamięć wszystkie metody z biblioteki matematycznej

[szatanskii]

@nad__czlowiek: Nie wiem czy wszyscy tutaj trollują, ale nie wiedzieć czym jest modulo lub jak rozwiązać tego typu zadanie (no może poza bezbłędnym zakodowaniem na kartce) to chyba jednak żart. Z drugiej strony nie używam Javy, może tam nie używa się modulo i nigdy niczego nie liczy.

[ardiuno]

@Creamfields: za pierwszym razem jak przeczytałem to też od razu pomyślałem o tym rozwiązaniu, ale wątpię, że o to chodzi, bo przy tak dużych zakresach będzie to kompletnie niewydajne.

Myślę, że da się tutaj znaleźć pewien schemat, patrząc na liczbę cyfr w danej liczbie:

- od 1 do 9 mamy 9 takich liczb
- od 10 do 99 mamy mamy w każdej dziesiątce po 2, np. 10, 12 czy 21, 23 czy 32, 34, wyjątkiem jest zakres 90-99, gdzie jest tylko 98, czyli w zakresie od 10 do 99 jest takich

[darktemplar]

@nad__czlowiek: na 1 rzut oka nie wiem o co chodzi, kilkanaście lat w branży

nic nie pamiętam ze studiów z matmy, algo, itp, bo tego nie używam w pracy wiec czemu mam pamiętać coś co było dajmy na to 15 lat temu? ja juz nie pamiętam niektórych dziewczyn w z którym się r.v.ch.alem

[MalowanyPtak]

@nad__czlowiek stringa traktować jako inta, liczyć różnice pomiędzy n a n+1 wyrazem, jeżeli równa 1 to dodawać do counta. Sprawdzać z n-1 i jak był, to dodawac do sumy wyniku. To pierwszy rok studiow. O ile dobrze rozumiem, bo napisane jakby to pisał hindus.

[nad__czlowiek]

@MalowanyPtak: no ale ci koledzy napisali że jest #!$%@? zakres 10^100 wiec nie zrobisz sobie pętli bo ci wywali stackoverflow, trzeba jakoś kombinować z wzorami

[unlucky_]

@Creamfields: Bo przy tych założeniach napisałeś infinity loopa?
Jakoś to będzie działać do 10^10 (już tutaj będą potrzebne minuty na znalezienie rozwiązania).
I pytanko, jak chcesz przechowywać wartość 10^100?

@nad__czlowiek
Chłopy napisały infinity loopy, a się z Ciebie śmieją, niebywałe xD

[MalowanyPtak]

@nad__czlowiek: W takiej formie to może być nawet problem z wyświetleniem liczby (nie znam się na javie). Można zrobić chyba customowy float, ale nie wiem czy się zmieści.

[unlucky_]

@MalowanyPtak: Na swoim doemnowym jezyku tez jezeli myslisz ze mozesz zapisac liczbe 10^100 w typie prostym xDD