Zanimljiv programerski zadatak

Programiranje
1

Sheram jedan zadačić…razonode radi…tko voli razmišljati na programeski način, uživat će. :slight_smile:

Programiranje zapravo uopće nije potrebno…dovoljno je dati ideju kako bi se problem rješio.

Problem je sljedeći:

  • imamo mnogokut
  • što znači da su mu sve stranice ravne
  • mnogokut međutim može biti nepravilan
  • što znači da je moguće spojiti dvije točke mnogokuta, a da linija koja spaja te dvije točke izađe izvan mnogokuta
  • drugim riječima, nepravila mnogokut je slovo “W” (Zamislimo naravno debljinu linije slova, kako bi dobili površinu mnogokuta “W”)
  • jedina slova koja su pravilan mnogokut su slova “I” i “D” “O”. Naravno, kod “D” i “O” moramo zamisliti da zaobljene linije razbijemo na više ravnih linija. Sva druga slova bi bila nepravilan mnogokut.

Svaki mnogokut znači može imati koliko god točaka koje predstavljaju neki njegov vrh. I to je njegova definicija…te točke u prostoru. (Ako smo u 2D sustavu, svaka točka ima x,y vrijednost)

Bitan je i redosljed točaka koji nam mora biti poznat…jer on nam govori koji vrh je sa kojim spojen…tj. definira koje su stranice mnogokuta.

I sada zadatak:

Kako odrediti da li dva mnogokuta (čiji su nam vrhovi poznati) imaju zajednički presjek?

Uživajte. :slight_smile:

1 Like
2

Za ideju evo 7 sekundi guglanja:

2 Likeova
3

Nešto si krivo shvatio. Nije potrebno rješenje…nego tko želi da uživa u osmišljavanju rješenja.

Ti si vidim jako ponosan kad ti netko da logičku zagonetku, a ti ga zaebeš jer znaš kako ćeš da izguglaš rješenje. xd xd.

Zagonetke su da se rješavaju, ne da se šapću rješenja.

A što se tiče ovog gore problema, ima na svu sreću više zanimljivih rješenja. Jedno je baš predivno…a začudo nisam našao da se spominje. To me ujedno motiviralo za temu…pa ako se netko sjeti nečeg jako zanimljivog, neka puca :slight_smile:

4

P.S. nisu ti čak niti linkovi dobri, jer to nisu ponuđena rješenja za nepravilne mnogokute. Koliko sam uspio s mobitela vidjet…

5

Jedno je dobro a ostala su da se politely izrazimo kreativna (čitaj: može to bolje). I uvijek je tako.

6

1 Like
7

Mali offtopic ali da li ste se ikada zapitali koliko zaista znate? Ne neko drugi na internetu na koga vas neki od pretrazivaca uputi nego bas vi? I koliko bi ste posla uradili da nema interneta 7 dana?

Zato treba razmisljati bez neta ako je moguce.

2 Likeova
8

Slazem se. Nekad programer ili sistem admin nije isto kad danas.

9

Nekad je i programer morao znati ”samo” C.

Danas programeru traze milion stvari samo da bi mu dali sansu za intervju.

Svi Googlaju, i dobri i oni manje dobri programeri, i nema nista lose u tome.

Svaki dan, i svaki dan shvatam da nemam pojma :slight_smile:

4 Likeova
10

Isto. To ti je ono krug znanja i povrsina neznanja koju dodiruje. Sto vise znas, shvatas koliko si zapravo šupalj.

11

Upravo ste na tragu rješenja zadatka: poligon znanja i poligon neznanja se nikad ne preklapaju.

12

Skor’o sam nabas’o na Google intervju pitanje namijenjeno kandidatu za Lead poziciju.
Rješenje k’o i svako je jednostavno (kad je riješeno je l’) al’ se radi o nečem s čim se nisam susret’o.

Imate li ideju ili ste već rješavali slično?

13

Pageing? … 20 znakova

14

Crawler koji praviš mora prije crawl-anja da provjeri [zasad] bilion (eng. trillion) spam linkova.
Dakle prije (svakog) crawl-anja novog linka. Osnovni uslov je da se ne crawl-a link koji se nalazi na listi.
Traži se prihvatljivo rješenje koje će moći podržati mašina od 32 GB RAM-a [koja crawl-a].

Hint: nešto se može malo i žrtvovati (i.e. accuracy) ali ni po koju cijenu se ne smije crawl-ati link sa liste.

15

malo banalizirano, možda:

Nakon prvog pretraživanja spremi se rezultat i ne pretražuje listu ukoliko se lista ne osvježi.

Lista se pretražuje 500 000 unosa at once (ne znam kako bi ovo prošlo) i ako nađe rezultat ne prretražuje dalje.

16

Pa lista je ustvari rezultat tako da svaki naredni link treba da se provjeri u odnosu na listu.

Što je 2.000.000 chunk pretraga dok bi samo jedan link potražio. 32 GB vjerovatno može i na desetine miliona da pretraži ali opet se svodi na desetine hiljada full-size pretraga.

Neka je i jedan [link u pitanju] ali akcija bi vjerovatno bila: crawler dobije listu od par stotina (vjerovatnije nekol’ko hiljada ili više) linkova koje treba crawl-ati i prije svakog crawl-anja mora se biti sigurno da se link ne nalazi u listi.

Hint: nije bitno ako se ne crawl-a link koji nije na listi ali je kritički bitno da se ne crawl-a link koji je na listi.

17

Možda su se @creatifcode ili @tony susretali s nečim sličnim? :slight_smile:

18

Razmisljam na glas :smiley:

Mozda da se grupisu nekako URL-ovi sa iste domene (tj. pretvore u jedan) npr:

something.com/1
something.com/1/xyz
something.com/x

i samim tim reduciramo velicinu liste spam URL-ova.

Ovo je sve naravno pod pretpostavkom da ih imamo na osnovu cega grupisati :smiley:

19

Mislim da se ne može uticati na listu na taj način.
Tj. smatram da je lista decidna i da se ne može proizvoljno mijenjati.
Bitna stavka je da se ne dopusti da se crowl-uju spam linkovi koji su uvršteni u listu.

Hint: Činjenica stoji da treba razmotriti/uobziriti i način smještanja bilion redova u listu.

20

Maybe https://en.wikipedia.org/wiki/Fingerprint_(computing)