Reprise du message précédent :

J’attends de voir comment nos grands démocrates de dirigeants vont justifier leur inévitable opposition à cette décision.

 
Ok, on ne vit pas sur la même planète manifestement.

u mad stock exchange?  

Petite question à une interview où j'ai spectaculairement failé:
Soit une liste de points(int x,int y) disposés sur un plan, trouver le plus long alignement (en nombre de points alignés). Pas été foutu de sortir un algorithme qui marche, même modérément performant. Ch'uis vraiment rouillé

BRotip: use magnetz

Un truc genre "trouver la fonction affine y=ax+b vraie pour le plus grand nombre de point" ? Les maths c'est loin voire ça n'a jamais été là pour moi mais si tu peux déduire à partir de deux points une telle fonction c'est facile ensuite de tester quels autres points la vérifie.
 
/approche naive off

la plus naïve c'est de prendre toutes les paires de points, calculer l'équation de la droite qu'ils forment et de compter le nombre de points en plus que tu peux attraper dessus. C'est en n^3, mais c'est une première réponse.

C'est pas le problème de savoir si 3 points sont alignés, disons qu'on a une fonction qui fait ça (avec le produit scalaire je pense), le problème, c'est l'algo général.

C'est ce que j'ai essayé de faire, sans chercher l'équation de la droite, mais en tentant une liste de points alignés, et j'ai pas été foutu de le faire. Il aurait fallu faire une liste de listes et ensuite prendre la plus longue, mais je me suis dit que l'algo était déjà suffisamment brute force pour pas qu'en plus, on fasse exploser la mémoire avec des alignements dans tous les sens.

Bah au moins ça marche

Ouais, et si ça se trouve, il n'y a pas tant d'alignements que ça.

j'ai mis les colonnes "Read I/O", "Read I/O bytes", "Write I/O", "Write I/O bytes" et "Other I/O". Il y a autre chose ?

merci harko

c'est le genre de probleme que hephaestus affectionne,ce serait  interessant de lui demander.

Exploser la mémoire, je vois pas comment avec l'algo donné par nraynaud.

'tain le nouveau google reader wtf

Oui, c'est la lenteur de l'algo qui est le facteur limitant, clairement.

Ca donne à peu près ça je pense (pas testé):

edit: fin d'algo stupide

 
«page faults»

 
Calcule l'équation de toutes les paires de point, stockés sous la forme d'une liste de n^2/2 tuples de la forme (a,b), tu trie ces tuples, puis tu recherche la plus longue séquence où a et b sont constants dans la liste de tuples.
 
ça te fait n^2 calculs + un m*log(m) avec m=n^2 pour le tri, plus un m pour le scan final : n^2.log(n^2)+n^2  = n^2.log(n) si jme plante pas.
 
On peut faire mieux si on prend en compte le nombre d'alignements probables, avec un algo de type line-sweep je pense (mais tordu à écrire, et je doute fortement que ça améliore le worst-case)

Ca ressemble à l'algo que je viens de poster, mais je ne comprends pas le tri initial.

+1 mon algo ne consomme rien en mémoire tu gardes que le plus long jusqu'à maintenant. Le max c'est tous les points alignés, ce qui te fait un tableau de n. C'est l'exécution qui tabasse un poil(mais ça reste poly).
 
Y'a des petites optims qui viennent immédiatement (parcourir que la moitié de la liste etc.) mais elles ne font pas tomber la complexité.
 
Par contre, j'arrive pas à voir d'algo plus malin, même en réfléchissant plus longtemps, quelqu'un a d'autres idée ? J'essaye de mettre un tree ou une map dans le problème, mais je trouve pas d'index malin.

t'as quoi comme relation d'ordre dans un espace vectoriel de dimension 2 ? Au pire il est pas total.

tu tries rien du tout, tu gardes que le cas courant s'il est plus long que tout ce que tu as vu jusqu'à maintenant.

Oui, je viens d'éditer, c'est tellement con

 
Tri lexicographique.

nan, mais tu gardes pas la liste non plus bordel, au fil de l'eau tu ne gardes que la meilleure solution !

quelqu'un nous file un centaine points en coordonnées entières svp ?

Ben non, tu es bien obligé de garder en mémoire tous les alignements que tu as rencontré jusque là. Rien ne te dit qu'à un moment donné, un alignement de 3 points n'a pas soudainement 50 autres points alignés parmis les derniers, alors que ton alignement le plus long jusque là contient 12 points.
 
edit: ch'uis con...

généré en JS par :

J'espère que la famille va se faire rembourser la consultation
 
http://www.liberation.fr/societe/0 [...] -sa-webcam

OK, d'après la suggestion de nraynal:

je suis content même moi je l'aurais trouvé

D'ailleurs question : comment tu optimiserais cet algo ?

 
c'est le galaxy S, le i9000.

T'as cherché les équations sans chercher les équations ?    
 
BTW pour ce genre de question le plus important c'est de donner une réponse qui fonctionne, les optimisations ne viennent qu'après.

C'est bien, tu as dépassé le stade du déni

justement je trouve pas de vraie optim. J'ai des pétouilles, mais rien qui change le O

Dans le plan réel, avec des tirages aléatoires, la probabilité d'avoir une droite avec 3 points ou plus est nulle.
A partir de là, on peut calculer les pentes des n^2/2 paires et si on a de la chance, ils seront tous différents et on aura pas à chercher au-delà (autrement il faut continuer avec les paires de points parallèles).
 
Avec le tirage de naraynaud on est encore loin de ce cas car il a tiré 100 points dans un carré 100x100.

M'étonnerait qu'il y ait des solutions simples. Comme dit 0x90, il peut y avoir des approximations probabilistes si ont fait un sampling de l'espace pour avoir une idée de la distribution des points, mais un algo général qui marche à tous les coups, je ne sais pas, c'est un truc de mathématiciens.  
 
Pour info, c'était un test pour une boîte internet californienne bien connue...

Dans ce cas la bonne réponse était de dire que comme dans le cas général, la probabilité d'avoir 3 points alignés est nulle, l'algo recherché correspond à un faux problème

Sauf que c'est pas dans le plan réel, j'ai pas suffisamment précisé dans l'énoncé initial, p-ê (bien que je l'aie indiqué, si tu relis), mais les coordonnées sont entières. Et puis en informatique, les réels, ça n'existe pas.

Bref, je me suis banané big time, mais honnêtement, je m'y attendais.
Ceci dit, si l'un d'entre vous veut tenter le coup, ils ont ouvert de beaux bureaux à Paris et ils embauchent.

mais y'a pas de S-tout-court sur http://www.gelaskins.com/store/phones#Samsung  

L'interviewer va être super content de ce genre de réponse, c'est parfait pour évaluer tes capacités à trouver un algorithme et à analyser son coût et sa complexité

j'aurais tendance à dire que c'est le vibrant international la version "standard"...après si tu savais d'où vient le tel en question ça pourrait aider...