16 martie 2015

Probleme pentru interviu - Operatii pe biti & Brain teasers

---------------------------- cap. 5 - bit manipulation -----------------------------------------------------


Pe langa operatiile AND, OR, XOR, NOT, deplasare la dreapta sau la stanga, este bine de avut in vedere urmatoarele operatii pe biti:

* get bit at position i
(( num & (1 << i)) != 0)
(1 << i) inseamna 1 deplasat la stanga, i pozitii. 
Pe locul acelor pozitii se pune 0. Devine: 100....0 (0 de i ori) sau 0...010...0 , unde 1 se afla pe pozitia i.
num & (1 << i) = num & (0..0100....0) , de unde rezulta fix valoarea bitului i, care se compara cu 0.


* set bit at position i (adica bitul devine 1)
(num | (1 << i))
1 << i are aceeasi valoare cum am explicat, iar operatia OR va seta automat (cu 1) bitul i din num, pentru ca 1 OR x = 1 .


* clear bit at position i (adica bitul devine 0)
int mask = ~ (1 << i);
return num & mask;
Masca este opusul lui (0...010...0) adica (1...101...1), cu 0 pe bitul i.
num & mask pastreaza bitii din num asa cum sunt, mai putin bitul i care este obligat sa devina 0.


* clear all bits from most significant to bit i
int mask =  (1 << i) - 1;
return num & mask;
(1 << i) - 1 = (0..010...0) - 1 = (0...001...1) , adica toti bitii de la cel mai semnificativ pana la i inclusiv devin 0, iar restul 1.  num & mask pastreaza acest rest de biti si ii sterge pe ceilalti.


* clear all bits from the least significant to bit i
int mask = ~ ((1 << (i+1)) - 1);
return num & mask;
Sa o luam pe rand.
1 << (i + 1) inseamna (0...010...0), cu (i+1) zerouri in coada. Scazand 1 => (0...001....1), cu i de 1 in coada. Negand totul => (1...10...0), cu i zerouri in coada, si in final aplicand AND, se curata ultimii i biti din num, restul ramanand la fel.


* actualizarea unui bit la pozitia i, cu valoarea v
int mask1 = ~ (1 << i);
int mask2 = v << i;
return (num & mask1) | mask2;
mask1: ~(0...010...0) = (1..101..1) , cu i biti de 1 in coada
mask2: (0...0v0...0), cu i biti de 0 in coada
num & mask1 => pastreaza num asa cum e, mai putin bitul i care este curatat
| mask2 => modifica bitul i cu 1 daca v = 1, sau il lasa curatat daca v = 0


Si acum problemele propuse:

* N, M sunt doua numere pe 32 de biti. Se dau doua pozitii i si j. Sa se insereze M in N astfel incat M sa inceapa de la bitul j si sa se termine la bitul i din N.

Sol.: 
- creeaza o masca pe 32 de biti a.i. pozitiile > j (la stanga) si cele < i (la dreapta) sa fie 1, iar spatiul intre bitii i si j inclusiv sunt 0:
int left = (~ 0) << (j+1);    // 11....1 << (j+1)  =  11..10....0 , cu 0 de j+1 ori pt ca right most are poz. 0
int right = (( 1 << i) - 1);  //  (10...0) - 1 = 0...01..1 , cu i biti de 1 in coada
int mask = left | right;      //  "join"

- aplica masca pentru a curata portiunea dorita din N:
int cleared = N & mask;

- creeaza un M' care, la fel ca si masca, are pozitiile din afara sirului j->i cu 0, si portiunea dinauntru este copia lui M:
int m = M << i;  // M00...0 , cu i zero-uri 

- rezultatul va fi:    return cleared | m;


* Se da un numar real intre 0 si 1. Sa se scrie reprezentarea binara a acestuia sau eroare daca nu este posibil.

Sol.: Aceasta este o problema clasica de introducere in informatica.
Se ia un exemplu in baza 2:
0.101 = 1 * (1/2^1) + 0 * (1/2^2) + 1 * (1/2^3)
Ne trebuie operatia inversa: inmultire cu 2

String printBinary (double num) {
  if ( num >= 1 || num <= 0) return "error";
  StringBuilder sb = new StringBuilder().append(".");
  while ( num > 0 ) {
    if (binary.length() >= 32) return "error";
    double r = num * 2;
    if (r >= 1) { binary.append(1); num = r-1; }
    else { binary.append(0); num = r; }
  }
  return binary.toString(); }

ex. numarul 0.625 
r = 1.25 => binary = .1 , num = 0.25
r = 0.5   => binary = .10 , num = 0.5
r = 1      => binary = .101  , num = 0


* O functie care sa determine nr. de biti necesari pentru a converti un nr. intreg A la un nr. intreg B

