›

Test d'Embauche Google

MoKeSMoKeS Membre
avril 2015 modifié dans Coin canapé & détente #1

Bonjour à  tous,


 


Je ne sais pas si c'est la bonne section du forum pour poster cela.


 


Un ami à  moi a passé récemment un test technique pour entrer chez Google, et je pensais que ça pouvait être intéressant de vous le partager. Vous allez voir, c'est assez .. hum .. funky : 




Write a function to validate a UTF-8 string.

UTF-8 is a variable-length encoding of runes. If the most significant bit of the first

byte is 0, the rune is 1 byte long. Otherwise, its length is the number of leading

1s in the first byte. If a rune is more than one byte long,

all subsequent runes start with 10. Here is a chart:

byte (in binary)

0XXXXXXX = this is the entire rune

10XXXXXX = this is a continuation of the rune from the previous byte

110XXXXX = this is the start of a 2-byte rune.

1110XXXX = this is the start of a 3-byte rune.

11110XXX = this is the start of a 4-byte rune.

111110XX = this is the start of a 5-byte rune.

1111110X = this is the start of a 6-byte rune.

11111110 = this is the start of a 7-byte rune.

11111111 = this is the start of a 8-byte rune.

10110011  → False (continuation, no start)

11011001  → False (only 1 byte)

11011001 10110111  -> True (2 byte rune)

11011001 10110111 11111001 10110111 10110111 10100011 10110111 -> True (2-byte + 5-byte) string.

Ce test est à  faire sur un google docs, dans n'importe quel language, en utilisant la récursivité et ah oui ... en 15 minutes maximum ! 


 


Si vous voulez essayer de jouer le jeu ? 


 


 


MoKeS


Mots clés:

Réponses

  • DrakenDraken Membre
    #2

    Pfff .. c'est facile. La réponse c'est .. 42 !

  • AliGatorAliGator Membre, Modérateur
    avril 2015 modifié #3
    Pour le plaisir de tester ça en Swift :

    
typealias Byte = Int
    

    
enum ByteType
    
{
    
case FullRune     // 0XXXXXXX
    
case Continuation // 10XXXXXX
    
case MultiByteRune(size: Int) // 111...0XXX...
    

    
init(byte: Byte)
    
{
    
if byte & 0b10000000 == 0
    
{
    
self = FullRune
    
}
    
else if byte & 0b11000000 == 0b10000000
    
{
    
self = Continuation
    
}
    
else
    
{
    
var b = byte
    
var n = 0
    
while (b & 0b10000000 != 0)
    
{
    
n += 1
    
b <<= 1
    
}
    
self = MultiByteRune(size: n)
    
}
    
}
    
}
    

    
func parseBytes(bytes: [Byte]) -> Bool
    
{
    
var nextExpected = 0
    
for b in bytes {
    
let t = ByteType(byte: b)
    
println("byte type = \(t)")
    
switch(t) {
    
case .FullRune:
    
if nextExpected > 0 { return false }
    
nextExpected = 0
    
case .Continuation:
    
if nextExpected == 0 { return false }
    
nextExpected -= 1
    
case .MultiByteRune(size: let size):
    
if nextExpected > 0 { return false }
    
nextExpected = size-1
    
}
    
println("--> nextExpected = \(nextExpected)")
    
}
    
return nextExpected == 0
    
}
    

    

    

    
let test1 = [0b10110011] // False (continuation, no start)
    
let test2 = [0b11011001] // False (only 1 byte)
    
let test3 = [0b11011001, 0b10110111] // True (2 byte rune)
    
let test4 = [0b11011001, 0b10110111, 0b11111001, 0b10110111, 0b10110111, 0b10100011, 0b10110111] //  True (2-byte + 5-byte) string.
    
parseBytes(test1)
    
parseBytes(test2)
    
parseBytes(test3)
    
parseBytes(test4)
    Bon par contre j'ai fait ça dans un Playground pas dans un doc, donc c'est un peu tricher ^^
  • zoczoc Membre
    #4

    Récursivité obligatoire le monsieur il a dit  >:D


  • DrakenDraken Membre
    #5


    Ce test est à  faire sur un google docs, dans n'importe quel language, en utilisant la récursivité et ah oui ... en 15 minutes maximum ! 


     




    C'est des minutes ordinaires ou des minutes d'informaticiens ? La différence est parfois .. conséquente ! 


    "Oui chef, plus que 15 minutes avant de finir ce projet.."

  • MoKeSMoKeS Membre
    #6

    Non c'était vraiment 15 vraies minutes :-).


     


    Je vous colle ce que mon pote a rendu en 15 minutes : 



    
- (void)testNegativeWrongHeaderByteUTF8String
    
{
    
[self assert:[NSString isValidUTF8String:[10110011] equals:NO];
    
}
    

    
- (void)testNegativeWrongRuneHeaderByteUTF8String
    
{
    
[self assert:[NSString isValidUTF8String:[11011001] equals:NO];
    
}
    

    
- (void)testNegativeWrongCountRuneHeaderByteUTF8String
    
{
    
[self assert:[NSString isValidUTF8String:[11011001, 10011001, 10011001] equals:NO];
    
}
    

    
- (void)testNegativeWrongMultipleRuneHeaderByteUTF8String
    
{
    
[self assert:[NSString isValidUTF8String:[11011001 10110111 11110001 10110111 10110111 10100011 10110111] equals:NO];
    
}
    

    
- (void)testPositiveEntireRuneUTF8String
    
{
    
[self assert:[NSString isValidUTF8String:[01111111b] equals:YES];
    
}
    

    
- (void)testPositive2BytesUTF8String
    
{
    
[self assert:[NSString isValidUTF8String:[11011001b, 10110111b] equals:YES];
    
}
    

    
- (void)testPositiveMultipleRunesUTF8String
    
{
    
[self assert:[NSString isValidUTF8String:[11011001b, 10110111 11111001 10110111 10110111 10100011 10110111] equals:YES];
    
}
    

    
- (void)testNegativeEmptyUTF8String
    
{
    
[self assert:[NSString isValidUTF8String:[] equals:NO];
    
}
    

    
- (NSArray *)getBytesArrayFromByte:(unsigned)aByte
    
{
    

    
}
    

    
- (BOOL)isValidUTF8String:(NSArray*)bytesArray
    
{
    
if (![bytesArray count])
    
return NO;
    
int i = 0;
    

    
NSArray *bytesArray = [self getBytesArrayFromByte:[bytesArray objectAtIndex:0]];
    

    
while ([bytesArray objectAtIndex:i] == 1)
    
i++;
    
for (int j = 1; j < i - 1; j++)
    
{
    
var byte = [bytesArray objectAtIndex:j];
    

    
if ([byte objectAtIndex:0] != 1 || [byte objectAtIndex:1] != 0)
    
return NO;
    
}
    

    
if ([bytesArray count] == i && i > 1 || [bytesArray objectAtIndex:0] == 0 && [bytesArray count] == 1)
    
return YES;
    

    
if ([bytesArray count] <= i)
    
return NO;
    

    
BOOL otherParth = [self isValidUTF8String:[bytesArray objectAtIndexes:[NSINdexSet indexSetWithInt:i, [bytesArray count]]];
    

    

    
return otherParth;
    
}

    Il manque quelques accolades par ci par là , mais on va dire que la vitesse a induit quelques coquilles :-).


    Il n'a pas encore eu la réponse de son entretien ! 


     


    Personnellement j'ai mis 15 minutes à  comprendre le sujet :-P

Connectez-vous ou Inscrivez-vous pour répondre.