Problema JavaScript - algoritm pentru un calendar de evenimente

Limbaje de Programare JavaScript / Node
,
1

Am participat la un screening tehnic pentru o pozitie de web developer (3 probleme de rezolvat pe https://www.interviewzen.com - foarte interesanta platforma, prima data cand interactionez cu ea) si din cele 3 probleme la ultima dintre ele n-am stiut ce sa scriu.

Nici n-am reusit sa gasesc ceva online care sa ma lamureasca.
Daca are cineva chef/timp enuntul e asta (raspunsul l-am trimis deja catre recruter, ca sa nu apara discutii, sunt interesat de solutie doar pentru ca n-am stiut cum sa rezolv problema):

You are given access to your team’s in-house calendar. Given a schedule of all of your team’s meetings,
return the windows of free time between the meetings. Be careful, as there might be more than one meeting
at any given time.

For example, given:

[(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]

your function would return:

[(1, 3), (8, 9)]

3 Likes
2

Explic întâi logica vizual, și apoi postez și cod.

Pentru a ne asigura că ajungem la rezultatul corect, o să facem exemplul lor puțin mai complicat, așa încât să luăm în calcul și cerința “there might be more than one meeting at any given time.”. Așadar, o să folosesc pentru ilustrație exemplul:

[(0, 1), (3, 5), (4, 8), (10, 12), (4, 7), (9, 10)]

Observă cum între 4 și 7 sunt două întâlniri simultane.

  1. Sortăm întâlnirile după ora de început, crescător, iar apoi după ora de sfârșit, tot crescător: https://i.imgur.com/6WZcV5L.png
  2. Un timeslot e liber numai atunci când data de sfârșit a unei întâlniri este anterioară datei de început a celei care urmează imediat după: https://i.imgur.com/eYHq6VB.png

Vizual e foarte clar, să trecem la implementare. O să implementez în JS, deși chiar nu are nici o importanță, la fel de bine poți explica algoritmul în orice limbaj:

function getTimeslots(meetings) {
    meetings.sort(function (a, b) {
        if (a[0] < b[0]) {
            return -1;
        } else if (a[0] > b[0]) {
            return 1;
        } else {
            if (a[1] < b[1]) {
                return -1;
            } else {
                return 1;
            }
        }
    });

    var timeslots = [], current, next;
    for (var i = 0; i < meetings.length - 1; i++) {
        current = meetings[i];
        next = meetings[i + 1];
        if (current[1] < next[0]) {
            timeslots.push([current[1], next[0]]);
        }
    }
    
    return timeslots;
}

var tests = {total: 0, passed: 0, failed: 0};

function check(meetings, expected) {
    tests.total++;

    var timeslots = getTimeslots(meetings);
    if (timeslots.toString() == expected.toString()) {
        tests.passed++;
    } else {
        tests.failed++;
        console.error("Expected: " + JSON.stringify(expected) + ". Got: " + JSON.stringify(timeslots));
    }
}

check(
    [[0, 1], [3, 5], [4, 8], [10, 12], [4, 7], [9, 10]],
    [[1, 3], [8, 9]]
);

console.log(tests);

Poți să apelezi funcția check() cu mai multe variante de meetings, pentru a testa. Eu nu am testat cu foarte multe variante, deci nu garantez 100% corectitudinea.

Observație: Este important să sortăm după ambele capete ale unui meeting, pentru că altfel nu am putea respecta cerința cu meeting-urile care se suprapun. Dacă am sorta numai după ora de început, am avea următoarea situație: https://i.imgur.com/7mAZxZs.png. Observă cum am considera (7, 9) ca timeslot liber, în loc de (8, 9).

3 Likes
3

Acum, pentru că discuția e interesantă. Dacă erai la un interviu față în față, și nu automatizat, cu toate că cerința lor e foarte clară, “return the windows of free time between the meetings”, mai puteai să mai faci următoarea observație:

"Într-un scenariu realist m-ar interesa care sunt timeslot-urile libere din întreaga zi, nu numai cele dintre întâlniri. Așa încât dacă aș primi următorul set de date, mai restrâns…

[(3, 5), (4, 8), (9, 10)]

…să nu ignor intervalele (0, 3) și (10, 12). Sau dacă primesc ca input un array gol (ziua e complet liberă), să nu întorc ca rezultat alt array gol, ci un interval care să cuprindă toată ziua.

Așadar, presupunând că 0 și 12 reprezintă capetele intervalului orar în care se țin întâlniri (și nu orele adevărate de muncă, că sper că nu muncește nimeni la ora 0 noaptea la voi aici - caz în care oricum nu vreau să mă angajați :smiley: - este foarte simplu să adaptăm funcția noastră așa încât să întoarcă toate timeslot-urile libere, adăugând capetele de interval automat în lista de meetings: https://i.imgur.com/hMhyq2J.png

În cazul ăsta nu mai trebuie să adăugăm la funcție decât următoarea linie, fix la începutul funcției:

meetings.push([0,0], [12,12]);

4 Likes
4

Scriind mai multe teste, am descoperit un bug. C-așa-i în unit testing :smiley: . Să presupunem cazul:

[(3,5), (2,6), (7,10)]

Pentru că intervalul (2,6) cuprinde cu totul intervalul (3,5), rezultatul final va fi (5,7), care e greșit. Corect este (6,7). Așadar, imediat după sortare, trebuie să scoatem cu totul din lista de meetings acele înregistrări care sunt cuprinse cu totul în altele. Așadar, în exemplul de mai sus, după sortare array-ul trebuie să devină:

[(2,6), (7,10)]

Am actualizat codul, și am și spart funcția în funcții separate pentru fiecare pas. Am scris mai multe teste, inclusiv acesta care nu trecea, și am creat un Gist, pentru că devine dificil de urmărit pe forum:

2 Likes
5

Și pentru că o suită de unit tests bine pusă la punct îți permite să faci refactoring fără frică, m-am apucat să rescriu codul, pentru că mi-a venit în cap alt algoritm. Am redus cele trei funcții la o singură funcție, mult mai scurtă, care satisface toate testele.

Algoritmul, pe scurt: se folosesc meeting-urile și timeslot-urile (pe măsură ce sunt descoperite) pentru umplerea unui interval (variabila filled). Un timeslot e considerat liber atunci când există o pauză între intervalul deja umplut și următorul meeting:

function getTimeslots(meetings) {
    var timeslots = [];

    if (meetings.length > 1) {
        meetings.sort(function (a, b) {
            return a[0] < b[0] ? -1 : 1;
        });

        var filled = meetings[0], i, current;
        for (i = 1; i < meetings.length; i++) {
            current = meetings[i];
            if (current[0] > filled[1] && current[1] > filled[1]) {
                timeslots.push([filled[1], current[0]]);
            }
            filled[1] = Math.max(filled[1], current[1]);
        }
    }

    return timeslots;
}

În felul ăsta nu mai e nevoie nici de sortarea după data de sfârșit a meeting-urilor, și nici de atenție acordată acelor meeting care sunt cuprinse în altele. Suita de teste rămâne identică, nu o mai reproduc aici.

3 Likes
6

Nota: Nu am citit raspunsurile de mai sus, inainte sa postez. Mi-am amintit problema din liceu.

Varianta TL;DR:

Sortezi dupa orele de inceput, apoi dupa orele de finalizat (ultimul finalizat fiind primul in lista). Dupa ce ai sortat, e nevoie de o singura parcurgere pentru a verifica de unde pana unde se suprapun si astfel aflii perioadele libere (de cand s-a terminat ultimul event suprapus si pana a inceput primul event dupa el).

Alternativ, poti uni toate evenimentele care se suprapun (in loc sa le retii intr-un vector) si obtii aceeasi chestie. Si varianta aceasta ar fi mai eleganta, daca nu ai nevoie de datele initiale sau de memoria in plus folosita.

7

Multumesc @victorstanciu, foarte utile raspunsurile tale. Sunt de parere ca intrebarea e totusi putin peste ceea ce stiu eu momentan. .

Pentru ca am fost intrebat, scriu mai jos si celelalte doua intrebari, impreuna cu raspunsurile mele.
Raspunsurile reflecta nivelul actual al cunostintelor mele de JavaScript. Asa ca nu m-ar deranja eventualele imbunatatiri/comentarii ce pot fi aduse. Apreciez criticile.

Intrebare 1:

You are given a list of integers. Replace each element in the list with the product of all the other elements.
For example, given:
  [1, 7, 3, 4]
your function would return:
  [84, 12, 28, 21]
by calculating:
  [7*3*4, 1*3*4, 1*7*4, 1*7*3]


Raspuns 1: 

function replace(list) {
    
    var total = 1;
    var newList = [];
    
    for (i=0; i<list.length; i++) {
        total = total * list[i];
    }
    
    for (i=0; i<list.length; i++) {
        newList[i] = total / list[i];
    }
    
list = newList;
return list;
}



Intrebare 2:

You're working for a big airline company. You task is to build a new feature for their in-flight entertainment system. Given a list of movies and the flight's duration, find two different movies with a total runtime equal to the flight's.
The movies are given as a list of integers, each integer representing the movie's length in minutes. Assume the users will watch exactly two movies. Optimize for runtime over memory.
For example, given a flight of 273 minutes and the following list of movie lengths:
  [134, 92, 118, 88, 104, 155, 122]
your function would return: 
  2 5 # meaning the third movie (length 118) and the sixth movie (length 155) sum up to 273


Raspuns 2:

function movies(flightDuration, moviesList) {
    for (i=0; i<moviesList.length - 1; i++) {
        for (j=1; j<moviesList.length; j++) {
            if (moviesList[i] + moviesList[j] == flightDuration) {
                return i + " " + j;
            }
        }
    }
}
1 Like
8

E clar ca ai dat un răspuns care demonstrează ca te-ai prins de șmecherie. De obicei la un test se urmărește si cum ai ajuns la rezultat, nu numai dacă ai făcut corect.

Legat de prima problema, cineva s-ar putea lua de faptul ca “iesi” un pic prea mult din range-ul numerelor. Practic ai nevoie de numere pana la produsul tuturor numerelor. Cum ai la schimbarea a doua numere (a=a+b;b=a-b;a=a-b;)

O alta chestie care ar putea fi vrut sa vada este daca stiai ce face reduce si map, gen (sper sa fie corect)

var p=[ 1, 7, 3, 4].reduce(function(previousValue, currentValue) {
  return previousValue * currentValue;
});

[ 1, 7, 3, 4].map(function (item){return p/item;})
3 Likes
9

La intrebarea 1 prima varianta a fost sa iau valorile de la 0 la i-1 si i+1 pana la list.length. Evident ca m-am incurcat si nu mi-a iesit nimic.
Varianta doi e cea de mai sus, care mi-a venit in cap dupa ce m-am jucat putin cu exemplul lor pe hartie.

Raspunsul la intrebarea 2 l-am facut din prima asa.

10

Inca doua solutii la intrebarea 3 (tot la fel obtinute, intreband oameni):

var meetings = [ [ 0, 1 ], [ 3, 5 ], [ 4, 8 ], [ 10, 12 ], [ 9, 10 ] ];  

// create readable objects from array tuples  
meetings = meetings.map( function( entry ) {  
    return { start : entry.shift(), end : entry.shift() }; } );  
  
// create timeslots for each hour of the fictional (work) day  
    var timeslots = [];  
    while( timeslots.length < 12 )  
          timeslots.push( { start : timeslots.length, end : timeslots.length + 1 } );  
  
// check which of these slots don't overlap with meetings  
        var free = timeslots.filter( function( slot ) {  
          return ! meetings.some( function( meeting ) {  
            return meeting.start <= slot.start && meeting.end >= slot.end;  
  } ); } );  
  
// show free time slots  
console.log( free );

si

const checkFreeTimeslots = function (meetingList) {  
  const maxMeetingEnd = 24;  
  if (!meetingList) {    
    return [[0,maxMeetingEnd]];  
  }  

  const availableSlots = [];  
  let currentBegin = 0;  
  let currentEnd = 0;  

  const sortedMeetingList = meetingList.sort((a,b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));  
  sortedMeetingList.forEach((currentMeeting) => {

    if (currentMeeting[0] > currentEnd) {
      availableSlots.push([currentEnd, currentMeeting[0]]);
      currentBegin = currentMeeting[0];
      currentEnd = currentMeeting[1];

    } else if (currentMeeting[1] > currentEnd ) {
      currentEnd = currentMeeting[1];
    }
  });

  if (currentEnd !== maxMeetingEnd) {
    availableSlots.push([currentEnd, maxMeetingEnd]);
  }

  return availableSlots;

 };
11

Păi stai, prima soluție e incorectă. A doua îmi e lene să o testez, pentru că nu e JS (later edit: ba e JS, pe ES6, discutat mai jos), dar pe prima o poți verifica și tu, rulând testele mele pe ea. De fapt o poți rula și fix cum ai primit-o, pentru că nu întoarce valorile corecte nici măcar pentru exemplul dat în cerință:

  • În loc să întoarcă [(1,3), (8,9)] întoarce [(1,2), (2,3), (8,9)].
  • Pentru array gol, în loc să întoarcă tot un array gol, întoarce [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12]]. Și dacă am considera că am extins cerința așa încât să întoarcă toate timeslot-urile libere din întreaga zi, ci nu cele între întâlniri, răspunsul corect aici ar fi [0,12] oricum.
  • Pentru [(1,3)], în loc să întoarcă un array gol (pentru că există o singură întâlnire, deci nu ai cum să ai timeslot între întâlniri, întoarce [[0,1],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12]]

Acum, soluții incorecte sunt complet acceptabile în testele tehnice față în față, unde cel care te intervievează este interesat mai mult să te vadă cum gândești, dar când ai temă pentru acasă și trebuie să trimiți răspunsul, apăi ai face bine ca răspunsul tău să meargă măcar pentru exemplele date de ei, chiar dacă uiți să acoperi edge cases.

Cea mai mare greșeală de fapt nici măcar nu este că funcția nu merge cum trebuie, ci că persoana respectivă nu a citit atent cerințele:

  • Cerința este să întorci the windows of free time between the meetings, nu orele libere din întreaga zi.
  • Se specifică foarte clar în exemplul lor că timeslot-urile libere pot avea mai mult de o oră, și pentru intervalul orar 1-3 trebuie să întorci (1,3), nu (1,2),(2,3).

Incapacitatea de a asculta și înțelege cerințe este una din cele mai mari bile negre pe care le poți primi la un interviu. Pentru ca bug-uri produce orice programator, dar dacă din start pornești cu o înțelegere defectuoasă a cerințelor, șansele să ajungi la o soluție corectă sunt nule.

Fac o paranteză pentru a spune că d-aia este bine să îți scrii un set minim de teste, pornind de la exemplele primite în cerință, pe care să le tot rulezi pe măsură ce adaptezi soluția. În felul ăsta nu riști ca la final să livrezi o soluție care nu satisface nici măcar cerința.

12

E evident ca experienta ta e mult mai mare ca a mea si e posibil sa spun prostii acum.
Dar cred ca interpretarea e relativa. Si doi oameni se pot contrazice la nesfarsit pe o idee, amandoi avand dreptate in felul lor.
Mie acum solutia ta mi se pare cea mai buna. Dar nu cred ca cealalalta e gresita, ci interpreteaza altfel enuntul cel care a rezolvat-o.

Solutia cealalta (de care spui ca nu e JS), eu am testat-o in consola din browser si a rulat. Dar daca tu zici ca nu e in JS, nu te contrazic.

Partea de testare nu am acoperit-o pana acum in ce am invatat. Cel putin din toate tutorialele urmate si tot ce am citit, nu am dat pana acum peste asa ceva.
Daca mi-ai putea oferi si niste indicatii(materiale/resurse) legat de partea asta ti-as fi recunoscator.

13

Ba este, aspectul ăsta nu e discutabil, și nu lasă loc de interpretări. Atâta timp cât întoarce alte date fix pentru exemplul din cerință, soluția e greșită. Punct. Pentru exemplul lor trebuia să întoarcă [(1,3), (8,9)], nu [(1,2), (2,3), (8,9)].

În principiu eu sunt de acord cu tine, dar doar pe cazul general, nu aici, îmi pare rău. Cerința e engleză simplă, clară ca bună ziua: the windows of free time between the meetings. Poate oamenii vor să știe dacă au timp să comande pizza între două întâlniri.

Dacă ești la interviu față în față dai dovadă de inițiativă și flexibilitate dacă ceri clarificări, sau dacă propui o soluție care să întoarcă un rezultat mai relevant, și anume timeslot-urile din întreaga zi. Dar asta o faci doar ca un bonus. Soluția ta trebuie în primul rând să respecte cerințele, care sunt sfinte.

1 Like
14

Pardon, ba e JS, pe standardul ECMAScript 6 din câte îmi dau seama. Eu rulez testele în Node, nu în browser, și rulez pe un VM unde am un Node mai vechi, care nu suportă ES6 (nu știu nici dacă versiunea actuală de Node suportă, că nu am mai folosit). Îți merge în browser pentru că browserul suportă deja.

1 Like
15

Am inteles. Voi citi mai multe, multumesc pentru link.

16

Păi domeniul se numește unit testing, și e vast, dar poți pentru început, când mai ai situații ca asta, să faci cum am făcut aici. Dacă tot trebuie să testezi funcția pe care o scrii, depune un mic efort la început și construiește un mod simplu de tot de a testa outputul cu cât mai multe variante de input. Nu trebuie să fie nimic mai complicat decât o funcție căreia îi spui “Cu input-ul x, mă aștept ca funcția y să întoarcă rezultatul z”.

Asta pentru a prinde obiceiul de a te folosi de teste, care îți dau siguranța că modificările pe care le faci pe cod respectă încă cerințele. Iar apoi caută “unit testing in [JS|PHP|Python|Java|Whatever]”, și vezi care este toolset-ul uzual pentru stack-ul tău. Iar mai apoi poți opta să treci la TDD.

2 Likes
17

Plecand de la premiza ca ora 12 nu este o ora valida pentru a incepe o intalnire si intalnirile dureaza cel putin 1 ora am facut si eu o versiune (pentru prima intrebare):

var meetings = [[0, 1], [3, 5], [4, 8], [10, 12], [9, 10]];
var total_hours = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
var empty_hours = [];

meetings.forEach(function(meeting) {
    for (var i = meeting[0], j = meeting[1]; i < j; i++) {
        var hour_index = total_hours.indexOf(i);
        if (hour_index > -1) {
            total_hours.splice(hour_index, 1);
        }                
    }
});

total_hours.forEach(function(hour, index, arr) {
    if (index > 0 && arr[index-1] +1 == arr[index]) {
        empty_hours[empty_hours.length-1][1] = hour+1;
    } else {
        empty_hours.push([hour, hour+1]);
    }
});

console.log(empty_hours);

Glad that’s over :slight_smile:

18

For the record: https://en.wikipedia.org/wiki/Interval_tree, https://en.wikipedia.org/wiki/Segment_tree

Ar fi fost mai bine daca ai fi postat topicul la sectiunea de algoritmica a forumului, din moment ce provocarea pentru tine nu a fost limbajul js, ci algoritmica.

Acolo ma uit mai des.

Cum ai tu acolo intervale discrete, poti aloca din start un arbore pentru “toate intervalele indivizibile” (frunzele de jos), si construi pe el acel arbore.

Apoi la fiecare introducere de nou interval, marchezi unul sau mai multe noduri ca folosite.

OypruV8.png823×276 5.93 KB

Efectiv faci pruning la fiecare interval, deci cu cat ai mai multe date, cu atat algoritmul va tinde sa ruleze mai rapid pentru operatia query.

La insertie va trebui uneori sa faci sinteza: cand toti copiii unui nod sunt marcati ca folositi, marcheaza si parintele ca folosit (recursiv).

Abordarea e ideala cand ai nevoie de un algoritm cu garantie de timp de rulare maxim, independent de cantitatea de date (de intervale introduse).

5 Likes
19

Totusi parca e mai bine sa vezi diferite variante pana sa ajungi la un algoritm batut in cuie.

Good to know anyway :slight_smile:

1 Like