Entretiens d'embauche chez Google
Entretiens d'embauche chez Google
Question 1:
Comment trouver le premier caractère en double dans une chaîne de caractère ?
Par exemple dans cette chaine, le premier caractère en double est le (pas le A) mais le D !! (merci Marc)
Chaine$="POABCDEFTHLGDSALKL"
Il y a évidemment deux solutions, une naïve (qui vous vient déjà à l'esprit, ne niez pas ! ) en O(n²) et une plus efficace en O(n).
Jouez honnêtement le jeu, vous avez 30 secondes pour y réfléchir...
Du coup, on se dit qu'on devrait postuler, non ?
Comment trouver le premier caractère en double dans une chaîne de caractère ?
Par exemple dans cette chaine, le premier caractère en double est le (pas le A) mais le D !! (merci Marc)
Chaine$="POABCDEFTHLGDSALKL"
Il y a évidemment deux solutions, une naïve (qui vous vient déjà à l'esprit, ne niez pas ! ) en O(n²) et une plus efficace en O(n).
Jouez honnêtement le jeu, vous avez 30 secondes pour y réfléchir...
Du coup, on se dit qu'on devrait postuler, non ?
Dernière modification par Fig le jeu. 29/mars/2018 18:56, modifié 3 fois.
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits
Re: Entretien d'embauche téléphonique chez Google
Code : Tout sélectionner
Chaine$="POABCDEFTHLGDSALKL"
Dim c(255)
For i=1 To Len(Chaine$)
a=Asc(Mid(chaine$,i,1))
c(a)+1
If c(a)=2:Debug Chr(a):End:EndIf
Next
Re: Entretien d'embauche téléphonique chez Google
Embauché !
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits
Re: Entretien d'embauche téléphonique chez Google
connaissent pas mes prétentions salariales !!
Re: Entretien d'embauche téléphonique chez Google
Pour aller plus vite :
http://www.purebasic.fr/french/viewtopi ... =6&t=16276
Il y a les SSE mais j'ai ommis où j'ai mis ça. C'est dans la section ASM. Ipistri ou Champistri, je sais plus...
And... Yea ! When Google becomes nake, Google becomes my friend ! A poil mon pote ! Rock n Roll !
Au fait... Mais... A qui profite le criiiii....
.....
...
(votre correspond s'est pris la comète "Tagoul 937" et c'est bien dommage pour lui, prends-en de la graine!)
...
http://www.purebasic.fr/french/viewtopi ... =6&t=16276
Il y a les SSE mais j'ai ommis où j'ai mis ça. C'est dans la section ASM. Ipistri ou Champistri, je sais plus...
And... Yea ! When Google becomes nake, Google becomes my friend ! A poil mon pote ! Rock n Roll !
Au fait... Mais... A qui profite le criiiii....
.....
...
(votre correspond s'est pris la comète "Tagoul 937" et c'est bien dommage pour lui, prends-en de la graine!)
...
Re: Entretien d'embauche téléphonique chez Google
Ça dépend comment on perçoit le premier du double.Comment trouver le premier caractère en double dans une chaîne de caractère ?
Par exemple dans cette chaine, le premier caractère en double est le A
Chaine$="POABCDEFTHLGDSALKL"
D'après le programme de Guillot et la logique pure, c'est D et pas A
P O A B C D E F T H L G D S A L K L
Voilà ma version (Code moche première fois que j'utilise une map)
Code : Tout sélectionner
Chaine$="POABCDEFTHLGDSALKL"
Debug "Chaine à traiter: " + Chaine$
NewMap Lettre.s()
For i = 1 To Len(Chaine$)
Caratere.s = Mid(Chaine$, i, 1)
Debug "#" + RSet(Str(i), 2, " ") + " -> " + Caratere
If FindMapElement(Lettre(), Caratere)
Debug "------ " + Caratere + " existe déjà !"
Else
AddMapElement(Lettre(), Mid(Chaine$, i, 1), #PB_Map_NoElementCheck)
EndIf
Next
Code : Tout sélectionner
Chaine à traiter: POABCDEFTHLGDSALKL
# 1 -> P
# 2 -> O
# 3 -> A
# 4 -> B
# 5 -> C
# 6 -> D
# 7 -> E
# 8 -> F
# 9 -> T
#10 -> H
#11 -> L
#12 -> G
#13 -> D
------ D existe déjà !
#14 -> S
#15 -> A
------ A existe déjà !
#16 -> L
------ L existe déjà !
#17 -> K
#18 -> L
------ L existe déjà !
Si la liste de référence est déjà construite, alors c'est effectivement le A qui sera vu en premier.
(mais j'ai toujours été nul en math, c'est pourquoi je n'ai pas compris le O(n²) et O(n) qui expriment sans doute cela d'une manière abstraite ?)
Re: Entretien d'embauche téléphonique chez Google
Bonjour,
Une autre version possible :
Cordialement,
GallyHC
Une autre version possible :
Code : Tout sélectionner
EnableExplicit
Define.l i
Define.s temp, char = "POABCDEFTHLGDSALKL"
For i=1 To Len(char) - 1
temp = Mid(char, i, 1)
If FindString(char, temp, i + 1) > 0
Debug temp
Break
EndIf
Next i
GallyHC
Configuration : Tower: Windows 10 (Processeur: i7 "x64") (Mémoire: 16Go) (GeForce GTX 760 - 2Go) - PureBasic 5.72 (x86 et x64)
Re: Entretien d'embauche téléphonique chez Google
Un peu plus de lignes..
Code : Tout sélectionner
Global NewList lettre.s()
Global char.s = "POABCDEFTHLGDSALKL"
For i=1 To Len(char) - 1 : AddElement (lettre()) : lettre() = Mid(char, i, 1) : Next i
SortList(Lettre(), #PB_Sort_Ascending)
For i=0 To Len(char) - 3
SelectElement(lettre(),i)
car1.s = lettre()
SelectElement(lettre(),i+1)
car2.s = lettre()
If car1 = car2 : compte +1 : Debug "1er double trouvé : "+car1 : Break : EndIf
Next
~~~~Règles du forum ~~~~
⋅.˳˳.⋅ॱ˙˙ॱ⋅.˳Ar-S ˳.⋅ॱ˙˙ॱ⋅.˳˳.⋅
W11x64 PB 6.x
Section HORS SUJET : ICI
LDV MULTIMEDIA : Dépannage informatique & mes Logiciels PB
UPLOAD D'IMAGES : Uploader des images de vos logiciels
⋅.˳˳.⋅ॱ˙˙ॱ⋅.˳Ar-S ˳.⋅ॱ˙˙ॱ⋅.˳˳.⋅
W11x64 PB 6.x
Section HORS SUJET : ICI
LDV MULTIMEDIA : Dépannage informatique & mes Logiciels PB
UPLOAD D'IMAGES : Uploader des images de vos logiciels
Re: Entretien d'embauche téléphonique chez Google
Marc, tu as raison dans mon exemple c'est la lettre D qui est attendu et non le A comme je l'avais écrit.
Concernant la notation "Big O", ce n'est pas très compliqué mais fondamentale pour l'analyse de la vitesse des algorithmes indépendamment de l'implémentation.
http://bigocheatsheet.com/
Par exemple si tu dois examiner chaque élément d'une liste pour trouver la réponse à un problème, ton algo est de type O(n) cad que plus il y a d'éléments dans la liste (n éléments) plus ça sera proportionnellement long. C'est une droite.
Si pour chaque élément de la liste tu dois le comparer à chacun des autres éléments de cette même liste, tu fera n² itérations (soit une double boucle imbriquée). Dans ce cas, la courbe est quadratique au nombre d’éléments de la liste O(n²).
Cherche un élément en mémoire prend en moyenne un temps constant donc O(1)
Etc...
Selon le type d’algorithme et selon le nombre d’éléments traités, le but est de trouver un algo qui est calculable en un temps raisonnable.
Quelques exemples, en abscisse le nombre d'éléments, en ordonnée, le temps de traitement.
La réponse de GallyHC est O(n²) car chaque élément est comparé à tous les autres (la fonction findstring est une boucle en fait), la tienne O(n).
Celle de Ars qui utilise le tri des listes est O(n log n) -pour simplifier, mais en fait pire à cause des deux autres boucles-, en effet, le tri des listes chainées en Pb est un tri par fusion (il me semble).
Si il y a une complexité forte, ça reste acceptable dans la mesure où on traite peu d'éléments.
Concernant la notation "Big O", ce n'est pas très compliqué mais fondamentale pour l'analyse de la vitesse des algorithmes indépendamment de l'implémentation.
http://bigocheatsheet.com/
Par exemple si tu dois examiner chaque élément d'une liste pour trouver la réponse à un problème, ton algo est de type O(n) cad que plus il y a d'éléments dans la liste (n éléments) plus ça sera proportionnellement long. C'est une droite.
Si pour chaque élément de la liste tu dois le comparer à chacun des autres éléments de cette même liste, tu fera n² itérations (soit une double boucle imbriquée). Dans ce cas, la courbe est quadratique au nombre d’éléments de la liste O(n²).
Cherche un élément en mémoire prend en moyenne un temps constant donc O(1)
Etc...
Selon le type d’algorithme et selon le nombre d’éléments traités, le but est de trouver un algo qui est calculable en un temps raisonnable.
Quelques exemples, en abscisse le nombre d'éléments, en ordonnée, le temps de traitement.
La réponse de GallyHC est O(n²) car chaque élément est comparé à tous les autres (la fonction findstring est une boucle en fait), la tienne O(n).
Celle de Ars qui utilise le tri des listes est O(n log n) -pour simplifier, mais en fait pire à cause des deux autres boucles-, en effet, le tri des listes chainées en Pb est un tri par fusion (il me semble).
Si il y a une complexité forte, ça reste acceptable dans la mesure où on traite peu d'éléments.
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
Version de PB : 6.00LTS - 64 bits
Re: Entretien d'embauche téléphonique chez Google
Ah du coup j'avais mal lu l'énoncé, mon code trouve les premières lettre en double mais pas celles qui apparaissent dans la liste en 1er
~~~~Règles du forum ~~~~
⋅.˳˳.⋅ॱ˙˙ॱ⋅.˳Ar-S ˳.⋅ॱ˙˙ॱ⋅.˳˳.⋅
W11x64 PB 6.x
Section HORS SUJET : ICI
LDV MULTIMEDIA : Dépannage informatique & mes Logiciels PB
UPLOAD D'IMAGES : Uploader des images de vos logiciels
⋅.˳˳.⋅ॱ˙˙ॱ⋅.˳Ar-S ˳.⋅ॱ˙˙ॱ⋅.˳˳.⋅
W11x64 PB 6.x
Section HORS SUJET : ICI
LDV MULTIMEDIA : Dépannage informatique & mes Logiciels PB
UPLOAD D'IMAGES : Uploader des images de vos logiciels
Re: Entretien d'embauche téléphonique chez Google
Et dire que j'ai fais ça sans rien y comprendre
Je me suis simplement dit que comme les Maps refusent les doublons, il suffit de remplir avec chaque caractère et d'attendre le message d'erreur
(j'ai honte de ma logique cheap de vieux codeur autodidacte )
Je me suis simplement dit que comme les Maps refusent les doublons, il suffit de remplir avec chaque caractère et d'attendre le message d'erreur
(j'ai honte de ma logique cheap de vieux codeur autodidacte )
Re: Entretien d'embauche téléphonique chez Google
Code de Gally modifié pour prendre en compte le premier doublon tel qu'on l'attend:
Code : Tout sélectionner
EnableExplicit
Define.l i, position, mem=65535
Define.s temp, first, char = "POABCDEFTHLGDSALKL"
For i=1 To Len(char) - 1
temp = Mid(char, i, 1)
position = FindString(char, temp, i + 1)
If position > 0
Debug temp
If position<mem
mem=position
first = temp
EndIf
EndIf
Next i
Debug "-----------------------------"
Debug mem
Debug first
Re: Entretien d'embauche téléphonique chez Google
Ma contribution :
Aucune idee du temps qu'elle met...
Code : Tout sélectionner
chaine$="POABCDEFTHLGDSALKL"
Dim c.b(90)
For i=1 To Len(chaine$)
c(Asc(Mid(chaine$,i,1)))+1
If c(Asc(Mid(chaine$,i,1)))>1
Debug Mid(chaine$,i,1)
End
EndIf
Next
http://HexaScrabble.com/
!i!i!i!i!i!i!i!i!i!
!i!i!i!i!i!i!
!i!i!i!
//// Informations ////
Intel Core i7 4770 64 bits - GTX 650 Ti
Version de PB : 6.00 - 64 bits
!i!i!i!i!i!i!i!i!i!
!i!i!i!i!i!i!
!i!i!i!
//// Informations ////
Intel Core i7 4770 64 bits - GTX 650 Ti
Version de PB : 6.00 - 64 bits
Re: Entretien d'embauche téléphonique chez Google
La version de Nico simplifié ^^ (pour le première version, j'avais surement mal compris) :
Cordialement,
GallyHC
Code : Tout sélectionner
EnableExplicit
Define.s temp, char = "POABCDEFTHLGDSALKL"
Define.l i, lpos, lmem = Len(char)
For i=1 To Len(char) - 1
temp = Mid(char, i, 1)
lpos = FindString(char, temp, i + 1)
If lpos > 0 And lpos < lmem
lmem = lpos
EndIf
Next i
If lmem > 0
Debug Mid(char, lmem, 1)
EndIf
GallyHC
Configuration : Tower: Windows 10 (Processeur: i7 "x64") (Mémoire: 16Go) (GeForce GTX 760 - 2Go) - PureBasic 5.72 (x86 et x64)
Re: Entretien d'embauche téléphonique chez Google
Non c'est pas le D c'est la A
Code : Tout sélectionner
Chaine$="POABCDEFTHLGDSALKL"
For i = 1 To Len(Chaine$)
txt$ = Mid(Chaine$, i, 1)
a.a = CountString(Chaine$, txt$)
If a= 2 : Debug txt$ : End : EndIf
Next i