Test d'Embauche Google

MoKeS

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

Draken

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

AliGator

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 ^^

zoc

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

Draken

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.."

MoKeS

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