Omówienie zadania Loteria – problem z rozmowy kwalifikacyjnej do firmy Google

Szczegółowe omówienie zadania Loteria.
Zadanie powstało na podstawie problemu jaki otrzymują osoby które chcą pracować w firmie Google.

Link do powyższego omówienia zadania Loteria:
https://youtu.be/xF5wlR-xX8g?t=4631
Link do zadania Loteria:
https://szkopul.edu.pl/problemset/problem/loteriazad/site

Zadanie Loteria wymaga użycia algorytmu Binary Search.

Znalezienie dwóch liczb które sumują się do zadanej wartości – to jeden z problemów jaki otrzymują kandydaci do Google podczas interview.

Trudny?
Oczywiście nie.
Też może być tym który wymyśla jak ma działać komputer, Facebook czy… nowy start-up!
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
——-
Kod C++ programu Loteria, który jest omówiony w powyższym filmie i który otrzymuje 100%

#include <bits/stdc++.h>

using namespace std;

const int MAX_LOSOW = 10000010;
int losy[MAX_LOSOW];

int BinarySearchPierwszy (int poczatek, int koniec, int wartosc) {
 int srodek;
 while (poczatek < koniec) {
    srodek = (poczatek + koniec) / 2;
    if (losy[srodek] >= wartosc)
        koniec = srodek;
    else
        poczatek = srodek + 1;
 }
 if ( losy[poczatek] == wartosc )
    return poczatek;
 return -1;
}

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int k, liczba_losow;
 int p1_index, p2_index, p2_wartosc, i;

 cin >> k;
 cin >> liczba_losow;

 for (i=1; i<=liczba_losow; ++i)
    cin >> losy[i];

 sort (losy+1, losy+liczba_losow+1);

 for (p1_index=1; p1_index<liczba_losow; ++p1_index) {
    p2_wartosc = k - losy[p1_index];
    p2_index = BinarySearchPierwszy (p1_index+1, liczba_losow, p2_wartosc);
    if (p2_index == -1)
       continue;
	cout << "Mozesz ryzykowac\n";
    return 0;
 }

 cout << "Bez szans\n";
 return 0;

}
Link do pliku ze wzorcowym kodem C++ zadania Loteria - tym samym który został użyty w omówieniu 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz