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

--- Experienta NTT Data ---

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

Morala: ???

--- Experienta Spirent ---

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

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

--- Experienta Thales ---

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

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

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

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

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

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

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

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

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

Amazon "code assessment"

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

 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

Microsoft "technical task"

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

    }

}

Unix/networking interview questions

Lista proceselor in executie:

> px aux

> ps -l

> ps -e

Get thread dump of running Java processes:

> jps -lv      # afla [pid] proces java

> kill -3 [pid]

GREP - cauta linii in fisier text folosind un regex

> cat file.txt | grep "Cauta un rand"

TAIL - tipareste ultimele linii dintr-un fisier (default ultimele 10)

> cat file.txt | tail -n 2

LESS - afiseaza cate o pagina (nu incarca tot)

> less file.txt

> cat file.txt | less -p "pattern"   # afiseaza de la acel rand incolo

MORE - la fel ca LESS, insa navigarea inapoi e limitata si nu are optiuni de cautare 

Diferenta TCP si UDP

TCP = transmission control protocol, bazat pe conexiune, de incredere dar mai lent, verificare buna de erori. Potrivit pt transmitere de texte, fisiere, navigare pe internet.

UDP = user datagram protocol, fara conexiune, rapid dar pierde date (nu retransmite), verificare minimala de erori, permite broadcasting. Potrivit pt transmitere continut media (video, audio), jocuri in retea.

In caz de coliziune, ruterele prefera pachetele TCP si renunta la cele UDP.

Aflare spatiu liber pe disc:

> df

Aflare marime folder

> du