INTERWIEV QUESTION

Quando si entra a far parte del mondo del lavoro inevitabilmente dovranno essere sostenuti dei colloqui lavorativi. Tra le principali aziende informatiche troviamo Amazon, Google, Apple, Microsoft, IBM ecc… Tutte queste aziende richiedono una profonda conoscenza dei linguaggi di programmazione, perciò durante l’intervista non deve sorprendere se alcune delle domande più frequenti riguardano proprio la programmazione. Tra queste troviamo 4 domande a cui cercheremo di rispondere in modo semplice e completo in questo articolo.

La prima domanda è determinare il valore LSB (Less Significative Bit) di un numero qualunque N. Il valore LSB non è altro che il valore che assume l’ultimo bit a destra. Ovviamente, essendo il linguaggio macchina un linguaggio binario, tale bit potrà assumere valore 0 o 1. Riuscendo a stabilire questo valore sarà possibile definire se un numero dato è pari o dispari, per questo motivo questo problema risulta essere molto importante. Per riuscire a risolvere questo problema è possibile utilizzare l’operatore bitwise And visto nell’articolo precedente. Ricordiamo che gli operatori bitwise sono dei particolari operatori che permettono di effettuare operazioni bit per bit; in questo caso particolare l’operatore And restituisce il valore 1, o True, solo se entrambi gli operandi assumono valore 1. E’ facile capire quindi che per risolvere il nostro problema basta utilizzare come secondo operando il numero 1. In questo caso infatti l’operazione avrebbe come risultato 1 se anche l’ultimo bit del nostro numero N vale 1 (quindi il numero è dispari), mentre si otterrebbe 0 se l’ultimo bit di N vale 0 (quindi N è pari). Vediamo come implementare il ragionamento appena fatto in VB.NET creando una funzione che restituisce True se il numero N è pari e False se è dispari.

Private Function IsPari(N as Integer) As Boolean
 If((N And 1) = 0) Then
  Return True
 Else
  Return False
 End If
End Function

Una seconda domanda molto comune nei colloqui di lavoro delle aziende informatiche è risolvere il problema del conteggio del numero di bit in un numero N qualsiasi. Una semplice risposta potrebbe essere quella di studiare il valore del bit più a destra e poi shiftare di una posizione verso destra tutti i bit fino a quando non si arriverà al numero 0. Per poter studiare l’ultimo bit basterà utilizzare l’operazione vista in precedenza. Questo algoritmo, che possiamo definire “naive”, esegue n iterazioni, dove n è il numero di bit totali che compongono N. Un algoritmo sicuramente più efficiente è l’algoritmo di Kernighan. Tale algoritmo sfrutta la relazione che c’è tra N e (N-1); infatti l’operazione N And (N-1) causa l’azzeramento del primo bit di N uguale a 1 da destra. Inserendo questa relazione in un ciclo sarà possibile infatti azzerare tutti i bit pari a 1 fino ad arrivare al numero 0. Questo secondo algoritmo utilizza m iterazioni, dove m equivale al numero di bit pari a 1, perciò m sarà minore o al massimo uguale a n.

// algoritmo naive

Private Function SommaBit(N As Integer) As Integer
 Dim Contatore As Integer = 0
 Do While N <> 0 
   Dim ValoreRightMostBit As Integer = N And 1
   Contatore += ValoreRightMostBit
   N >>= 1
 Loop
End Function


//algoritmo di Kernighan

Private Function Kernighan (N As Integer) As Integer
 Dim Contatore As Integer = 0
 Do While N <> 0
   N = N And (N-1)
   Contatore += 1
 Loop
 Return Contatore
End Function

La terza domanda molto frequente è testare se un qualsiasi numero n sia o meno potenza di 2. Se il numero scritto in linguaggio binario è formato da tutti valori 0 e un solo valore 1 è facile intuire che tale numero è proprio una potenza di 2. Se così non fosse si potrebbe essere interessati al più vicino numero dispari maggiore od uguale a N. Per risolvere quest’ultimo problema basta utilizzare l’operatore Or che, ricordiamo, restituisce True se uno dei due o entrambi gli operandi sono True. In questo caso ponendo N Or 1 si ottiene proprio il più vicino numero dispari maggiore od uguale a N. Vediamo ora l’implementazione di una funzione che restituisce True se il numero passato come argomento è potenza di 2.

Private Function IsPowerOf2(N As Integer) As Boolean
 If (N And (N-1)) = 0 Then
  Return True
 Else
  Return False
 End If
End Function

Un ultimo problema da risolvere è trovare la più grande potenza di 2 che divide un numero qualunque N. Ad esempio, se N è pari a 12 si vuole come risultato 2^2 con residuo 3. Innanzitutto notiamo che se il numero analizzato è dispari la massima potenza di 2 è 0. Studiando la scrittura in linguaggio binario si può facilmente notare che la massima potenza di risulta essere proprio la posizione del bit uguale a 1 più a destra. Si devono perciò porre pari a 0 tutti i bit a sinistra del primo bit uguale a 1 da destra. Per fare questo si può utilizzare la relazione tra N e (N-1), ma negando quest’ultimo operando attraverso l’operatore unary Not poiché i due numeri risultano essere uguali a sinistra del primo valore 1 e opposti alla sua destra. Vediamo come implementare questa semplice funzione.

Private Function MaxPowerOfTwo(N As Integer) As Integer
 Return N And Not (N-1)
End Function