int bits (int A, int B) {
  int xor = A ^ B; int cnt = 0;
  while (xor != 0) {
    if (xor & 1) cnt++;  // daca xor nu e in intregime 0
    xor = xor >> 1;       // se taie bitul din coada, deplasare la dreapta
  }
  return cnt; }


* Sa se interschimbe bitii de pe pozitiile pare si impare astfel: bit 0 cu bit 1, bit 2 cu bit 3, samd... in cat mai putine instructiuni posibile.

Sol.: 
- se ia numarul x si se face o masca a.i. toti bitii de pe pozitii impare sunt 1, restul sunt 0
Daca nr. ar avea 8 biti, masca ar arata 10101010, reprezentat ca AA in baza 16. Fiind un intreg de 32 biti, in hexazecimal arata: 0xaaaaaaaa  (de 8 ori A) 
int mask1 = 0xaaaaaaaa;
int left = (x & mask1) >> 1;  // pozitiile impare se muta pe pozitiile pare (ex. bitul 3 peste bitul 2, etc)
- se face o alta masca a.i. toti bitii de pe pozitiile pare sunt 1, restul 0
Masca ar arata gen: 01010101 , adica 55 in baza 16.
int mask2 = 0x55555555;
int right = (x & mask2) << 1; // pozitiile pare se muta peste cele impare, la stanga (ex. bitul 2 peste bitul 3, etc) 
- rezultatul final este:  left | right ;


* Se da un sir A in care toate elementele sunt intregi distincte de la 0... n mai putin un element care lipseste :) Singurul mod in care se poate accesa un intreg este printr-o operatie "binara": fetch(i, j) = bitul j din A[i] . Aflati elementul lipsa, in O(N).

Sol1: S = n*(n+1)/2 , S' se poate afla parcurgand sirul => elementul lipsa este S-S' , dar complexitatea este O (n * log n) , cu log n = lungimea lui n, nr. de biti pe care sunt repr. elementele (desi mie imi suna a constanta, 32 biti pt int)

Sol2: operatii pe biti. Se face un desen cu un exemplu. Se ia pozitie cu pozitie, ce se intampla la o eventuala suma, de la rangul cel mai mic la cel mai mare. In primul rand, daca n este par, vom vedea cifra "unitatilor" ca fiind 0, 1, 0, 1, .... , 0 , deci nr. de 0-uri = 1 + nr. de biti 1. Daca n este impar, nr. de 0-uri si 1-uri sunt egale. Astfel se poate deduce bitul cel mai putin semnificativ. Solutia sugereaza acest procedeu pentru toti bitii, ceea ce mie mi se pare de aceeasi complexitate ca in sol. 1. Alte idei gasiti si aici.


---------------------------- cap. 6 - brain teasers --------------------------------------------------------

Aceste probleme se pot numi si de logica / matematica aplicata / gandire si aduc putin aminte de concursul Cangurul.

* avem 2 franghii, fiecare poate arde o ora. Densitatea unei franghii variaza, deci o jumatate nu arde neaparat intr-o jumatate de ora. Cum numaram 15 minute?

Sol.: o franghie, daca o ardem la ambele capete, va arde in 30 minute. O franghie, daca stim sigur ca a ars jumatate din timp (fiind arsa doar la un capat) si apoi o ardem si la celalalt capat, va arde inca 15 minute pana e gata. Asadar: dam foc la ambele capete ale primei franghii si la un singur capat al celei de-a doua. Cand prima se consuma, dam foc si la celalalt capat al celei de-a doua si atunci incepe minutul 0. Cand se consuma si aceasta, vor fi trecut 15 minute.


* avem 9 mingii, 8 au aceeasi greutate, una este un pic mai grea. O balanta spune daca partea stanga sau dreapta este mai grea. Cu 2 utilizari ale balantei, sa se afle bila grea.

Sol.: se iau 3 + 3 mingii si se cantaresc. 
Daca sunt diferite, se iau cele 3 mai grele, se aleg 2 dintre ele si se cantaresc. Daca sunt egale, cea de-a 3-a este bila grea, altfel, se ia bila care a iesit mai grea.
Altfel, daca sunt egale, se iau celelalte 3 bile puse deoparte si se repeta procedeul se mai sus (se aleg 2... )


* avem 20 de sticle cu medicamente, 19 sticle au pastile de fix 1 gram, ultima are pastile de 1.1 grame. Un cantar arata greutatea exacta, dar poate fi folosit o singura data. Cum se poate determina care este sticla cu pastilele cele mai grele?

Sol.: daca cantarul se poate folosi o singura data, inseamna ca trebuie cantarite cel putin 19 sticle odata (sau ceva din continutul lor). Se ia un exemplu cu 2 sticle. Nu putem pune o sticla si alta pe ambele parti ale balantei pt ca nu stim daca au nr egal de pastile. Dar putem lua o pastila din prima si 2 din a doua sticla si astfel putem obtine:
  1 + 2 = 3 g daca sticlele sunt normale
  1.1 + 2 = 3.1 g daca prima sticla are medicamente mai grele
  1 + 2.2 = 3.2 g daca a doua ...
