BoomBleBee

Top 6 API Architecture Styles (repost)

2025-11-08T12:12:00.001+02:00

Articol disponibil AICI

Training Java performance - Ziua 3 (microservicii)

2025-11-06T10:23:00.025+02:00

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)

2025-11-04T10:23:00.001+02:00

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)

2025-10-25T11:05:00.000+03:00

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

2025-09-13T18:23:00.006+03:00

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

2025-08-07T11:19:00.002+03:00

Windows:

> netstat -ano | findstr :8080

> taskkill PID <pid> /F

Linux:

> sudo lsof -i 8080

> sudo kill -9 <pid>

Proto vs Json performance test

2025-08-02T14:12:00.005+03:00


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

2024-12-04T11:47:00.002+02:00

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

2024-11-20T14:22:00.003+02:00

--- 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

2024-10-31T18:07:00.004+02:00

@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

2024-10-30T16:43:00.003+02:00

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

2024-08-16T20:32:00.004+03:00

#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

2024-08-09T14:31:00.006+03:00

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

2024-08-07T23:16:00.001+03:00

./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)

2024-07-21T21:06:00.018+03:00

#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");
        }
    }
}

Probleme grafuri & arbori (1)

2024-07-19T16:23:00.008+03:00

#1. Aflare daca exista o cale intre doua noduri dintr-un graf

Graf neorientat cu n noduri pentru care se da o lista de muchii edges[i] = [n1, n2] care inseamna ca exista o legatura directa intre n1 si n2. Sa se afle daca din n1 se poate ajunge in n2.

Nota: BFS. Nu este necesar sa folosim Map, un simplu ArrayList e suficient.

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }

        Map<Integer, Node> nodes = new HashMap<>();
        for (int i=0; i<n; i++) {
            nodes.put(i, new Node(i));
        }

        for (int i=0; i<edges.length; i++) {
            int from = edges[i][0], to = edges[i][1];
            nodes.get(from).addNeighbor(nodes.get(to));
            nodes.get(to).addNeighbor(nodes.get(from));
        }

        Node startNode = nodes.get(source);
        if (startNode.isLinkedTo(nodes.get(destination))) {
            return true;
        }
        startNode.setVisited();

        Queue<Node> queue = new LinkedList<>();
        queue.addAll(startNode.neighbors);
        
        while(!queue.isEmpty()) {
            Node next = queue.remove();
            if (!next.visited) {
                next.setVisited();
                if (next.isLinkedTo(nodes.get(destination))) {
                    return true;
                }
                queue.addAll(next.neighbors);
            }
        }

        return false;
    }

    private class Node {
        int value;
        List<Node> neighbors;
        boolean visited = false;

        public Node (int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }

        public void addNeighbor(Node node) {
            this.neighbors.add(node);
        }

        public boolean isLinkedTo(Node node) {
            return this.neighbors.contains(node);
        }

        public void setVisited() {
            this.visited = true;
        }
    }
}

#2. Transformarea unui array sortat intr-un BST (binary search tree)

Sirul este sortat crescator. In arborele creat, toti descendentii din stanga ai unui nod <= valoarea nodului, iar descendentii din dreapta > valoarea nodului. In plus, arborele trebuie sa fie aiba inaltimea minima posibila.

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return transform(nums, 0, nums.length - 1);
    }

    TreeNode transform(int[] nums, int indexFrom, int indexTo) {
        if (indexFrom == indexTo) {
            return new TreeNode(nums[indexFrom]);
        }
        
        if (indexFrom == indexTo - 1) {
            TreeNode root = new TreeNode(nums[indexTo]);
            root.left = new TreeNode(nums[indexFrom]);
            return root;
        }

        int size = indexTo - indexFrom + 1;
        TreeNode root = new TreeNode(nums[indexFrom + size/2]);
        root.left = transform(nums, indexFrom, indexFrom + size/2 - 1);
        root.right = transform(nums, indexFrom + size/2 + 1, indexTo);
        return root;
    }
}

#3. Arbore binar echilibrat

Dandu-se un arbore binar, sa se afle daca este echilibrat, adica pt fiecare nod diferenta intre inaltimile in jos ale fiecarui subarbore sa nu fie mai mare decat 1.

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        try {
            findHeightUnderNode(root);
        } catch (UnbalancedTreeException e) {
            return false;
        }
        return true;
    }

    private int findHeightUnderNode(TreeNode node) throws UnbalancedTreeException {
        if (node.left == null && node.right == null) {
            return 1;
        }
        int heightUnderLeft = node.left == null ? 0 : findHeightUnderNode(node.left);
        int heightUnderRight = node.right == null ? 0 : findHeightUnderNode(node.right);
        if (Math.abs(heightUnderLeft - heightUnderRight) > 1) {
            throw new UnbalancedTreeException();
        }
        return 1 + Math.max(heightUnderLeft, heightUnderRight);
    }

    private class UnbalancedTreeException extends RuntimeException {
        public UnbalancedTreeException() {
            super();
        }
    }
}

#4. Validarea unui BST

Se da un arbore binar. Sa se verifice daca este un arbore binar de cautare (BST).

class Solution {
    public boolean isValidBST(TreeNode root) {
        try {
            checkValid(root, null, null);
        } catch(InvalidBSTException e) {
            return false;
        }
        return true;
    }

    private void checkValid(TreeNode node, Integer lessThan, Integer moreThan) {
        // lessThan, moreThan - constrangeri propagate de sus in jos
        if (node == null || (node.left == null && node.right == null)) {
            return;
        }
        
        if (node.left != null) {
            if (node.left.val >= node.val || (lessThan != null && node.left.val >= lessThan) || 
                    (moreThan != null && node.left.val <= moreThan)) {
                throw new InvalidBSTException();
            }
        }
        if (node.right != null) {
            if (node.right.val <= node.val || (lessThan != null && node.right.val >= lessThan) || 
                    (moreThan != null && node.right.val <= moreThan)) {
                throw new InvalidBSTException();
            }
        }

        checkValid(node.left, min(node.val, lessThan), moreThan);
        checkValid(node.right, lessThan, max(node.val, moreThan));
    }

    private int min(Integer x, Integer y) {
        if (x != null && y != null) {
            return Math.min(x,y);
        }
        return x != null ? x : y;
    }

    private int max(Integer x, Integer y) {
        if (x != null && y != null) {
            return Math.max(x,y);
        }
        return x != null ? x : y;
    }

    private class InvalidBSTException extends RuntimeException {
        public InvalidBSTException() {
            super();
        }
    }
}

Probleme programare dinamică & recursivitate (2)

2024-07-17T10:52:00.015+03:00

#5. Generarea tuturor parantezelor

Dându-se un număr n, să se genereze toate combinațiile de paranteze bine-formate. Adică: fiecare paranteză deschisă formează un cuplu cu o paranteză închisă și cuplul începe întotdeauna cu paranteza deschisă.

Exemplu: Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        // all strings will have 2*n length and are built from scratch
        generateParenthesis(2*n, n, "", result);
        return result;
    }

    private void generateParenthesis(int n, int initialN, String generated, List<String> result) {
        if (n == 1) {
            // in the last call we can only use )
            if (isValid(generated + ')', true, initialN)) {
                result.add(generated + ')');
            }
            return;
        }

        // recurse only if we are on the good path with the partial result
        if (isValid(generated + '(', false, initialN)) {
            generateParenthesis(n-1, initialN, generated + '(', result);
        }
        if (isValid(generated + ')', false, initialN)) {
            generateParenthesis(n-1, initialN, generated + ')', result);
        }        
    }

    private boolean isValid(String str, boolean checkFinal, int n) {
        int left = 0, right = 0;
        for (char c : str.toCharArray()) {
            if (c == '(') {
                left++;
            } else {
                right++;
                if (right > left) {
                    return false;
                }
            }
        }
        return checkFinal ? 
            left == right : // a well-formed string has the same number of ( and )
            left <= n;      // a partial result should not have ( count more than n
    }
}

#6. Asezarea unor cutii intr-o stiva

Avem N cutii, fiecare cutie fiind reprezentata in 3 dimensiuni (width, length, height). Ele se pot stivui astfel incat cutia aflata deasupra altei cutii va avea w2 <= w1, l2 <= l1 si h2 <= h1. Nu toate cutiile se pot stivui, dar ele se pot roti astfel incat o inaltime sa devina lungime etc. Care e inaltimea celei mai inalte stive posibile?

Nota: la prima vedere, problema este o variatie la problema Maximum subarray (aflarea sumei maxime a unui subsir dintr-un sir), la care se adauga cateva constrangeri. Am implementat urmatorii pasi:

transformarea obiectelor-cutie prin rotire astfel incat inaltimea sa fie dimensiunea cu valoarea cea mai mare dintre cele 3D (greedy)
sortarea cutiilor dupa inaltime, urmata de celelalte doua dimensiuni, descrescator (*)
aplicarea algoritmului pt Max subarray mentionat anterior, cu adaptarea constrangerilor pentru cutii (programare dinamica)

(*) neasteptat de tricky este sortarea cutiilor. Nu toate cutiile sunt ordonabile, iar un algoritm eficient precum Mergesort greseste pentru anumite cazuri. Asa ca am optat pentru un Bubblesort cu numar maxim de comparatii intre elemente, pentru a forta o relatie de ordonare intre oricare 2 elemente din sirul de cutii. (S-a dovedit si ca doar Bubblesort-ul cu 2 for-uri va functiona corect pentru toate testele!)

Nota: nu e extrem de eficient, dar e corect. Complexitate: timp O(N^2) determinata in principal de Bubblesort, spatiu O(N) pt un array suplimentar.

class Solution {
    public int maxHeight(int[][] boxes) {
        // boxes[i] = (w, len, h)

        rotateObjectsMaxHeight(boxes);

        if (boxes.length == 1) {
            return boxes[0][2];
        }

        sortByMaxHeightAndWLDesc(boxes);

        int maxSumHeight = boxes[0][2];
        int largest[] = new int[boxes.length];
        largest[0] = boxes[0][2];
        int lastAddedIndex = 0; // index of the last added box to obtain largest so far

        for (int i=1; i<boxes.length; i++) {
            if (canPlace(boxes[lastAddedIndex], boxes[i])) {
                largest[i] = largest[lastAddedIndex] + boxes[i][2];
            } else {
                largest[i] = boxes[i][2];
                // try to put current box on any previous box if it gives profit
                for (int j=0; j<i; j++) {
                    if (j != lastAddedIndex) {
                        if (canPlace(boxes[j], boxes[i]) && largest[i] < largest[j] + boxes[i][2]) {
                            largest[i] = largest[j] + boxes[i][2];
                        }
                    }
                }
            }

            if (maxSumHeight < largest[i]) {
                maxSumHeight = largest[i];
                lastAddedIndex = i;
            }
        }

        return maxSumHeight;
    }

    private void rotateObjectsMaxHeight(int[][] boxes) {
        // h = max(w, len, h) => swap h with the max
        for (int i=0; i<boxes.length; i++) {
            int max = Math.max(boxes[i][0], Math.max(boxes[i][1], boxes[i][2]));
            if (max != boxes[i][2]) {
                int aux = boxes[i][2]; // h
                boxes[i][2] = max;
                if (max == boxes[i][0]) { // w
                    boxes[i][0] = aux;
                } else if (max == boxes[i][1]) { // l
                    boxes[i][1] = aux;
                }
            }
        }
    }

    private boolean canPlace(int[] boxUnder, int[] boxTop) {
        boolean firstCheck = boxUnder[0] >= boxTop[0] && boxUnder[1] >= boxTop[1];
        boolean rotateCheck = boxUnder[0] >= boxTop[1] && boxUnder[1] >= boxTop[0];
        return firstCheck || rotateCheck;
    }

    private boolean equals(int[] boxUnder, int[] boxTop) {
        boolean firstCheck = boxUnder[0] == boxTop[0] && boxUnder[1] == boxTop[1];
        boolean rotateCheck = boxUnder[0] == boxTop[1] && boxUnder[1] == boxTop[0];
        return firstCheck || rotateCheck;
    }

    public void sortByMaxHeightAndWLDesc(int[][] boxes) {
        // max complexity bubble sort needed because we need to make as many comparisons as possible
        for (int i=0; i<boxes.length - 1; i++) {
            for (int j=i+1; j<boxes.length; j++) {
                boolean rightHeightHigher = boxes[i][2] < boxes[j][2];
                boolean equalHeightsWithRightBigger = boxes[i][2] == boxes[j][2] && 
                        canPlace(boxes[j], boxes[i]) &&
                        !equals(boxes[j], boxes[i]);
                if (rightHeightHigher || equalHeightsWithRightBigger) {
                    int[] aux = boxes[i];
                    boxes[i] = boxes[j];
                    boxes[j] = aux;
                }
            }
        }
    }
}

#7. In cate moduri se pot pune paranteze unei expresii booleene

Se da o expresie formata din valorile 0, 1 (false, true) si operatorii binari &, | si ^. In cate moduri se pot pune paranteze astfel incat evaluarea expresiei sa fie result? Parantezele de genul (( )) nu sunt valide.

Exemplu: countEval('1 & 0 | 1', true) = 2, posibilitatile sunt 1 & (0 | 1) si (1 & 0) | 1.

Rezolvare: cateva observatii:

cazuri de baza: countEval(Strings.EMPTY, result) = 0 si countEval(str, result) ~ str.equals(result) adica 0 sau 1, cand str are un singur caracter.
valorile 0 si 1 vor sta intotdeauna pe pozitiile 0, 2, 4, ... n , pe cand operatorii binari vor sta intotdeauna pe pozitiile 1, 3, 5, ... n-1

asta duce la un for (int i=1; i<str.length(); i+=2) in care sa calculam subproblemele

daca ne situam pe pozitia unui operator (i), putem calcula recursiv leftCountTrue = countEval(str.substring(0, i), true) si rightCountTrue = countEval(str.substring(i+1), true). Similar si leftCountFalse, rightCountFalse. Toate variabilele ne trebuie pentru ca la un '|', de exemplu, evaluarea uneia din parti poate fi si false, iar rezultatul final sa fie true.
se calculeaza totalCount = toate modurile posibile de a obtine orice rezultat al evaluarii, care consta din toate modurile de a aranja parantezele in partea stanga * toate modurile de a aranja parantezele in partea dreapta

totalCount = (leftTrue + leftFalse) * (rightTrue + rightFalse);

calculam totalCountTrue in functie de operatorul de pe pozitia i:

'&' --> totalCountTrue = leftCountTrue * rightCountTrue
'|' --> totalCountTrue = leftCountTrue * rightCountTrue + leftCountTrue * rightCountFalse + leftCountFalse * rightCountTrue;
'^' --> totalCountTrue = leftCountTrue * rightCountFalse + leftCountFalse * rightCountTrue;

in functie de rezultatul dorit, solutia subproblemei curente este totalCountTrue sau totalCount - totalCountTrue. Ea se adauga la variabila pentru pastrarea tuturor modurilor.

Optimizare: unele apeluri ale metodei countEval se repeta. Putem pastra un tabel unde stocam rezultatul apelului curent pe care sa-l obtinem rapid, daca exista, inainte de intrarea in for.

if (memo.containsKey(result + str)) return memo.get(result+str);
memo.put(result+str, countWays);

Probleme programare dinamică & recursivitate (1)

2024-07-16T18:31:00.003+03:00

#1. Robot in a Grid (p.d.)

Un robot se află într-o matrice, in coltul din stanga sus. El se poate deplasa doar la dreapta sau in jos, daca celula vizata nu contine un obstacol. Tinta lui este sa ajunga in coltul din dreapta jos al matricii. Sa se afle in cate moduri poate ajunge robotul la destinatie.

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        // go from destination to origin
        Map<Integer,Integer> cache = new HashMap<>();
        return search(grid, grid.length-1, grid[0].length-1, cache);
    }

    private int search(int[][] grid, int i, int j, Map<Integer,Integer> cache) {
        if (reachedBack(grid, i, j)) {
            return 1; // found one way!
        }

        // Number of ways to reach grid[i][j] = ways to reach grid[i-1][j] (go up) +
        //                                      ways to reach grid[i][j-1] (left)

        if (isCellFit(grid, i, j)) {
            int indexUp = (i-1) * grid[0].length + j;
            int pathUp = 0;
            // element indexUp could be already visited but not necessarily attainable from grid[i][j]
            if (isCellFit(grid, i-1, j)) {
                pathUp = cache.containsKey(indexUp) ? cache.get(indexUp) : search(grid, i-1, j, cache);
            }             

            int indexLeft = i * grid[0].length + j-1;
            int pathLeft = 0;
            if (isCellFit(grid, i, j-1)) {
                pathLeft = cache.containsKey(indexLeft) ? cache.get(indexLeft) : search(grid, i, j-1, cache);
            }
            
            int index = i * grid[0].length + j;
            cache.put(index, pathUp + pathLeft); // grid[i][j] is visited and its result established

            return pathUp + pathLeft;
        }

        return 0;
    }

    private boolean isCellFit(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
            return false; // out of grid
        }        
        return grid[i][j] == 0; // should be obstacle free
    }

    private boolean reachedBack(int[][] grid, int i, int j) {
        return i==0 && j==0 && grid[i][j] == 0;
    }
}

#2. Toate submultimile unei multimi (recursivitate)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        result.addAll(find(Arrays.stream(nums).boxed().collect(Collectors.toList())));
        return result;
    }

    private List<List<Integer>> find(List<Integer> set) {
        if (set.size() == 1) {
            return Arrays.asList(Arrays.asList(set.get(0)));
        }
        
        List<List<Integer>> result = new ArrayList<>(); 
        result.add(Arrays.asList(set.get(0))); // primul element
        
        List<List<Integer>> subsets = find(set.subList(1, set.size()));
        result.addAll(subsets); // submultimile din (A - primul elem)
        
        for (List<Integer> subset : subsets) {
            List<Integer> subsetCopy = clone(subset);
            // adaug primul element la toate submultimile din (A - primul elem)
            subsetCopy.add(set.get(0));
            result.add(subsetCopy);
        }
        
        return result;
    }

    private List<Integer> clone(List<Integer> set) {
        List<Integer> clonedSet = new ArrayList<>();
        clonedSet.addAll(set);
        return clonedSet;
    }
}

#3. Inmultirea a doua numere fara a folosi * , doar prin adunari, scaderi sau deplasari de biti, in numar minim de operatii. (recursivitate)

public class MultiplyIntegers {
    public static int solve(int a, int b) {
        int minAb = Math.min(a, b);
        int maxAb = Math.max(a, b);
        return multiply(minAb, maxAb); // to optimize the number of recursions
    }

    private static int multiply(int a, int b) {
        if (a == 0 || b == 0) {
            return 0;
        }
        if (a == 1) {
            return b;
        }

        // a is even => multiply(a,b) = 2 * multiply(a/2, b)
        // a is odd => multiply(a,b) = 2 * multiply(a/2, b) + b

        int partialRes = multiply(a >> 1, b); // multiply (a/2, b)
        partialRes <<= 1; // partialRes *= 2
        if (a % 2 == 1) {
            partialRes += b;
        }
        return partialRes;
    }

    public void test() {
        List<TestCase> testCases = new ArrayList<>();
        testCases.add(new TestCase(5, 3, 15));
        testCases.add(new TestCase(10, 7, 70));
        testCases.add(new TestCase(31, 35, 1085));
        testCases.add(new TestCase(16, 6, 96));
        testCases.add(new TestCase(3, 0, 0));
        testCases.add(new TestCase(27, 4, 108));
        testCases.add(new TestCase(36475, 4249, 154982275));
        testCases.add(new TestCase(4585, 42339, 194124315));

        long startTime = System.nanoTime();
        for (TestCase testCase : testCases) {
            int result = MultiplyIntegers.solve(testCase.a, testCase.b);
            System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
                    (result == testCase.result ?
                            "PASSED" :
                            "FAILED with output=" + result + " " +
                                    "[expected=" + testCase.result + "] \t\t<------"));
        }
        long endTime = System.nanoTime();
        System.out.println("Executed in " + (endTime - startTime)/1000000 + " ms.");
    }

    public static void main(String args[]) {
        new MultiplyIntegers().test();
    }

    public class TestCase {
        public final int a;
        public final int b;
        public final int result;
        public TestCase(int a, int b, int result) {
            this.a = a;
            this.b = b;
            this.result = result;
        }
    }
}

#4. Turnurile din Hanoi

Se dau 3 turnuri: A, B, C. Pe fiecare turn se pot aseza discuri aranjate descrescator, cele mai mari stand la baza si cele mai mici deasupra. Sa se mute toate discurile din A in C, folosind B ca intermediar, respectand conditia. Care e numarul minim de miscari pentru a realiza acest transfer?

Nota: se porneste de la cazul de baza - 1 disc, care are nevoie de o singura miscare pt a ajunge in C. Apoi simulam pe hartie ce se intampla cand avem 2 discuri. Apoi 3. De fiecare data se poate observa (de la n >= 2) ca turnul B se comporta ca un buffer. De asemenea, pentru a rezolva cazuri superioare, ne putem folosi de rezultatul anterior deja calculat, la care mai avem de mutat un singur disc (ultimul). Astfel: pentru a muta n discuri, trebuie sa mutam n-1 discuri din A in B (folosind C ca intermediar) pentru a lasa liber ultimul disc din A, apoi mutat direct discul din A in C, apoi mutate cele n-1 discuri din B in C (folosind A ca intermediar). Se observa ca numarul de mutari este 2^n - 1.

Nota: design-ul solutiei. Obiectele Disk si Tower sunt "personalizate". Am facut cateva validari. Tower detine o stiva de obiecte Disk. Adaugarea se face intr-o metoda din Tower afectand un alt obiect Tower din care se scoate un disc.

import java.util.*;

public class Hanoi {
    private int moveDisks (int n, Tower origin, Tower destination, Tower buffer) throws Exception {
        if (n == 1) {
            destination.takeFrom(origin);
            return 1; // one move
        }

        int steps = 0;
        steps += moveDisks(n-1, origin, buffer, destination); // move first n-1 from origin to buffer
        destination.takeFrom(origin);                            // move last element from origin to dest
        steps++;
        steps += moveDisks(n-1, buffer, destination, origin); // move back n-1 elements from buffer to dest

        return steps;
    }

    public static void main(String args[]) {
        Hanoi hanoi = new Hanoi();
        hanoi.test();
    }

    public void test() {
        Hanoi hanoi = new Hanoi();

        List<Disk> disks = new ArrayList<>();
        disks.add(new Disk(1, 5));
        disks.add(new Disk(2, 2));
        disks.add(new Disk(3, 8));
        disks.add(new Disk(4, 1));
        disks.add(new Disk(5, 3));
        disks.add(new Disk(6, 4));
        disks.add(new Disk(6, 7));
        disks.add(new Disk(6, 6));

        // hanoi(n) = 2^n - 1

        List<TestCase> testCases = new ArrayList<>();
        testCases.add(new TestCase(new Tower("A", disks.subList(0, 1)), new Tower("B"), new Tower("C"), 1));
        testCases.add(new TestCase(new Tower("A", disks.subList(0, 2)), new Tower("B"), new Tower("C"), 3));
        testCases.add(new TestCase(new Tower("A", disks.subList(0, 3)), new Tower("B"), new Tower("C"), 7));
        testCases.add(new TestCase(new Tower("A", disks.subList(0, 4)), new Tower("B"), new Tower("C"), 15));
        testCases.add(new TestCase(new Tower("A", disks.subList(0, 5)), new Tower("B"), new Tower("C"), 31));
        testCases.add(new TestCase(new Tower("A", disks.subList(0, 6)), new Tower("B"), new Tower("C"), 63));
        testCases.add(new TestCase(new Tower("A", disks.subList(0, 7)), new Tower("B"), new Tower("C"), 127));
        testCases.add(new TestCase(new Tower("A", disks), new Tower("B"), new Tower("C"), 255));
        for (TestCase tc : testCases) {
            try {
                int numberOfDisks = tc.origin.getNumberOfDisks();
                int res = hanoi.moveDisks(numberOfDisks, tc.origin, tc.destination, tc.buffer);
                boolean testResult = res == tc.expectedMoves && tc.origin.getNumberOfDisks() == 0 &&
                        tc.buffer.getNumberOfDisks() == 0 &&
                        tc.destination.getNumberOfDisks() == numberOfDisks;
                System.out.println("Test case #" + testCases.indexOf(tc) + " " +
                        (testResult ?
                                "PASSED" :
                                "FAILED with moves=" + res + " " +
                                        "[expected.moves=" + tc.expectedMoves + "] AND " +
                                        "with origin.size=" + tc.origin.getNumberOfDisks() + " AND " +
                                        "with buffer.size=" + tc.buffer.getNumberOfDisks() + " AND " +
                                        "with destination.size=" + tc.destination.getNumberOfDisks() +
                                        " [expected.dest.size=" + numberOfDisks + "] \t\t<------"));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    class Tower {
        String label;
        Stack<Disk> disks;

        public Tower(String label) {
            this.label = label;
            this.disks = new Stack<>();
        }

        public Tower(String label, List<Disk> initDisks) {
            this.label = label;
            this.disks = new Stack<>();
            Collections.sort(initDisks);
            for (Disk disk : initDisks) {
                this.disks.push(disk);
            }
        }

        public void takeFrom(Tower from) throws Exception {
            if (from.disks.isEmpty()) {
                throw new Exception("Nothing to add from!");
            }
            Disk diskToAdd = from.disks.peek();
            if (!disks.isEmpty() && diskToAdd.value > disks.peek().value) {
                throw new Exception("Cannot add disk with value " + diskToAdd.value + " to tower " + label);
            }
            disks.push(from.disks.pop());
        }

        public int getNumberOfDisks() {
            return this.disks.size();
        }

        @Override
        public String toString() {
            return "Tower " + label + " has " + disks.size() + " disks.";
        }
    }

    class Disk implements Comparable<Disk> {
        int label;
        int value;

        public Disk(int label, int value) {
            this.label = label;
            this.value = value;
        }

        @Override
        public int compareTo(Disk disk) {
            if (disk.value == value) {
                return 0;
            }
            return disk.value - value;
        }
    }

    public class TestCase {
        public final Tower origin;
        public final Tower buffer;
        public final Tower destination;
        public final int expectedMoves;
        public TestCase(Tower tower, Tower buffer, Tower destination, int expectedMoves) {
            this.origin = tower;
            this.buffer = buffer;
            this.destination = destination;
            this.expectedMoves = expectedMoves;
        }
    }
}

Amazon "code assessment"

2024-07-09T18:31:00.006+03:00

1. Student prep for test

Un student se pregateste de un examen, are de studiat o carte impartita in capitole: pages[i] reprezinta nr. de pagini per capitole. El are la dispozitie un numar maxim de zile de pregatire pana la examen si ar vrea sa citeasca cat mai putin pe zi, daca se poate. De fiecare data cand se termina capitolul, studentul incheie ziua si incepe cu urmatorul capitol in urmatoarea zi. Sa se afle numarul minim de pagini/zi pe care trebuie sa le citeasca pentru a fi gata la timp.

Ex.: pages = [2,3,4,5] si days=5 . Daca citeste 4 pagini/zi, in primele 3 zile citeste 3 capitole, iar al patrulea il face in 2 zile (4+1 pagini). Daca ar citi mai putin, nu s-ar incadra in timp.

package amazon;

import java.util.*;

class StudentExam {

    public static int minimumNumberOfPages(List<Integer> pages, int days) {
        if (pages.isEmpty()) {
            return 0;
        }

        if (pages.size() > days) {
            return -1;
        }

        int max = 0;
        for (int page : pages) {
            if (page > max) {
                max = page;
            }
        }
        if (pages.size() == days) {
            return max;
        }

        return solve_kiss_approach(pages, days);
    }

    public static int solve_kiss_approach(List<Integer> pages, int days) {
        int totalPages = pages.stream().reduce((a,b) -> a+b).get();
        int pagesPerDay = totalPages % days == 0 ? totalPages/days : totalPages/days+1;
        while (true) {
            int neededDays = 0;
            for (int i=0; i<pages.size(); i++) {
                neededDays += pages.get(i) % pagesPerDay == 0 ? 
                        pages.get(i) / pagesPerDay : 
                        pages.get(i)/pagesPerDay+1;
            }
            if (neededDays <= days) {
                return pagesPerDay;
            }
            pagesPerDay++;
        }
    }

    public static void main(String args[]) {
        new StudentExam().test();
    }

    public void test() {
        List<TestCase> testCases = new ArrayList<>();
        testCases.add(new TestCase (Arrays.asList(2,3,4,5), 5, 4));
        testCases.add(new TestCase (Arrays.asList(3,1,5,3,2), 2, -1));
        testCases.add(new TestCase (Arrays.asList(3,1,5,3,2), 6, 3));
        testCases.add(new TestCase (Arrays.asList(3,1,5,3,2), 8, 3));
        testCases.add(new TestCase (Arrays.asList(3,1,5,3,2), 9, 2));
        testCases.add(new TestCase (Arrays.asList(7), 2, 4));
        testCases.add(new TestCase (Arrays.asList(20,1,30,25,1), 9, 13));
        testCases.add(new TestCase (Arrays.asList(30,25,20,1,1), 12, 9));
        testCases.add(new TestCase (Arrays.asList(70,4,1,1,1), 12, 9));
        testCases.add(new TestCase (Arrays.asList(15,15,16,20,11), 12, 8));
        testCases.add(new TestCase (Arrays.asList(2,3,4,5), 100, 1));
        for (TestCase testCase : testCases) {
            int result = StudentExam.minimumNumberOfPages(testCase.pages, testCase.days);
            System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
                    (result == testCase.expectedResult ?
                            "PASSED" :
                            "FAILED with output=" + result + " " +
                                    "[expected=" + testCase.expectedResult + "] \t\t<------"));
        }
    }

    public class TestCase {
        public final List<Integer> pages;
        public final int days;
        public final int expectedResult;
        public TestCase(List<Integer> pages, int days, int pagesPerDay) {
            this.pages = pages;
            this.days = days;
            this.expectedResult = pagesPerDay;
        }
    }
}

2. Market trends of Amazon stocks

Se da un array reprezentand profiturile pe un numar de luni consecutive, initial toate valorile sunt pozitive (castig). Sa se afle numarul maxim de luni ale caror valori pot fi transformate in pierdere (inmultindu-le cu -1), astfel incat profitul cumulat de la luna la luna sa reprezinte totusi castig.

Ex.: PnL = [5,3,1,2], daca il transformam in [5,-3,-1,2] => profitul cumulat este [5, 2, 1, 3] cu toate valorile pozitive => 2 elemente s-au putut negativiza si nu exista o solutie cu 3 elemente negativizate.

package amazon;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class AmazonStocks {
    public static int getMaxNegativePnL(List<Integer> PnL) {
        int maxCumul = 0;
        for (int i=0; i<PnL.size(); i++) {
            maxCumul += PnL.get(i);
        }

        int num = 0;
        for (int i=PnL.size()-1; i>=1; i--) {
            if (maxCumul - PnL.get(i)*2 > 0) {
                maxCumul -= PnL.get(i)*2;
                num++;
            }
        }

        return num;
    }

    public static void main(String args[]) {
        new AmazonStocks().test();
    }

    public void test() {
        List<TestCase> testCases = new ArrayList<>();
        testCases.add(new TestCase(Arrays.asList(5,3,1,2), 2));
        testCases.add(new TestCase(Arrays.asList(1,1,1,1,1), 2));
        testCases.add(new TestCase(Arrays.asList(5,2,3,5,2,3), 3));
        testCases.add(new TestCase(Arrays.asList(5,10,1,9,5,4), 3));
        testCases.add(new TestCase(Arrays.asList(2,3,4,1,1,2), 3));
        testCases.add(new TestCase(Arrays.asList(3,2,4,1,1,2), 4));
        for (TestCase testCase : testCases) {
            int res = AmazonStocks.getMaxNegativePnL(testCase.pnl);
            System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
                    (res == testCase.result ? "PASSED" : "FAILED with output=" + res +
                            " [expected=" + testCase.result + "] <------"));
        }
    }

    public class TestCase {
        public final List<Integer> pnl;
        public final int result;
        public TestCase(List<Integer> pnl, int result) {
            this.pnl = pnl;
            this.result = result;
        }
    }
}

Bonus Demo #1: Optimizing Box Weights

Se da un array de greutati ale unor cutii, se cere impartirea acestor valori in 2 multimi A si B cu urmatoarele conditii:

A intersectat cu B = vid
A reunit cu B = arr
A are numar minim de elemente
sum(A) > sum(B)
A trebuie returnat in ordine crescatoare
daca exista mai multe multimi A, se returneaza cea cu greutate totala maxima

Ex.: arr = [1, 12, 5, 5, 7] => A = [7, 12]

package amazon.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

class SetProblem {
    public static List<Integer> minimalHeaviestSetA(List<Integer> arr) {
        arr.sort(Comparator.reverseOrder());
        AtomicInteger totalSum = new AtomicInteger(0);
        arr.forEach(elem -> totalSum.set(totalSum.get() + elem));

        List<Integer> A = new ArrayList<>();
        int aSum = 0;
        for (int elem : arr) {
            A.add(elem);
            aSum += elem;
            if (aSum > totalSum.get() - aSum) {
                A.sort(Comparator.naturalOrder());
                return A;
            }
        }
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        new SetProblem().test();
    }

    public void test() {
        List<TestCase> testCases = new ArrayList<>();
        testCases.add(new TestCase(Arrays.asList(1,12,5,5,7), Arrays.asList(7, 12)));
        testCases.add(new TestCase(Arrays.asList(70,4,1,1,1), Arrays.asList(70)));
        testCases.add(new TestCase(Arrays.asList(15,15,16,20,11), Arrays.asList(15,16,20)));
        testCases.add(new TestCase(Arrays.asList(2), Arrays.asList(2)));
        testCases.add(new TestCase(Arrays.asList(1,10,9), Arrays.asList(9,10)));
        testCases.add(new TestCase(Arrays.asList(1,10,12), Arrays.asList(12)));
        testCases.add(new TestCase(Arrays.asList(), Arrays.asList()));
        testCases.add(new TestCase(Arrays.asList(6,7,3,10,1), Arrays.asList(7,10)));
        for (TestCase testCase : testCases) {
            List<Integer> result = SetProblem.minimalHeaviestSetA(testCase.arr);
            System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
                    (result.equals(testCase.result) ? "PASSED" : "FAILED with output=" + result +
                            " [expected=" + testCase.result + "] <------"));
        }
    }

    public class TestCase {
        public final List<Integer> arr;
        public final List<Integer> result;
        public TestCase(List<Integer> arr, List<Integer> result) {
            this.arr = arr;
            this.result = result;
        }
    }
}

Bonus Demo #2: Items in containers

Se da un string compus din caracterele '*' pentru un obiect si '|' pentru delimitarea unui compartiment. Se cere sa se afle toate obiectele aflate intre pozitiile start si stop din acel string, cu conditia ca obiectul sa apartina unui compartiment inchis (intre doua caractere '|').

Ex.: "|*|**|*|" , start = 1, stop = 5 => se afla 2 obiecte (numerotarea incepe de la 0, start/stop sunt inclusive)

package amazon.demo;

import java.util.*;

public class Containers {
    private Map<Integer, Integer> buildMap(String input) {
        Map<Integer, Integer> countMap = new TreeMap<>(); // the keys are sorted asc
        int count = 0;
        int indexStart = -1;
        for (int i=0; i<input.length(); i++) {
            if (input.charAt(i) == '|') {
                if (indexStart >= 0) {
                    countMap.put(indexStart, count);
                }
                indexStart = i;
                count = 0;
            } else if (input.charAt(i) == '*') {
                count++;
            }
        }
        return countMap;
        // key: indexFrom, value: number of items
    }

    private int find(int from, int to, Map<Integer, Integer> map) {
        if (to - from < 2) {
            return 0;
        }

        int count = 0;
        boolean started = false;
        for (int key : map.keySet()) {
            if (!started && key >= from && to >= key + map.get(key) + 1) {
                count += map.get(key);
                started = true;
            } else if (started && to >= key + map.get(key) + 1) {
                count += map.get(key);
            }
        }

        return count;
    }

    public static void main(String[] args) {
        new Containers().test();
    }

    public void test() {
        List<TestCase> testCases = new ArrayList<>();
        testCases.add(new TestCase("|*|**|*|", new int[]{0, 0, 1, 2, 5, 7, 15},
                new int[]{2, 1, 4, 7, 7, 7, 17}, new int[]{1, 0, 0, 3, 1, 0, 0}));
        testCases.add(new TestCase("|**|*|*", new int[]{0, 0, 1},
                new int[]{4,5,6}, new int[]{2,3,1}));
        testCases.add(new TestCase("*|*|*|||**|", new int[]{0,0,0,1,5,5, 0},
                new int[]{1,2,3,5,9,10,10}, new int[]{0, 0, 1, 2, 0, 2, 4}));

        Containers containers = new Containers();
        for (TestCase testCase : testCases) {
            Map<Integer, Integer> occurrenceMap = containers.buildMap(testCase.input);
            for (int i=0; i<testCase.start.length; i++) {
                int res = containers.find(testCase.start[i], testCase.stop[i], occurrenceMap);
                System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
                        (res == testCase.result[i] ? "PASSED" : "FAILED with output=" + res +
                                " [expected=" + testCase.result[i] + "] <------"));
            }
        }
    }

    public class TestCase {
        public final String input;
        public final int[] start;
        public final int[] stop;
        public final int[] result;
        public TestCase(String input, int[] start, int[] stop, int[] expectedResult) {
            this.input = input;
            this.start = start;
            this.stop = stop;
            this.result = expectedResult;
        }
    }
}

CATALOG Cracking the code interview

2024-06-27T19:31:00.002+03:00

POST #1

Șiruri de caractere
impl. Java pt. cap.1 Arrays & Strings aici
Liste înlănțuite
Stive & cozi
Arbori binari și grafuri

POST #2

Operații pe biți
Întrebări de sucit mințile

POST #3

Matematică, probabilități
OOP
Recursivitate și programare dinamică

POST #4

Memorie și scalabilitate
Sortări și căutări
Testări

POST #5

C/C++
Java
Baze de date
Thread-uri, lock-uri

CATALOG 50DSA

2024-06-22T16:38:00.022+03:00

Array

1. Two Sum OK

2. Best time to buy and sell stock OK

3. Contains duplicate OK

4. Product of array except self OK

5. Maximum subarray OK

6. Maximum product subarray OK

7. Find the minimum in rotated sorted array

8. Search in rotated sorted array

9. 3Sum

10. Container with most water

Matrix

11. Set matrix zeroes OK

12. Spiral matrix OK

13. Rotate image OK

14. Word Search OK

String

15. Longest Substring Without Repeating Character

16. Longest Repeating Character Replacement

17. Minimum Window Substring

18. Valid Anagram

19. Group Anagrams

20. Valid Parentheses

21. Longest Palindromic Substring

22. Palindromic Substrings

23. Encode and Decode Strings

Linked List

24. Reverse Linked Lists OK

25. Linked List Cycle OK

26. Merge two sorted lists OK

27. Merge k Sorted Lists OK - vezi si #38

28. Remove Nth Node From End of List OK

29. Reorder List OK

Tree

30. Maximum Depth of Binary Tree OK

31. Same Tree OK

32. Invert Binary Tree OK

33. Binary Tree Maximum Path Sum OK

34. Binary Tree Level Order Traversal OK

35. Serialize & Deserialize Binary Tree OK

36. Design Add and Search Words Data Structure OK

37. Word Search II OK

Heap

38. Merge k Sorted Lists OK

39. Top K Frequent Elements OK

40. Find Median from Data Stream OK

Graph

41. Clone graph OK

42. Course Schedule OK

43. Number of Islands OK

44. Pacific Atlantic Water Flow OK

Dynamic Programming - link

45. Climbing Stairs OK

46. Coin Change OK

Bitwise Operations - link

47. Sum of Two Integers OK

48. Number of 1 Bit OK

49. Counting Bits OK

50. Missing Number OK

Dockerfile

2024-06-21T12:18:00.001+03:00

# specify base image to start from

FROM node:9.4.0-alpine
# copy files
COPY app.js .
COPY package.json .
# execute commands
RUN npm install &&\
    apk update &&\
    apk upgrade
# exposes port 8080 with a specified protocol inside a Docker Container
EXPOSE  8080
# run app.js with executable "node"
CMD node app.js

# Build in the current dir with tag myimage version v1
# > docker build . -t myimage:v1
# > docker images

# Run the image as a container 
# -d=detach, run in background
# -p=publish a container's port to the host
# > docker run -dp 8080:8080 myimage:v1

# Ping the application
# > curl localhost:8080

Probleme Strings

2024-06-13T17:07:00.008+03:00

#1. First non-repeating character

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

class Solution {
    public int firstUniqChar(String str) {
        Map<Character,Integer> map = new HashMap<>();
        for (int i=0; i<str.length(); i++) {
            Integer count = map.get(str.charAt(i));
            map.put(str.charAt(i), count == null ? 1 : count + 1);
        }
        for (int i=0; i<str.length(); i++) {
            if (map.get(str.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }

    public int firstUniqChar_2(String str) { // str contains only lowercase letters 'a' t o 'z'
        int bitVector = 0;
        int unique = (int) Math.pow(2, 27) - 1; // 1....1 for 26 bits corresponding to 'a' to 'z'
        for (int i=0; i<str.length(); i++) {
            int index = str.charAt(i) - 'a';
            if ((bitVector & (1 << index)) > 0) { // if bit index already set
                unique = unique & ~(1 << index); // clear bit at index
            }
            bitVector = bitVector | (1 << index); // set bit at index
        }
        for (int i=0; i<str.length(); i++) {
            int index = str.charAt(i) - 'a';
            boolean isBitSet = (unique & (1 << index)) > 0;
            if (isBitSet) {
                return i;
            }
        }
        return -1;
    }
}

#2. Permutation of a palindrome

Given a string, return if it is a permutation of a palindrome.

class Solution {

public boolean canBecomePalindrome(String str) {

if (str.length() == 0) {

return false;

}

int bitVector = 0;

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

int index = str.charAt(i) - 'a';

if ((bitVector & (1 << index)) > 0) { // if bit set

bitVector = bitVector & ~(1 << index); // clear

} else {

bitVector = bitVector | (1 << index); // set

}

// se poate transforma in palindrom daca:

// Are nr par de caractere si toti bitii 0, SAU

// nr impar de caractere si un singur bit 1

boolean evenAmountOfChar = str.length() % 2 == 0;

boolean hasBit1 = false;

for (int i=0; i<26; i++) { // 26 letters in alphabet

if ((bitVector & (1 << i)) > 0) { // if bit set

if (hasBit1) {

return false; // a second bit is set

}

hasBit1 = true;

}

return evenAmountOfChar ^ hasBit1;

}

Microsoft "technical task"

2024-06-06T19:06:00.005+03:00

1. De corectat un program ✖️

A este un array de cifre 0 sau 1 (reprezentarea binară a unui număr, cu A[0] = LSB). Se cere să se afle prima poziție (de la LSB la MSB) de pe care apare cel mai lung șir de biți/cifre 1. De corectat maxim 2 linii (eu am corectat una).

class Solution {

    int solution(int[] A) {

        int n = A.length;

        int i = n - 1;

        int result = -1;

        int k = 0, maximal = 0;

        while (i > 0) {

            if (A[i] == 1) {

                k = k + 1;

                if (k >= maximal) {

                    maximal = k;

                    result = i;

}

}

            else

                k = 0;

            i = i - 1;

}

if (A[i] == 1 && k + 1 >= maximal) // correction >= instead of >

            result = 0;

        return result;

}

}

2. Repartizare pacienți într-un sanatoriu ✔️

Se dau N oaspeți (0... N-1) care așteaptă să fie repartizați pe camere, într-un sanatoriu. Într-o cameră se pot caza oricâți, dar nu toți pacienții vor să aibă mulți colegi de cameră.

Input: un array A cu N elemente, A[K] = numărul maxim de persoane într-o cameră, permis de pacientul K, inclusiv el însuși

Să se afle numărul minim de camere necesare pentru a caza toți pacienții.

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] A) {
        int rooms = 0;

        List<Integer> patients = Arrays.stream(A).boxed().collect(Collectors.toList());
        Collections.sort(patients);

        for (int i=0; i<patients.size(); i++) {
            rooms++;
            if (patients.get(i) == 1) {
                continue;
            }
            i += patients.get(i);
        }

        return rooms;
    }
}

3. Reducerea unui șir de caractere ✔️

Un șir S conține doar literele A, B, C, D. El se poate transforma eliminând un grup de litere adiacente „AB” sau „CD” (în orice ordine). Să se afle șirul final, după aplicarea tuturor reducerilor posibile. Algoritmul trebuie să fie eficient pt seturi mari de date (un șir de maxim 250.000 caractere).

class Solution {
    public String solution2(String word) {
        String copy;
        do {
            copy = word;
            word = word.replaceAll("AB", "");
            word = word.replaceAll("BA", "");
            word = word.replaceAll("CD", "");
            word = word.replaceAll("DC", "");
        } while (!copy.equals(word));

        return word;
    }

    public String solution(String word) {
        if (word.isEmpty()) {
            return word;
        }
        int[] marked = new int[word.length()];
        marked[0] = 0;
        for (int i=1; i<word.length(); i++) {
            marked[i] = 0;
            if (condition(word, i, i-1)) {
                    marked[i] = 1;
                    marked[i-1] = 1;
                    i++;
            }
        }

        for (int i=0; i<word.length(); i++) {
            if (marked[i] == 1) {
                marked = circle(word, i, marked);
                i++;
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i=0; i<marked.length; i++) {
            if (marked[i] == 0) {
                result.append(word.charAt(i));
            }
        }

        return result.toString();
    }

    private int[] circle(String word, int pos, int[] marked) {
        int left = pos - 1;
        int right = pos + 2;
        while (left >= 0 && right < marked.length && marked[left] == 0) {
            if (marked[left] == 0 && marked[right] == 0 && condition(word, left, right)) {
                marked[left] = 1;
                marked[right] = 1;
                left--;
                right--;
                continue;
            } 

            int r2 = right;
            while (r2 < marked.length && marked[r2] == 1) {
                r2++;
            }
            if (r2 != right) {
                right = r2;
            } else {
                break;
            }
        }

        return marked;
    }

    private boolean condition(String word, int i, int j) {
        return word.charAt(i) == 'A' && word.charAt(j) == 'B' || 
                word.charAt(i) == 'B' && word.charAt(j) == 'A' ||
                word.charAt(i) == 'C' && word.charAt(j) == 'D' ||
                word.charAt(i) == 'D' && word.charAt(j) == 'C';
    }
}

4. Bonus (demo): First Missing Positive ✖️

Given an unsorted integer array nums, return the smallest positive integer that is not present in nums. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Prima implementare (firstMissingPositive2): O(n^2) timp și O(n) spațiu

A doua implementare (firstMissingPositive): O(n) timp și O(1) spațiu

class Solution {
    public int firstMissingPositive2(int[] nums) {
        if (initialCheck(nums) == 1) {
            return 1;
        }
        Set<Integer> elems = new HashSet<>();
        for (int num : nums) {
            elems.add(num);
        }
        for (int i=1; ; i++) {
            if (!elems.contains(i)) {
                return i;
            }
        }
    }

    private int initialCheck(int[] nums) {
        boolean allNegative = true;
        int min = Integer.MAX_VALUE;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] > 0) {
                allNegative = false;
                if (min > nums[i]) {
                    min = nums[i];
                }
            }
        }
        if (allNegative || min > 1) {
            return 1;
        }
        return 0;
    }

    private boolean isArrayComplete(int[] nums, int max) {
        int xor = 0;
        int times = 0;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] > 0) {
                xor = xor ^ nums[i];
                times++;
            }
        }
        for (int i=1; i<=times; i++) {
            xor = xor ^ i;
        }
        return xor == 0 && times == max;
    }

    public int firstMissingPositive(int[] nums) {
        if (initialCheck(nums) == 1) {
            return 1;
        }

        // find min, max
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] < 0) {
                nums[i] = 0;
            }
            if (max < nums[i]) {
                max = nums[i];
            }
            if (min > nums[i] && min > 0) {
                min = nums[i];
            }
        }

        if (min == 1 && isArrayComplete(nums, max)) {
            return max + 1;
        }

        // tag in place
        int tag = max != Integer.MAX_VALUE ? max + 1 : max;
        for (int i=0; i<nums.length; i++) {
            int val = nums[i] >= tag ? nums[i]-tag : nums[i]; // untag/extract if already tagged
            if (val > 0 && val < nums.length && nums[val-1] < tag) { // avoid duplicates
                nums[val-1] += tag;
            }
        }

        // find first untagged
        for (int i=0; i<nums.length; i++) {
            if (nums[i] < tag && nums[i] >= 0) {
                return i+1;
            }
        }

        return max + 1; // should not arrive here
    }
}

50 DSA-Questions: Biti #47, #48, #49, #50

2024-06-01T23:49:00.005+03:00

#47. Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -.

class Solution {
    // addition a, b => sum = a ^ b; carry = a & b

    public int getSum1(int a, int b) {
        int carry;
        while (b != 0) {
            carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }

    public int getSum2(int a, int b) {
        int carry = (a & b) << 1;
        int result = a ^ b;
        if (carry == 0) {
            return result;
        }             
        return getSum2(carry, result);
    }
}

#48. Number of 1 Bit

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

class Solution {
    public int hammingWeight(int num) {
        int bits = 0;
        while (num != 0) {
            boolean is1 = (num & 1) != 0;
            if (is1) {
                bits++;
            }
            num = num >> 1;
        }
        return bits;
    }
}

#49. Counting Bits

Given an integer n, return an array of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

class Solution {
    public int[] countBits(int n) {
        int[] array = new int[n+1];
        for (int i=0; i<=n; i++) {
            array[i] = hammingWeight(i);
        }
        return array;
    }
}

#50. Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

class Solution {
    public int missingNumber2(int[] nums) {
        int max = nums.length;
        int sum = (max+1) * max / 2;
        for (int num : nums) {
            sum -= num;
        }        
        return sum;
    }

    public int missingNumber(int[] nums) {
        int xor = nums.length;
        // XOR properties:
        // a ^ b = b ^ a => we can xor the elements in any order
        // x ^ x = 0 => nums[k] ^ i = 0 if nums[k] == i => will eliminate matching elements
        // x ^ 0 = x
        // the unmatched i will stand out
        for (int i=0; i<nums.length; i++) {
            xor = xor ^ nums[i] ^ i;
        }        
        return xor;
    }
}

Bonus: Reverse bits

Reverse bits of a given 32 bits unsigned integer.

public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        int i = 32;  // need to fill all 32 bits
        while (i > 0) {
            int currentBit = n & 1;
            res = res << 1 | currentBit; // res = res * 2 + currentBit;
            n = n >> 1;
            i--;
        }
        return res;
    }
}