Top 6 API Architecture Styles (repost)

 

Articol disponibil AICI

Training Java performance - Ziua 3 (microservicii)

NFR = non functional requirements

reteaua Google - sa nu depinda de alte cabluri; 6 x 9 availability pt Google Login

Sistem neperformant:
Throttling: ex. rate limiting
Queuing
Auto-scaling

Startup time: rau pe Java > mai rau Spring > si mai rau EJB

Conexiune persistenta Browser-BE: websocket/grpc/http2; pt multe request-uri/zi de la putini useri

Disintegrator - spargere cod mare in bucati mici
avantaje: decuplare, refolosire, izolare bug, versiune java la zi (CVE, Spring), testabil mai usor (pe bucati), scaleaza independent, deploy independent (faster cycle time)

Spring AI, Spring MCP

Integrator: motive sa nu spargi codul
latenta, cuplare stransa, microserviciile sunt scumpe; consistenta datelor (ACID in loc de eventual consistency)

https://www.infoq.com/news/2023/03/stop-cloud-zombies-qcon/

enum in Dtos pt REST compatibility: cand modifici/scoti din enum strici; daca faci rename pe un camp din Dto; camp din required in optional;

test care verifica ca nu ai facut breaking change pe contract;

subjson in json "metadata" pt alte adaugiri

Clientii v1 identificati prin header-ele Authorization, X-Api-Key, X-Client-Id, Traceparent (incl timp)

OpenTelemetry Java Agent- pus in JVM pt tracing (userv)

swagger-ts-generator

isaqb.org - certificare arhitect

Get id repetat - eroare 429 Too Many Requests -> use batch API

Request multiplexing - astepti sa vina mai multe req, le pui in asteptare (sincron) ~ batching

Netflix: grpc + graphQL

CQRS - segregare responsabilitati command / query

POST/PUT return data?

Caz RM creare programare in 2 pasi -> ret. patientId -> GET alte patientId -> afli date despre alti pacienti

202 Accepted (dupa validare request)
200 OK [Retry-after] - prea lung, nu e gata, dar totul e ok, ruleaza async; clientul face polling
200 OK {status: DONE}
302 Redirect - pt rezultate mari

SAU: serverul creeaza un topic la care clientul se aboneaza

SAU: clientul primeste un HTTP callback (webhook) pe care sa faca polling

SAU: websocket

Agregator - face batching

Proxy - ruteaza orbeste
API proxy - la intrare in system
Service proxy - la iesire, spre API externe

Gateway: caching, compresie date, rutare requests, load balancing, service registry, http access log, metrici, tracing,
agrega date din mai multe API-uri == NOK ca implica business logic in Gw
autentifica request-uri (cu ajutorul unui serviciu), fara autorizare
rate limiting

Connect timeout < Response timeout -- trebuie setate, altfel infinite

Lock.tryLock(timeout)

Eroare 500 + header Retry-After - daca e din cauza unui serviciu extern (nu 500 propriu-zis)

resilience4j

health probe: aliveness & readiness (capabil de trafic)
unalive: conexiuni agatate permanent, disc corupt, OOME, deadlock

LB poate evita o instanta daca e slow/are erori.

Inbox table = store then process
Outbox table pattern = store and fwd
- pune mesajul in SQL cu un status, apoi luat si trimis extern, actualizat status

Operatii idempotente = retryable: GET, DELETE, PUT (overwrite)

POST: idempotent daca la retry trimite acelasi idempotency key (poate fi timestamp la ms); sau serverul sa tina un hash(comanda), salvat intr-un map cu comenzile din ultimele 30 minute -> daca primeste aceeasi comanda va face reject

PUT cu IK (UUID)

server.tomcat.max-connections
server.tomcat.accept-count
server.tomcat.threads.max

Bulkhead = apeluri simultane per JVM
Rate limiter = apeluri intr-un interval de timp
Quartz - orchestrare timers prin DB

Compartimentalizare -> izolare serviciu picat

Cache - for latency or for data replication

App de baza are un SLA (99.99) -> e ok sa chemi alt API cu SLA mai mare (99.999)

Istio: construieste un mic scut in jurul unui serviciu (throttling etc - il face ca un gateway)

Strategii de deployment: canary (ex. FB release in Argentina), blue/green (gradually transfer traffic), deploy in staging pt testeri si clienti timp de _;

release notes, feature flags

shadow deploy=rutezi input din prod si verifici ca da la fel, in paralel cu versiunea veche

Ex. connection pool starvation:

@Transactional
method() {
  synchronized(b) {
  // call a slow api
  }
}

Cache miss 99%: e prea mic, a expirat, nu este gasita cheia (lipseste hashCode, equals in clasa cheii)
Teste pe cache!! --> AgencyCacheTest
Cache hit prea mare: key collision? (chei trunchiate, sunt mereu gasite)

@TimeAspect
@Timed
MeterRegistry - raporteaza metrici

@Observed

Monolit (risc: cod complex) -> microservicii (risc: integrarile)
=>
Mockito -> WireMock (care nu reflecta realitatea din prod)
Monolit: multe unit teste; uS: multe teste de integrare
uS: mai multe bug-uri in yaml config decat in cod

@FeignClient - pt apel rest dintr-un uS la altul

Jeff Bezos manifesto for externalization (2002)

ZoomIt- timer (gong)

Surse:
video: https://www.youtube.com/watch?v=arUOVFUKt6s
drive: https://drive.google.com/open?id=1A2WIOb6tZvkzkHwDEAQSfFCKQAIG4imt&usp=drive_fs
https://victorrentea.ro/slides/

Training Java performance - Ziua 2 (JPA)

 SOLR/ES/Lucene - full text search

Vector search - next thing

Brian: paginare N rezultate, apoi N/2 , N/4 ... dar intr-o singura tranzactie

Query-uri dinamice:

1. concat string-uri: WHERE 1+1" (ca apoi sa poti concatena alte conditii, if criteria)

2. Query DieSL: JpaQuery

- Diesel genereaza entitatile (ex. QMaterial)

3. CriteriaAPI

Planul de executie uraste "OR"

- face cache la planul construit anterior

- query diferit: alt plan

Index: ideal e sa ai distributie buna pe date (nu prea multe valori repetitive)

AskTom - (Oracle) - intrebari tuning etc

@Id

@GeneratedValue(strategy = _ )

- SEQUENCE: trebuie creata; la rollback tranzactie nu se poate recupera (da impresia ca e un rand sters in table)

INCREMENT BY 50: tragi din baza 50 id-uri odata

- IDENTITY = auto-increment; ceri de fiecare data din baza

- PK violation daca inserezi id-uri 'cunoscute'

- UUID - greu de ghicit, poate fi generat de client; dar urat

- TABLE

@Embedded pe un obiect din entity -> muti anumite attribute din clasa (coloane) pt a-i scurta marimea

@Entity to Domain Model - vezi notele