Astfel, pentru 20 de sticle, luam 1 pastila din prima, 2 pastile din a doua.... 20 de pastile din a treia. Stim ca ar trebui sa obtinem (1 + 2 + ... + 20) daca sticlele ar fi toate la fel. In schimb, cantarul va arata mai mult, si facem diferenta. Stim ca surplusul este (1.1 - 1) * k, unde k este indicele sticlei, asadar 0.1 * k = diferenta si aflam k.


* O tabla de sah 8 x 8 in care s-au taiat 2 colturi diagonal opuse. Se dau 31 piese de domino, in care un domino poate acoperi 2 patratele. Intrebarea este daca se pot folosi toate cele 31 piese pentru a acoperi complet tabla?

Sol.: in primul rand, o piesa de domino care ocupa 2 patratele adiacente inseamna ca ocupa un patratel alb si unul negru. Pentru 31 piese => tabla ar trebui sa aiba cel putin 31 patratele albe si 31 negre. Dar 2 colturi care erau de aceeasi culoare s-au indepartat. Tabla are 64-2 = 62 patratele, dar nr. de patratele albe nu e egal cu cel de negre. Asadar, piesele nu pot acoperi tabla.


* Niste oameni rationali traiesc pe o insula, unde un vizitator vine cu o porunca ciudata: toti oamenii cu ochii albastri trebuie sa paraseasca insula cat mai curand. Exista un zbor pe zi. Fiecare persoana vede ochii celorlalti, dar nu ii poate vedea pe ai sai, si nici nu are voie sa afle. Nimeni nu stie exact cati oameni au ochii albastri, desi se stie ca exista cel putin 1 persoana. Cate zile le vor lua oamenilor in cauza sa paraseasca insula?

Sol.: Se ia pe cazuri in functie de cate persoane cu ochii albastri sunt.
> c = 1 persoana. Se uita la toti ceilalti si vede ca nu exista nimeni cu ochii albastri, deduce ca e singura care ar trebui sa aiba ochii albastri, ia avionul si pleaca din prima zi.
> c = 2 persoane. In prima zi cei doi se uita in jur si vad o singura persoana cu ochii albastri. Asteapta ca ea sa plece din prima zi, dar acest lucru nu se intampla, pt ca fiecare ramane pe insula in asteptarea celuilalt. A doua zi, amandoi isi da seama ca se afla in cazul c = 2 si pleaca cu avionul.
Despre ceilalti: se uita in jur si observa ca exista doua persoane cu ochii albastri. A doua zi ii vad plecand si isi dau seama ca se afla in cazul 2.
> c = 3 persoane. Cei 3 se uita in jur si vad ca exista 2 persoane cu ochii albastri. Nu fac nimic in prima zi pentru ca stiu ca nu este cazul 1. In a doua zi nu ii vad plecand pe ceilalti 2, deci isi dau seama ca c > 2 si cum nu vad decat alti 2 cu ochii albastri, isi dau seama ca ei sunt a treia. Pleaca imediat in a treia zi. Despre ceilalti: vad de la inceput 3 oameni cu ochi albastri, asteapta o zi, doua, in a treia ii vad plecand, si ofteaza usurati.
> caz general: daca exista N oameni cu ochii albastri, le va lua N zile sa paraseasca insula


* Intr-o sala de sport avem 100 lacatele incuiate. Un paznic vine si le deschide pe toate. A doua oara, paznicul vine si le inchide din 2 in 2. Apoi vine si schimba starea lacatelului din 3 in 3, 4 in 4, tot asa pana la 100. Cate lacatele descuiate vor fi la sfarsit?

Sol.: O intrebare tipic "Cangurul". Se poate lua un exemplu, din care se poate observa ca:
lacat 1: sta deschis
lacat 2: deschis + inchis => inchis
lacat 3: deschis + ___ + inchis => inchis
lacat 4: deschis + inchis +  ____ + deschis => deschis
Pozitiile ____ sunt pt ca nr. lacatului nu a fost divizibil cu runda de trecere a paznicului, deci paznicul nu a atins lacatul. In final, se poate observa ca nr. de treceri reprezinta nr. de divizori al nr. de ordine al lacatului: 1 {1}, 2 {1, 2} , 3 {1, 3} , 4 {1, 2, 4} , iar lacatele ramase deschise sunt cele ale caror nr. de ordine are nr. impar de divizori. Aceste numere sunt patratele perfecte. Asadar, pana la 100 exista 10 patrate perfecte.


Probleme asemanatoare "brain teasers" am citit si aici. Unele sunt incluse chiar in acest post.

Niciun comentariu: