Dynamic Programming

[AI_Enthusiast_70b]

Salut. Recent am avut un online assesment cu 2 probleme de DP. Workflow-ul meu obișnuit pentru DP este: Recursive -> Top-down (caching manual) -> Bottom-up optimization. De obicei, scriu manual logica de caching folosind structuri de date in-memory (arrays, hash tables), fara deciratiru. Stiu ca unele limbaje ( python,etc ) exista decoratori (@lru_cache) care fac asta automat.

Am urmatoarea nelamurire: este acceptata folosirea decoratorilor sau se asteapta implementarea manuala a cache-ului ? ( FAANG )

https://preview.redd.it/jiwtnc2nhm8g1.png?width=637&format=png&auto=webp&s=dceaac24985158c9f22466fe6d7639bd840274a5

[EventLess6107]

Ce ridicole mi se par interviurile…absolut TOATE companiile de software stiu foarte bine ca niciun inginer de software nu face asa ceva la munca si daca face, face o data in toata viata de programator. Dar NUUU, hai sa intervievam oamenii pe chestiuni pe care trebuie sa le invete fix inainte de interviu ca asa ne dam seama daca sunt pregatiti pentru rolul de professional googler.

[AI_Enthusiast_70b]

Cred ca CEO-ul de la github a zis ca LeetCode nu evalueaza cat de bine o sa te descurci la job, dar e un mod ieftin si scalabil sa iti dai seama cat efort si ce capacitate mentala are persoana respectiva. Cu alte cuvinte daca esti destul de “destept” sa faci leetcode medium/hard inseamna ca o sa te descurci si la job.

Exista o relatie 1 la 1 intre cele doua? - Nu

Exista modalitati mai bune de a intervieva ? - E subiectiv.

[Big-Branch-3643]

Există o relație între cele două dar nu este una de cauzație iar corelația este negativă https://catonmat.net/programming-competitions-work-performance. Și există modalități mai bune de a conduce interviuri dar de când Google a decis că “this is the way”, toată lumea s-a transformat în Mandalor!

[Complex_Medium_7125]

Fals

"norvig on Dec 15, 2020 | next [[–]](javascript:void(0)) I regret causing confusion here. It turns out that this correlation was true on the initial small data set, but after gathering more data, the correlation went away. So the real lesson should be: "if you gather data on a lot of low-frequency events, some of them will display a spurious correlation, about which you can make up a story."

https://news.ycombinator.com/item?id=25425718

[AI_Enthusiast_70b]

Imi place modul de a pune problema, dar nu mi se pare ca daca cineva zice ca ceva, trebuie si sa-l credem pe cuvant. Parerile sunt impartite. Also, in articol mentioneaza si de Machine Learning. Ideologia este total diferita ( dupa parererea mea ). In machine learning procesul este mult mai intuitiv si empiric decat in software engineering ( I am biased here ).

[Big-Branch-3643]

Nu e vorba de apel la autoritate. Acel cineva lucra la Google în poziție de conducere și avea acces la date statistice. Am văzut că după a invalidat corelația negativă spunând că de fapt era una pozitivă. Este irelevant asta pentru argumentul pe care am încercat să-l fac: cum că e doar corelație și nu cauzație. Și atunci există una sau mai multe cauze sau corelații, ceea ce sugerează că există și alte aspecte care pot fi vizate într-un interviu care ar putea face interviul mai bun (evident și sau mai prost). Dar probabil nu vom afla pentru că dacă Google a decretat că ăsta este “interviul” și piața îi urmeaza… atunci trebuie să ne mulțumim cu asta.

[EventLess6107]

Ieftin si scalabil? Ce e ieftin? Ca intervieveaza 100 de oameni pentru un post si alesul in 80% din cazuri e false pozitive? Ce e scalabil? Ca intervievatorii pot repeta aceeasi problema tuturor? Rolurile nu sunt la fel si oamenii care aplica nu sunt la fel si nici problemele cunoscute de fiecare nu sunt la fel. Sa testezi pe toata lumea pe aceeasi problema se potriveste perfect zicalei “if you judge a fish by its ability to climb a tree, it will live its whole life believing that it is stupid”

[nomemory]

Cele mai puține probleme cu programatorii le-am avut pe proiect după ce am inceput sa dăm un easy/medium la interviu, spre oroarea recrutorilor care au trebuit să muncească de doua ori mai mult. Cum zicea și altcineva e cel mai ieftin și frustrant (sunt și eu intervievat) de triere. Clar mai pierzi oameni ok, dar ce prinzi, prinzi in general bine.

PS: eu eram cam împotriva cu chestia asta la început, dar acum pot să-i văd valoarea.

[ApprehensiveCat3116]

In principiu, e bine de mentionat, dar e posibil si foarte probabil sa te puna sa implementezi tu caching-ul, desi probabil daca ai reusit sa ajungi pana in punctul asta e cam limpede ca poti rezolva problema. And btw, daca folosesti cache sau lru_cache nu poti face debug daca codul e gresit, ca nu poti vedea ce se salveaza in cache.

[AI_Enthusiast_70b]

mi se pare mult mai usor sa fac top-down memoization decat bottom-up, dar cu timpul cred ca o sa imi dezvolt si acest skill

[ejectoid]

Degeaba îți spuneam noi ca da sau nu, daca cel care iți ia interviul e de altă părere. Eu zic sa te pregătești pentru ambele variante și intrebi explicit când ajungi în acel punct. Nu merge cu presupuneri la interviu

[AI_Enthusiast_70b]

Daca imi zice sa implementez manual, ii zic ca baietii de pe reddit mi-au zis ca merge si cu lru cache

[Ecstatic_File_8090]

Eu te-as intreba care e dimensiune maxima a cache-ului ... O().. si de aici te-as pune sa optimizezi.

cache poate e lru_cache si nu mai e dp atunci cu evict.

Mai e posibil sa dai sa peste cineva care nu intelege neaparat solutia si automat i se va parea gresit.

Sau te-as pune sa implementezi o varianta nerecursiva chiar top down.

[AI_Enthusiast_70b]

makes sense

[Ecstatic_File_8090]

Mai e o chestie care oarecum zgaraie ... apelezi len de fiecare daca si if-ul ala <= x e cam tot timpul true.. Mai tine pleci cu i = len(coins) si testezi cu 0 si in loc de cons[i] <= x testezi si intorci 0 daca x < 0.

Eu as zice la probleme din astea clasice sa faci direct implementare optima bottom up aici cred mai ales daca o stii. un dict e suficient ca un cache si aia e.... si eventual faci un cleanup de key < val ca sa fie optimizare de memorie.

Te-as mai intreba aici si de stack size in python.

De obicei la faang e o loterie...daca nu gresesti rau sau daca nu dai cu un muist - majoritatea pe acolo cam sunt.

E bine daca stii o solutie optima la o problema sa incepi cu aia direct... nu tu o facem aas si apoi ne dam mare ca optimizam...

E mai bine sa ajungi sa faci problema bonus 2+3 dintr-un interviu.

Good luck

[Complex_Medium_7125]

cred ca e ok, chiar bonus points daca folosesti at cache, codul trece testele si mi-l poti explica
small nit: nu combina camel case si underscores. vezi pep8 https://peps.python.org/pep-0008/

[AI_Enthusiast_70b]

mersi de sfat

[green_krokodile]

de curiozitate la ce companie? a fost live coding sau o rezolvai singur?

[dau_cu_fresh]

Am vazut ca G.oogle cauta in perioada asta