@Transactional pe metoda - nu poti face face try/catch pe query

- interzise tranzactiile manuale

Write behind: JPA amana scrierile pana inainte de commit (flush)- pt a insera/update in batch-uri

em.flush() - grabeste flush, dar nu comite; crapa de la erori

+ un select ar putea grabi flush

Carte: "Release it!"

Entitate gasita cu find pe o metoda @Transactional:

.set...() face update (auto-save)

alt .set nu face / nu se mai potriveste equals

em.detach(obj); // scoate din urmarire

em.clear(); // elimina din context toate entitatile (detach la tot), goleste 1st level cache al lui Hibernate

flush vs clear:

- flush scrie tot ce avea de scris; util: inainte sa chemi un PL/SQL, Trigger sau native query.

- goleste fara sa scrie nimic

@DynamicUpdate - modifica coloana din entitate doar daca chiar se modifica

1st level cache = transaction-scoped; find se uita in cache

2nd level cache = intre request-uri diferite (optional @Cacheble pe @Entity sau query hint)

- util: primul select ia din baza, al doilea select identic intr-un TTL=5 min ia din cache

Persistence context

@Cache pe entity class

em.merge(entity); // update fara auto-save, fara @Transactional, cand construiesti cu new entitatea Venita de la client (nu mai faci find)

Merge = suprascriere entitate veche

select parinte, copii si apoi update

cascade

- DETACH ~ detaseaza copiii odata cu parintele

- REFRESH ~ git reset

- MERGE - copiii se ins/upd/del

@Transactional cand doar citesti din BD: lazy init (entitatile-copii ca lista nu sunt dispo pt un framework gen Jackson)

@OneToMany(cascade = ALL, fetch = EAGER, orphanRemoval = true)

entitate parent.getChildren().remove(1) => UPDATE copil set parent null => cu orphanRemoval omoara copiii cu FK = null

( valabil la em.merge )

Cand un camp nu trebuie sa fie modificat pe un flux (ajuta cu merge side effects):

1) @Column(updatable = false) String createdBy; // eroare daca incerci sa modifici din cod

2) setCreatedBy - ignora/arunca eroare daca e deja setat campul

3) suprascrii cu valoarea care era initial in baza

Concurenta la modificare entitate:

Optimistic lock: te lasa sa scrii, cand salvezi iti da eroare daca cineva a salvat inaintea ta

@Version

private Long version; // sau LocalDateTime

// la em.merge(entity) se adauga o conditie suplimentara: AND version = 1 (cat era pe entity)

Pessimistic lock: pus lock in baza = intarzie a doua tranzactie pana comite prima

cu row lock: SELECT ... where version=7 FOR UPDATE [NO WAIT - la nivel de rand]

- face lock pe randurile returnate de SELECT

tx2 va astepta pana tx1 comite; = default in postgres/H2

adaugare coloane IN_EDIT_BY, IN_EDIT_SINCE cand materialul incepe sa fie editat de un user (lock pe linia din tabel)

Nu folosim synchronized in EJB

Monitorizare "connection acquisition time" = metrici - Grafana, Kibana, New Relic

@Transactional:

persist, flush nu duc la commitment daca apare exceptie in metoda tranzactata

- orice metoda chemata in thread-ul curent e parte din aceeasi tranzactie

- thread async: NU, si acopera exceptia; pt ca se pierde conexiunea JDBC care avea tranzactia pornita; nu merge nici daca pasezi EntityManager-ul de pe thread-ul gazda

Metoda @Transactional care cheama alta metoda @Transactional = e aceeasi tranzactie (parinte)

Propagation.REQUIRES_NEW ca sa fie distincta

TxType.REQUIRED = este default

throw checked exception intr-o metoda @Transactional nu impiedica commit-ul, doar unchecked (runtime) impiedica (!!!)

=> metoda @Transactional nu se recomanda cu throws! - faci try/catch/throw RuntimeException

@Transactional cu Propagation.REQUIRES_NEW pe o metoda-copil din acelasi serviciu = ca si cum nu are @Transactional

! nu se da API-call din @Transactional

Deadlock:

synchronized(x) din java + SELECT FOR UPDATE id=7 in parallel cu 

SELECT FOR UPDATE id=7 + synchronized(x) din java

View materializat pe disc si actualizat periodic;

Rainbow brackets- plugin IntelliJ

DbUnit 

Tuning tips:

- EXISTS (SELECT...) in loc de SELECT COUNT() sau id=(SELECT id...)

- Evita SELECT DISTINCT pe mai multe coloane = multe comparatii

- WHERE in loc de HAVING

- INNER JOIN ON <cond> in loc de WHERE<cond>

- LIMIT

- UNION ALL nu UNION (=DISTINCT)

- A UNION B in loc de WHERE... OR..

- GROUP BY in loc de OVER PARTITION BY

- tabele auxiliare

- IN si = in loc de != si <> si NOT IN

Training Java performance - Ziua 1 (JPA)

Hibernate - performanta down, magie

Orice @Entity trebuie sa aiba @Id (Integer, Long sau String - cheie naturala, ideal)

@OneToMany(mappedBy="numele companiei in cealalta clasa")

@Inheritance(strategy=TABLE_PER_CLASS, SINGLE_TABLE, JOINED)

Exemplu: 2 tabele Pisica/miaunat & Caine/latrat
SINGLE_TABLE: simplu, unele coloane sunt degeaba, nu poti pune NOT NULL pe coloanele specific; se foloseste daca dif dintre clase sunt minime; @DiscriminatorValue & @DiscriminatorColumn
TABLE_PER_CLASS (2 tabele): nu poti face select pe Animal; faci UNION (scump)
JOINED (3 tabele): join la orice query (ca sa incluzi si Animal) ---> nu se foloseste in practica

PARTITION BY - sparge datele in datafile separate (dupa an sau luna de obicei);
se face dupa cum vei face cautarea
daca cauti dupa altceva, merge rau
- nu ocupa spatiu in plus, precum indecsii

INDEX e ceva complementar (~ hashMap); prea multi afecteaza performanta

Employee si EmployeeDetails - pot avea shared primary key (FK al lui Details sa fie si PK)
- datele masive pot fi tinute in alt loc daca nu sunt frecventate des

Evitare referinte reciproce Employee si EmployeeDetails - depinde de caz - daca selectezi details si vrei si employee-ul initial, pui
altfel @OneToOne pt details, in Employee; daca modifici unul poti uita de celalalt

@ManyToMany
@JoinTable

@Enumerated - cand campul este un enum

ProjectType { LIB("L") } - in db ajunge "L", nu 0 sau LIB

XML/JSON - salvat ca CLOB (character large object)
- editare xml din clob risca stricaciuni
- poti selecta bucati din XML cu instr speciale Oracle
- poate fi prea mare, ocupa discul -- OOME (out of memory error)
Trebuie citit/scris in BD via fisier (cu InputStream/OutputStream)
Best practice: nu incarcat in BD, ci arhivat si salvat pe disc (ftp sau pe acelasi disc), cu referinta in BD;

like pe coloana CLOB: dureaza f mult pt ca CLOB nu e indexabil

https://github.com/victorrentea/jpa/tree/systematic25
run StartDatabase, JpaApplication
JpaPlayground - cu Lombok
fol. EntityManager in loc de Repository (EE)
em.persist(new Teacher());

@Transactional in Spring & Jakarta

Creare 2 entitati inrudite: trebuie legate both-way - daca uiti?
Relatiile bidirectionale sunt greu de intretinut.

Design mai bun: getter sa fie unmodifiable - blochezi get/add; faci o metoda de add in care legi dublu;
in cealalta clasa setter-ul e de tip default (nivel de package) - sa nu poti accesa set din afara pachetului

@OneToOne (cascade = CascadeType.ALL)
- TeacherDetails nu are ref la Teacher

CascadeType.ALL intre parinte si copiii exclusivi ai lui (creare, stergere automata)

campuri List vs Set
- ordonare cu @OrderBy("type ASC, value desc") pt List, sortare din query JPA
@OrderColumn(name = "INDEX") - salveaza in DB ordinea manual setata de user in UI
altfel ordinea nu e garantata

hashCode/equals pe:
- id?
- campuri?
- id + campuri? - situatie campuri identice si unul are id=null; ambele circula
=> nu impl hashCode/equals pe entitati, facem propriul equals; mai tricky la HashSet

@NotNull - previne sa inserezi prin java (Jakarta validation la persist)
nullable = false - previne sa inserezi "pe sub mana" -- folosit in POC, nu in proiecte mature (nu creezi DB din java); pot ramane out of sync

@AssertTrue pe metoda ~ @NotNull cand validarea e doar pe campul unui copil

@OneToMany poate fi def unidirectional, cu @JoinColumn(name = "loanerId")

constructor in entity:
protected cu constructor gol - ca sa nu planga Hibernate
public cu parametri - este cel relevant

getter/setters: nu neaparat necesare, Hibernate foloseste reflectie pt a popula campurile

--> BalanceEntityListener ??
--> @Transient in BalanceEntity?

http://annas-archive.org/ -- book "sql performance explained"

URL BD: jdbc:mssql ----> jdbc:p6spy:mssql , cu username, parola, dependency la p6spy
-> alternativa mai buna la show-sql=true

@OneToMany
N+1 queries = 1 pt parinte, N pt copii (loading lazy info)
fetch = FetchType.LAZY by default (doar pe colectii); la fel si pt @ManyToMany
EAGER daca eviti N+1 queries -> incarca tot dinainte - a nu se folosi aproape niciodata
@BatchSize(size=20) - este Hibernate specific - incarca entitati inrudite in calupuri

Ia toate info odata (pt @ManyToOne)
select p from Person p
LEFT JOIN FETCH p.children
LEFT JOIN FETCH p.country ---- nu este colectie

@ManyToOne - si asta aduce N+1 queries

fetch = EAGER by default

entityManager.createQuery("SELECT pFROM errorProne"); // app porneste, vezi bug-ul tarziu
@NamedQuery (name = "", query = "") ; // detecteaza devreme, nu compileaza

Sub-select: select doar anumite campuri
@Subselect("query...")
public record.... - in spring

@NamedNativeQuery - pt EE
(query= "", resultClass = , resultSetMapping = )
- cu COALESCE
- to VIEW ----> declari un nou @Entity in Java cu @Table("VIEW_NAME")

Teste pe query-uri

FetchGraph - sa incarci partial entitati

Paginare: ORDER BY, LIMIT __, OFFSET __
- in BD, in Java sau pe client

Problema: daca se insereaza/sterge in timpul frunzaririi (cached)
problema: el face select tot dar iti da numai ce ceri
Nu poti pagina in DB daca faci FETCH, pt ca se strica cardinalitatea
pe doua directii: iese produs cartezian

LEFT JOIN FETCH ALL PROPERTIES - ia in cascada

@ManyToOne private Country country; ==> private Long countryId; // pastreaza FK
-> pune numeric/string ref in loc de object reference

entityManager
.createNamedQuery(..)
.setFirstResult(0) // offset
.setMaxResults(2) // limit
.getResultList();

@ElementCollection -- entitati-copii fara id

Cross join: N x N x N results

Intrerupere query in timpul rularii - exista api de jdbc "abort" - nu din JPA, doar JDBC (statement.cancel())
sau: timeout in JPA

Jupiter Parameterized Test

import io.grpc.Status;
import io.grpc.StatusRuntimeException;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

public class ServerStreamingInputValidationTest extends AbstractTest {

    @ParameterizedTest
    @MethodSource("testData")
    void testBlockingInputValidation(WithdrawRequest request, Status.Code code) {
        var ex = Assertions.assertThrows(StatusRuntimeException.class, () -> this.blockingStub.withdraw(request).hasNext());
        Assertions.assertEquals(code, ex.getStatus().getCode());
    }

    @ParameterizedTest
    @MethodSource("testData")
    void testAsyncInputValidation(WithdrawRequest request, Status.Code code) {
        var observer = new ResponseObserver<Money>();
        this.asyncStub.withdraw(request, observer);
        observer.await();

        Assertions.assertTrue(observer.getItems().isEmpty());
        Assertions.assertNotNull(observer.getThrowable());
        Assertions.assertEquals(code, ((StatusRuntimeException) observer.getThrowable()).getStatus().getCode());
    }

    private Stream<Arguments> testData() {
        return Stream.of(
                // input, expectation
                Arguments.of(WithdrawRequest.newBuilder().setAccountNumber(11).setAmount(10).build(), Status.Code.INVALID_ARGUMENT),
                Arguments.of(WithdrawRequest.newBuilder().setAccountNumber(1).setAmount(17).build(), Status.Code.INVALID_ARGUMENT),
                Arguments.of(WithdrawRequest.newBuilder().setAccountNumber(1).setAmount(120).build(), Status.Code.FAILED_PRECONDITION)
        );
    }
}

Kill process in Windows & Linux

Windows:

> netstat -ano | findstr :8080

> taskkill PID <pid> /F

Linux:

> sudo lsof -i 8080

> sudo kill -9 <pid>

Proto vs Json performance test

 

public class PerformanceTest {
    private static final Logger LOGGER = LoggerFactory.getLogger(PerformanceTest.class);
    private static final ObjectMapper MAPPER = new ObjectMapper();

    public static void main(String[] args) throws Exception {
        var protoPerson = Person.newBuilder()
                .setLastName("T")
                .setAge(32)
                .setEmail("t@email.com")
                .setEmployed(true)
                .setSalary(123004.5)
                .setBankAccountNumber(38495959093040944L)
                .setBalance(-100)
                .build();
        LOGGER.info("how many bytes protoPerson has? {}", protoPerson.toByteArray().length); // 41

        var jsonPerson = new JsonPerson("T", 32, "t@email.com", true, 123004.5, 38495959093040944L, -100);
        var bytes = MAPPER.writeValueAsBytes(jsonPerson);
        LOGGER.info("how many bytes jsonPerson has? {}", bytes.length); // 130 = 3x more!

        for (int i=0; i<5; i++) { // first run to be ignored (warmup JVM)
            runTest("json", () -> json(jsonPerson));
            runTest("proto", () -> proto(protoPerson));  // 7x faster!
        }
    }

    private static void runTest(String testName, Runnable runnable) {
        var start = System.currentTimeMillis();
        for (int i=0; i<5_000_000; i++) {
            runnable.run();
        }
        var end = System.currentTimeMillis();
        LOGGER.info("time taken for {} = {} ms", testName, (end - start));
    }

    private static void proto(Person person)  {
        try {
            var bytes = person.toByteArray();
            Person.parseFrom(bytes);
        } catch (InvalidProtocolBufferException e) {
            throw new RuntimeException(e);
        }
    }

    private static void json(JsonPerson person) {
        try {
            var bytes = MAPPER.writeValueAsBytes(person);
            MAPPER.readValue(bytes, JsonPerson.class);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

Implementarea unui Rate Limiter

public class RateLimiter {
    private static final int ONE_SECOND = 1000;
    private final Map<String, List<Long>> requests;
    private boolean enabled = false;
    private int requestsPerSecond;

    public RateLimiter(Environment environment) {
        requests = new HashMap<>();
        if (environment.getProperty("enable.rate.limiter") != null) {
            this.enabled = Boolean.parseBoolean(environment.getProperty("enable.rate.limiter"));
        }
        if (this.enabled) {
            String property = environment.getProperty("max.requests.per.user.per.second");
            Assert.notNull(property, "Max requests per second not defined!");
            this.requestsPerSecond = Integer.parseInt(property);
        }
    }

    public boolean allows(String ipAddress) {
        if (!enabled) {
            return true;
        }

        if (!requests.containsKey(ipAddress)) {
            requests.put(ipAddress, new ArrayList<>());
        }

        Long now = System.currentTimeMillis();
        cleanup(ipAddress, now);
        requests.get(ipAddress).add(now);

        return requests.get(ipAddress).size() <= requestsPerSecond;
    }

    private void cleanup(String ipAddress, Long now) {
        List<Long> markedForDeletion = new ArrayList<>();
        for (Long timestamp : requests.get(ipAddress)) {
            if (now - timestamp > ONE_SECOND) {
                markedForDeletion.add(timestamp);
            }
        }
        requests.get(ipAddress).removeAll(markedForDeletion);
    }
}

Din interviurile anului 2024 si o experienta de munca mai putin fericita

--- Experienta NTT Data ---

M-a abordat pe LinkedIn o doamna draguta din Brasov, foarte vorbareata si dezghetata. Nu imi doream neaparat sa lucrez pentru o companie de consultanta, dar cumva m-a convins ca sediul era mai aproape de casa (si mare avantaj ca nu era lipit de Pipera), dar si ca aveau sedii in mai multe orase din tara, unde as fi putut oricand sa vin sa lucrez, chiar si in Serbia, unde aveau piscina. Am terminat interviul tehnic, am fost evaluata, urma sa fiu incadrata intr-unul din proiectele lor, dar doamna draguta mai avea nevoie de cateva detalii (era in plina activitate intelectuala, ma suna inopinat, se vedea ca muncea din greu sa faca lucrurile sa mearga pentru mine). Mi-a trimis o grila de completat cu informatii ceva mai mult decat se gaseau in CV, cu mentiunea ca trebuie AZI, cat mai REPEDE, NEAPARAT. Mi-am rupt din timp ca sa scriu cat mai multe detalii de care imi aduceam aminte, sa fie totul la timp, sa avem sansa la discutie cu clientul. Apoi? GHOSTING

Morala: ???

--- Experienta Spirent ---

Spirent a poposit in casuta mea postala de pe LinkedIn printr-o angajata a TechTalent. Planul era ca Spirent nu angajeaza oamenii direct asa, ci ca ii trece printr-un an de proba la TechTalent, cu aceleasi beneficii si conditii. Dupa discutia de la telefon cu HR, primesc un test pe email - o implementare. Accept cu bucurie, fiind un mod diferit de a desfasura un interviu, fara presiunea de a fi fata in fata si de a da raspunsurile rapid. Am stabilit ca termen o saptamana. Am lucrat in ritmul meu, dar vream sa mai cer o zi de gratie. HR-ul m-a zorit ca trebuie azi, ca sunt si altii, ca altii au trimis deja in doua zile. Incerc sa termin cat mai repede si sa trimit tema, ca sa raman in grafice. In cele din urma trimit repede si astept  programarea urmatorului interviu, si astept. Mi se comunica ca pozitia respectiva a fost inchisa, ei gasind intre timp pe cineva, dar mai exista o pozitie asemanatoare, pentru care se cere acelasi test, cu inca o cerinta adaugata ( come on, inca putin, esti practic deja acolo ) - dezvoltarea unui plugin de Eclipse. Nu mai facusem asta inainte, ma gandeam poate sa invat, dar ca cineva care lucreaza in IntelliJ lasand de mult in urma Eclipse, mi s-a parut a fi ca o intoarcere in timp. Si aici m-am oprit.

Morala: fusesem un backup de la inceput, ei cautau pe cineva care dezvolta plugin-uri Eclipse.

--- Experienta Thales ---

Thales a poposit in casuta mea postala de pe LinkedIn propunand un rol in industria aeriana cu ultimele tehnologii de Cloud. Cand i-am intrebat daca este o problema ca n-am mai lucrat cu unele dintre ele pana acum, mi s-a raspuns: nicio problema. Foarte bine, am acceptat un scurt apel telefonic cu un HR, i-am trimis CV-ul si am fost de acord sa merg mai departe cu interviul tehnic. A doua zi, mi se comunica faptul ca pozitia a fost inchisa, dar exista o pozitie similara pentru care as putea fi potrivita si primesc un JD pe email. M-am holbat de cateva ori si am cerut un alt JD mai detaliat. HR-ul mi-a transmis imediat varianta actualizata (o avea la indemana), dar nici de data asta n-am putut sa ma lamuresc: ce tehnologii sunt folosite? Ca sa ma lamuresc pe deplin, accept un interviu tehnic. La interviu au loc cateva prezentari, despre Thales si despre divizie, dupa care managerul vrea sa treaca la intrebarile pentru mine. Il opresc sa intreb cate ceva despre ce ma apasa, tehnologiile folosite. Plain Java, nimic special. Spring Framework, dar nu Boot. Aflu ca proiectul are si o componenta importanta de UI, dar managerul nu mentioneaza cu ce este realizata. Intreb explicit: ce tehnologii folositi pentru partea de UI? Raspunsul, atat de mult evitat, este: JAVA SWING. Ok, suntem deja in interviu, hai sa-l terminam. Inca o intrebare, ce baza de date folositi? Trebuia sa ii scot informatiile cu clestele din gura. SQL, nimic special. Vag. Trecem la intrebarile pentru mine, cate ceva despre biografia mea, cate ceva despre comportamentul meu ipotetic. Managerul are grija de cateva ori sa ma tachineze cu America: oare nu imi pare rau ca n-am ramas acolo? Oare ce as fi facut acum? Dar oare care e cea mai mare realizare a carierei mele? Dar oare unde vreau sa ajung cu programarea, ar avea sens sa programez cot la cot cu proaspat absolventi chiar si la 50 ani? Si astfel de intrebari care ii framantau mult in universul lor inchis :-) ne luam la revedere si sa aiba succes cu Java Swing.

Morala: m-au atras cu o pozitie smechera ca sa aiba candidati la o pozitie neatragatoare. Au mintit prin omisiune in JD, au continuat sa ascunda si la interviu lucruri importante. Au lasat impresia de pierde-vara putin frustrati, dar in cautare de seniori seriosi care sa puna lucrurile pe roate. N-am idee ce se intampla in proiectul ala, dar Thales nu imi mai suna la fel de bine ca inainte. Iar faptul ca lucreaza cu francezi... nu suna incurajator.

--- Experienta reala de munca @ SII / Allianz-Trade ---

Una dintre fetele de la compania de fete si femei SII m-a abordat pe LinkedIn cu o pozitie pentru clientul lor, Allianz-Trade (fostul Euler Hermes). Nu am luat anuntul foarte in serios si am tratat oportunitatea ca pe un interviu de proba, adica de incalzire. La interviu, am cunoscut TL-ul de la Allianz care mi-a pus cateva intrebari scolaresti despre Java (el cauta un senior), la care am raspuns mai mult sau mai putin bine (nici el nu stia sigur daca e bine). La al doilea interviu, intra viitorul manager de la SII, un pusti care era pe langa cu subiectul, impreuna cu managerul de la Allianz, fara camera pornita, care a inceput sa turuie despre business. Chiar explica pe inteles si eram uimita de generozitatea sa, dar si un pic plictisita, nu ma interesa cata vreme interviul era de proba. Ca sa fiu draguta, m-am aratat entuziasmata la final. Cred ca asta mi-a adus, surprinzator, oferta. La momentul ofertei nu mai tineam bine minte ce presupunea jobul, dar sigur nu presupunea dezvoltare, ceea ce era regretabil. Totusi, fiind singura oferta pe masa si cu salariu bun, am acceptat. 

Nu mi-a placut nimic de la inceput pana la sfarsit. La SII totul era fake si nu intelegeam ce rost are SII cand aveam sa lucrez 100% la Allianz. Pe masura ce treceau zilele si saptamanile, primeam mesaje din senin pe Whatsapp in care diferite fete din SII ma intrebau ce mai faci, cum esti, cum esti tu pe proiect. "Pe proiect" este efectiv sintagma lor preferata la care am devenit, intre timp, alergica.

La Allianz nu am avut nimic de lucru timp de aproape 2 luni. Era si perioada de concedii in care sefii francezi plecau cu saptamanile si lunile si nu exista volum de munca. Intr-adevar, proiectul nu presupunea dezvoltare, aia se facea in Franta. La noi se trimiteau bug-urile si se faceau configurarile, in mare parte manuale. O mai dadeau ei ca ar trebui sa scriem si noi cod, dar nu aveai ce sa scrii mai mult decat niste utilitare care sa mai reduca putin din munca manuala.

Initial m-au plasat intr-o echipa in care aveam "sa invat". Cumva, colegii mei aveau de lucru (doar eu nu) si tot ce puteam sa fac e sa le cer sa ne uitam impreuna din cand in cand. In zilele cand lucram de acasa acest lucru era mai incomod, asa ca bagam mainile in buzunar cand nu existau task-uri care mi se adresau direct si faceam altceva. Ulterior, am inceput sa fac acelasi lucru si la birou, unde era extrem de plictisitor. Citeam articole pe Medium, stirile, sau scriam scripturi care nu foloseau la nimic. Nu a existat training, nu au existat tichete in afara de: file reupload (muuuulte, banale si plictisitoare, terminate rapid) sau endorsement config (cateva, dar nedemne pentru un senior). La file reupload, faceam copy-paste si executam cateva comenzi de Git, iar la endorsement config faceam un copy paste mai generos, modificam cateva campuri cu ceva mai multa atentie si comparam cu alte fisiere de config in vederea consistentei. Apoi aceleasi comenzi de git. Chiar daca ma bucuram mult sa fac ceva mai exciting decat file reupload, acele tichete erau putine. Iar alte tipuri de tichete, mai complexe, reveneau colegilor. Unii dintre ei (tot consultanti SII) uneori imi promiteau ca o sa lucram impreuna, dar lucrau singuri. Altii ma amanau. In teorie, oricine era disponibil pentru intrebari, dar in practica deranjam.

La doua luni de la angajare am fost pusa in echipa in care fusesem destinata de la inceput. A inceput sa ploua cu bug-uri, m-am speriat. Am cerut ajutor. Am rezolvat cum am putut. Am gresit. Am reparat. Ploua cu bug-uri tot mai mult. Dupa o saptamana, primesc veste de la SII ca mi-au terminat contractul. Din partea Allianz nicio discutie, nicio avertizare. Explicatia oficiala: nu corespunde nivelul de senioritate. Neoficial: taieri de buget si o experienta a lor anterioara cu un baiat care s-a chinuit 5 luni la ei in aceeasi echipa. Nu voiau sa se intample din nou; dar nici ca faceau mai bine.

Morala: au tratat angajatul fix ca o resursa intr-un fisier Excel, netransparenta totala prin comunicarea deciziei doar firmei de consultanta, neimplicare in a face training-uri, neintroducere de la inceput in echipa corecta, lipsa existentei unui plan de imbarcare transparent si agreat de ambele parti.

Test de integrare pt Kafka Consumer

@EmbeddedKafka
@SpringBootTest(properties = "spring.kafka.consumer.bootstrap-servers=${spring.embedded.kafka.brokers}")
public class ProductCreatedEventHandlerTest {
    @MockBean
    ProcessedEventRepository processedEventRepository;

    @Autowired
    KafkaTemplate<String, Object> kafkaTemplate;

    @SpyBean // true object, its methods can be intercepted
    ProductCreatedEventHandler productCreatedEventHandler;

    @Test
    public void testHandle() throws Exception {
        // Arrange
        ProductCreatedEvent event = new ProductCreatedEvent(UUID.randomUUID().toString(), "iPhone SE", BigDecimal.valueOf(24.5), 12);
        ProducerRecord<String, Object> record = new ProducerRecord<>(PRODUCT_CREATED_EVT_TOPIC, event.getProductId(), event);
        String messageId = UUID.randomUUID().toString();
        record.headers().add("messageId", messageId.getBytes());
        record.headers().add(KafkaHeaders.RECEIVED_KEY, event.getProductId().getBytes());

        ProcessedEventEntity processedEventEntity = new ProcessedEventEntity();
        when(processedEventRepository.findByMessageId(any())).thenReturn(processedEventEntity);

        // Act
        kafkaTemplate.send(record).get();

        // Assert
        ArgumentCaptor<String> messageIdCaptor = ArgumentCaptor.forClass(String.class);
        ArgumentCaptor<String> messageKeyCaptor = ArgumentCaptor.forClass(String.class);
        ArgumentCaptor<ProductCreatedEvent> eventCaptor = ArgumentCaptor.forClass(ProductCreatedEvent.class);
        verify(productCreatedEventHandler, timeout(5000).times(1))
                .handle(eventCaptor.capture(), messageIdCaptor.capture(), messageKeyCaptor.capture());
        Assertions.assertEquals(messageId, messageIdCaptor.getValue());
        Assertions.assertEquals(event.getProductId(), messageKeyCaptor.getValue());
        Assertions.assertEquals(event.getProductId(), eventCaptor.getValue().getProductId());
    }
}

Test de integrare pt Kafka Producer

1. Testarea serviciului care trimite mesaje Kafka

package com.hanul.pis.ProductsMicroservice;

import com.hanul.pis.ProductsMicroservice.rest.NewProductDto;
import com.hanul.pis.ProductsMicroservice.service.ProductService;
import com.hanul.pis.core.event.ProductCreatedEvent;
import org.apache.kafka.clients.consumer.ConsumerConfig;
import org.apache.kafka.clients.consumer.ConsumerRecord;
import org.apache.kafka.common.serialization.StringDeserializer;
import org.junit.jupiter.api.*;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.core.env.Environment;
import org.springframework.kafka.core.DefaultKafkaConsumerFactory;
import org.springframework.kafka.listener.ContainerProperties;
import org.springframework.kafka.listener.KafkaMessageListenerContainer;
import org.springframework.kafka.listener.MessageListener;
import org.springframework.kafka.support.serializer.ErrorHandlingDeserializer;
import org.springframework.kafka.support.serializer.JsonDeserializer;
import org.springframework.kafka.test.EmbeddedKafkaBroker;
import org.springframework.kafka.test.context.EmbeddedKafka;
import org.springframework.kafka.test.utils.ContainerTestUtils;
import org.springframework.test.annotation.DirtiesContext;
import org.springframework.test.context.ActiveProfiles;

import java.math.BigDecimal;
import java.util.Map;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.TimeUnit;

@DirtiesContext                                 // it will corrupt the application context -> each test will start with a clean state
@TestInstance(TestInstance.Lifecycle.PER_CLASS) // one instance for all test methods, for expensive setup code
@ActiveProfiles("test")                         // look for application-test.properties
// use embedded Kafka server
@EmbeddedKafka (partitions = 3, count = 3, controlledShutdown = true)
@SpringBootTest(properties = "spring.kafka.producer.bootstrap-servers=${spring.embedded.kafka.brokers}")
public class ProductServiceImplTest {
    @Autowired
    private ProductService productService;

    @Autowired
    private EmbeddedKafkaBroker embeddedKafkaBroker;

    @Autowired
    private Environment environment;

    private KafkaMessageListenerContainer<String, ProductCreatedEvent> container;
    private BlockingQueue<ConsumerRecord<String, ProductCreatedEvent>> records = new LinkedBlockingQueue<>();

    @BeforeAll
    void setUp() {
        Map<String, Object> consumerProperties = getConsumerProperties();
        DefaultKafkaConsumerFactory<String, Object> consumerFactory = new DefaultKafkaConsumerFactory<>(consumerProperties);
        ContainerProperties containerProperties = new ContainerProperties(environment.getProperty("product-created-evt-topic-name"));
        container = new KafkaMessageListenerContainer<>(consumerFactory, containerProperties);
        container.setupMessageListener((MessageListener<String, ProductCreatedEvent>) records::add);
        container.start();
        ContainerTestUtils.waitForAssignment(container, embeddedKafkaBroker.getPartitionsPerTopic());
    }

    @AfterAll
    void tearDown() {
        container.stop();
    }

    @Test
    void testCreateProduct_validProduct_success() throws Exception {
        // Arrange
        NewProductDto newProductDto = new NewProductDto();
        newProductDto.setPrice(new BigDecimal(1200));
        newProductDto.setQuantity(10);
        newProductDto.setTitle("Philips monitor 40\"");

        // Act
        String productId = productService.createProduct(newProductDto);

        // Assert
        Assertions.assertNotNull(productId);
        ConsumerRecord<String, ProductCreatedEvent> message = records.poll(3, TimeUnit.SECONDS);
        Assertions.assertNotNull(message);
        Assertions.assertNotNull(message.key());
        ProductCreatedEvent event = message.value();
        Assertions.assertNotNull(event);
        Assertions.assertEquals(newProductDto.getTitle(), event.getTitle());
        Assertions.assertEquals(newProductDto.getPrice(), event.getPrice());
        Assertions.assertEquals(newProductDto.getQuantity(), event.getQuantity());
    }

    private Map<String, Object> getConsumerProperties() {
        // Brokers' port numbers will dynamically change during executions of this test
        // Therefore, they should be dynamically retrieved in configuration
        return Map.of(
                ConsumerConfig.BOOTSTRAP_SERVERS_CONFIG, embeddedKafkaBroker.getBrokersAsString(),
                ConsumerConfig.KEY_DESERIALIZER_CLASS_CONFIG, StringDeserializer.class,
                ConsumerConfig.VALUE_DESERIALIZER_CLASS_CONFIG, ErrorHandlingDeserializer.class,
                ErrorHandlingDeserializer.VALUE_DESERIALIZER_CLASS, JsonDeserializer.class,
                ConsumerConfig.GROUP_ID_CONFIG, environment.getProperty("spring.kafka.consumer.group-id"),
                JsonDeserializer.TRUSTED_PACKAGES, environment.getProperty("spring.kafka.consumer.properties.spring.json.trusted.packages"),
                ConsumerConfig.AUTO_OFFSET_RESET_CONFIG, environment.getProperty("spring.kafka.consumer.auto-offset-reset")
                );
    }
}

2. Testarea configurarilor - ex. ca producatorul este idempotent

package com.hanul.pis.ProductsMicroservice;

import com.hanul.pis.core.event.ProductCreatedEvent;
import org.apache.kafka.clients.producer.ProducerConfig;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.kafka.core.KafkaTemplate;
import org.springframework.kafka.core.ProducerFactory;

import java.util.Map;

@SpringBootTest
public class IdempotentProducerItTest { // it will test based on real configuration
    @Autowired
    KafkaTemplate<String, ProductCreatedEvent> kafkaTemplate;

    @Test
    void test_enabledIdempotence() {
        // Arrange
        ProducerFactory<String, ProductCreatedEvent> producerFactory = kafkaTemplate.getProducerFactory();

        // Act
        Map<String, Object> config = producerFactory.getConfigurationProperties();

        // Assert
        Assertions.assertEquals("true", config.get(ProducerConfig.ENABLE_IDEMPOTENCE_CONFIG));
        Assertions.assertTrue("all".equalsIgnoreCase((String) config.get(ProducerConfig.ACKS_CONFIG)));
        if (config.containsKey(ProducerConfig.RETRIES_CONFIG)) {
            Assertions.assertTrue(Integer.parseInt(config.get(ProducerConfig.RETRIES_CONFIG).toString()) > 0);
        }
    }
}

Grind75

#57. Insert Interval (link)

class Solution {

public int[][] insert(int[][] intervals, int[] newInterval) {

int start = newInterval[0], stop = newInterval[1];

// case: newInterval contains all intervals

if (intervals.length == 0 || start <= intervals[0][0] && stop >= intervals[intervals.length-1][1]) {

int[][] result = new int[1][2];

result[0] = newInterval;

return result;

}

int[] insertion = new int[2];

// What should insertion[0] be?

insertion[0] = start;

if (start > intervals[0][0]) {

for (int i=0; i<intervals.length; i++) {

if (start >= intervals[i][0] && start <= intervals[i][1]) {

insertion[0] = intervals[i][0];

break;

}

}

}

// What should insertion[1] be?

insertion[1] = stop;

if (stop < intervals[intervals.length-1][1]) {

for (int i=0; i<intervals.length; i++) {

if (stop >= intervals[i][0] && stop <= intervals[i][1]) {

insertion[1] = intervals[i][1];

break;

}

}

}

// Place insertion

boolean added = false;

List<Integer[]> result = new ArrayList<>();

for (int i=0; i<intervals.length; i++) {

if (insertion[0] <= intervals[i][0]) {

addToList(insertion, result);

added = true;

while (i<intervals.length && intervals[i][1] <= insertion[1]) {

i++;

}

copyRest(i, intervals, result);

break;

} else {

addToList(intervals[i], result);

}

}

if (!added) {

// add at the end

addToList(insertion, result);

}

// List to arrays

int[][] array = new int[result.size()][2];

for (int i=0; i<result.size(); i++) {

array[i][0] = result.get(i)[0];

array[i][1] = result.get(i)[1];

}

return array;

}

private void copyRest(int from, int[][] intervals, List<Integer[]> list) {

for (int i=from; i<intervals.length; i++) {

addToList(intervals[i], list);

}

}

private void addToList(int[] interval, List<Integer[]> list) {

Integer[] pair = new Integer[2];

pair[0] = interval[0];

pair[1] = interval[1];

list.add(pair);

}

}

Pt. restul LINK

Exemple Deadlock & Livelock

Deadlock

Cand doua sau mai multe fire de executie sunt blocate in asteptarea eliberarii unor resurse de care au nevoie. Solutie: how to prevent deadlock in Java.

private static void deadlock() {
    final String res1 = "Resource_1";
    final String res2 = "Resource_2";

    Thread t1 = new Thread(() -> {
        synchronized (res1) {
            System.out.println("[t1] acquired access to res1");
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            synchronized (res2) {
                System.out.println("[t1] Yay! escaped deadlock."); // not happening
            }
        }
    });
    Thread t2 = new Thread(() -> {
        synchronized (res2) {
            System.out.println("[t2] acquired access to res2");
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            synchronized (res1) {
                System.out.println("[t2] Yay! escaped deadlock.");
            }
        }
    });

    t1.start();
    t2.start();
}

Livelock

Doua sau mai multe fire de executie isi cedeaza dreptul de a rula in favoarea celorlalte astfel ajungand sa nu ruleze niciodata, iar aplicatia nu progreseaza. Solutie: schimbarea logicii.

static class Spoon {
    Diner owner;

    public Spoon (Diner firstOwner) {
        this.owner = firstOwner;
    }

    synchronized void setOwner(Diner owner) {
        this.owner = owner;
    }

    synchronized void use() {
        System.out.println(owner.name + " just ate!");
    }
}

static class Diner {
    String name;
    boolean isHungry;

    public Diner (String name) {
        this.name = name;
        this.isHungry = true;
    }

    public void eatWith (Spoon spoon, Diner spouse) {
        while (isHungry) {
            if (spoon.owner != this) {
                // wait for a while for the spoon to be released
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }

            // after wait, try to give the spoon to the spouse if she's hungry
            if (spouse.isHungry) {
                System.out.println("[" + name + "] Eat, baby, eat!");
                spoon.owner = spouse;
            } else {
                // finally
                spoon.use();
                isHungry = false;
                System.out.println("[" + name + "] Finally ate!!!"); // never
                spoon.owner = spouse;
            }
        }
    }
}

private static void livelock() {
    final Diner husband = new Diner("Adnan");
    final Diner wife = new Diner("Hannan");
    Spoon spoon = new Spoon(wife);
    
    try {
        new Thread(() -> husband.eatWith(spoon, wife)).start();
        Thread.sleep(1500);
        new Thread(() -> wife.eatWith(spoon, husband)).start();
    } catch (InterruptedException e) {
        throw new RuntimeException(e);
    }
}

Script bash pt build proiecte

 ./script.sh <nume branch>

branch="master"

if [ -n "$1" ]; then

branch=$1

fi

printf "\ngit pull from "$branch"\n\n"

currentDate=`date +"%Y-%m-%d-%H%M"`

filename="$currentDate.log"

touch $filename

for dir in `ls .`;

do

if [[ -d $dir ]]; then

echo $'\n'$dir

cd $dir

mvn clean &>> ../$filename

git checkout master

git pull

cd ..

echo $'\n' &>> $filename

fi

done

# legacy first

echo $'\n' >> $filename

for dir in `ls .`;

do

if [[ -d $dir && "$dir" == *"legacy"* ]]; then

echo $'\n'$dir

cd $dir

mvn install -DskipTests &>> ../$filename

cd ..

echo $'\n' &>> $filename

fi

done

printf "\n"

for dir in `ls .`;

do

if [[ -d $dir && "$dir" != *"legacy"* ]]; then

echo $'\n'$dir

cd $dir

mvn install -DskipTests &>> ../$filename

cd ..

echo $'\n' &>> $filename

fi

done

Probleme grafuri & arbori (2)

#5. Aranjarea unor cursuri cu relatie de dependenta intre ele

Se da un numCourses si o lista de dependinte prereq[i] = [a, b], cu semnificatia: pentru a putea participa la cursul a, un student trebuie sa participe intai la cursul b. Sa se gaseasca o aranjare posibila a cursurilor, cu satisfacerea tuturor relatiilor de dependenta. 

Nota: sortare topologica intr-un graf orientat. Se pun intr-o stiva si se elimina succesiv nodurile care nu au arce de iesire, impreuna cu arcele lor de intrare. Se repeta pana cand nu mai ramane niciun nod, apoi se scot nodurile din stiva; ele vor fi sortate topologic. Daca exista un ciclu in graf, nu exista sortare topologica - se va observa ca de la o iteratie la alta nu se mai sterg noduri.

class Solution {

public int[] findOrder(int numCourses, int[][] prereq) {

Map<Integer, Set<Integer>> outgoingEdges = new HashMap<>();

for (int i=0; i<numCourses; i++) {

outgoingEdges.put(i, new HashSet<>());

}

for (int[] edges : prereq) {

int to = edges[0], from = edges[1];

outgoingEdges.get(from).add(to);

}

int result[] = new int[numCourses];

try {

Stack<Integer> stack = topologicalSort(numCourses, outgoingEdges);

int i = 0;

while (!stack.isEmpty()) {

result[i++] = stack.pop();

}

} catch (CircularException e) {

return new int[0];

}

return result;

}

private Stack<Integer> topologicalSort(int numCourses, Map<Integer, Set<Integer>> outgoingEdges) {

Stack<Integer> nodeStack = new Stack<>();

int remainingNodes = outgoingEdges.size();

while (!outgoingEdges.isEmpty()) {

List<Integer> connectionsToDelete = new LinkedList<>();

for (int i=0; i<numCourses; i++) {

if (outgoingEdges.containsKey(i) && outgoingEdges.get(i).isEmpty()) {

nodeStack.push(i);

outgoingEdges.remove(i);

connectionsToDelete.add(i);

}

}

outgoingEdges.forEach((k,v) -> v.removeAll(connectionsToDelete));

connectionsToDelete.clear();

// este un ciclu atunci cand dupa o parcurgere completa nu se mai scot noduri

if (remainingNodes == outgoingEdges.size()) {

throw new CircularException();

}

remainingNodes = outgoingEdges.size();

}

return nodeStack;

}

private class CircularException extends RuntimeException {

public CircularException() {

super();

}

}

}

Varianta mai eficienta: sortare topologica folosind DSF. Dupa obtinerea unei ordini topologice, trebuie sa se verifice ca graful nu contine cicluri.

class Solution {

public int[] findOrder(int numCourses, int[][] prereq) {

List<List<Integer>> adjList = getAdjList(numCourses, prereq);

boolean visited[] = new boolean[numCourses]; // all false

Stack<Integer> stack = new Stack<>();

int result[] = new int[numCourses];

for (int i=0; i<numCourses; i++) {

if (!visited[i]) {

dfs(i, adjList, stack, visited);

}

}

int i = 0;

while (!stack.isEmpty()) {

result[i++] = stack.pop();

}

// check for any cycle

for (int node = 0; node < numCourses; node++) {

for (int conn : adjList.get(node)) {

// we have a vertex from node -> conn

// if conn appears before node in the ordering => cycle

if (indexOf(conn, result) < indexOf(node, result)) {

return new int[0]; // cycle

}

}

}

return result;

}

private void dfs(int node, List<List<Integer>> adjList, Stack<Integer> stack, boolean visited[]) {

visited[node] = true;

for (int neighbor : adjList.get(node)) {

if (!visited[neighbor]) {

dfs(neighbor, adjList, stack, visited);

}

}

stack.push(node);

}

private List<List<Integer>> getAdjList(int numCourses, int[][] prereq) {

List<List<Integer>> adjList = new ArrayList<>();

for (int i=0; i<numCourses; i++) {

adjList.add(new ArrayList<>());

}

for (int[] edges : prereq) {

int to = edges[0], from = edges[1];

adjList.get(from).add(to);

}

return adjList;

}

private int indexOf(int node, int[] order) {

for (int i=0; i<order.length; i++) {

if (order[i] == node) {

return i;

}

}

return -1;

}

}

#6. Primul stramos comun a doua noduri dintr-un arbore binar

Cand avem acces la parintii unui nod:

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (p == root || q == root) {

return root;

}

int diffDepth = depth(root, p) - depth(root, q);

while (diffDepth > 0) {

p = p.parent; // bring p on the same level with q

diffDepth--;

}

while (diffDepth < 0) {

q = q.parent; // bring q on the same level with p

diffDepth++;

}

while (p != q && p != null && q != null) {

// go up together

p = q.parent;

p = q.parent;

}

return (p != null && q != null) ? p : null;

}

private int depth(TreeNode root, TreeNode node) {

int depth = 0;

while (node != root) {

depth++;

node = node.parent;

}

return depth;

}

}

Cand nu avem acces la parintii unui nod:

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (p == root || q == root || root == null) {

return root;

}

return search(root, p, q);

}

private TreeNode search(TreeNode node, TreeNode p, TreeNode q) {

if (node == p || node == q) {

return node;

}

boolean isPinLeft = isNodeInSubtree(node.left, p);

boolean isQinLeft = isNodeInSubtree(node.left, q);

if (isPinLeft != isQinLeft) { // if p and q are in different branches of node

return node; // common ancestor

} else {

TreeNode nodeNext = isPinLeft ? node.left : node.right;

return search(nodeNext, p, q);

}

}

private boolean isNodeInSubtree(TreeNode subtree, TreeNode node) {

if (subtree == null) {

return false;

}

if (subtree.val == node.val) {

return true;

}

return isNodeInSubtree(subtree.left, node) || isNodeInSubtree(subtree.right, node);

}

// issue: repetitive calls to isNodeInSubtree when it already found the node

}

Alternativa - fara acces la parinti, tinem minte calea pana la nod in format L/R

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (p == root || q == root || root == null) {

return root;

}

search(root, p, "", q, "");

TreeNode ancestor = root;

int i = 0;

while (finalPathP.length() > i && finalPathQ.length() > i && finalPathP.charAt(i) == finalPathQ.charAt(i)) {

char c = finalPathP.charAt(i);

ancestor = c == 'L' ? ancestor.left : ancestor.right;

i++;

}

return ancestor;

}

String finalPathP = null;

String finalPathQ = null;

private void search(TreeNode node, TreeNode p, String pathP, TreeNode q, String pathQ) {

if (node == null) {

return;

}

if (node.val == p.val) {

finalPathP = pathP;

}

if (node.val == q.val) {

finalPathQ = pathQ;

}

if (finalPathP == null || finalPathQ == null) {

search(node.left, p, pathP + "L", q, pathQ + "L");

search(node.right, p, pathP + "R", q, pathQ + "R");

}

}

}