Praca w Google: przykładowe zadanie dla inżyniera/programisty (za 15k) [EN]

Google pokazało przykładowe zadanie do rozwiązania przez programistę, który chciałby pracować w Google. Warto zobaczyć jak to wygląda od środka.

[DEATH_INTJ]

jesli to test do googla to bym stworzyl program dajacy losowa odpowiedz. zupelnie jak google search.

[bialy_nyga]

Uśmiałem się bo sam daje to samo zadanie devom na rozmowach o prace i ich tok myślenia wyglada prawie identycznie

[k.....r]

Mnie wyszło 417. Dobrze?

[a.....j]

nie wiem o czym oni p------ą ale ja jestem skromnym grafikiem 2d

[Z.....d]

Niestety jestem stolarzem za 1k, ale oto moja odpowiedź:
https://jsfiddle.net/sLkov7wn/

ktoś może sprawdzić i dać znać, czy dobrze :D

[DanioPL]

@Zild: może i dobrze, ale ciągle n^2 :D

[p.....a]

@Zild: Ło panie, jak zarabiasz 1k to słaby stolarz z Ciebie, to już lepiej wróć do programowania.

[NajwyzszaFormaSztuki]

Miałem identyczne pytanie na rozmowie rekrutacyjnej :|

[mgorski]

musiałem pisać dokładnie całe na nowo, bo odłączyli prąd.
jest liniowo i żeby polepszyć trzeba zastosować zasadę 'dziel i zwyciężaj'

using System;
using System.Collections.Generic;

class

[t.....m]

Sciema troche, bo rozwiazanie z ordered setem nie jest liniowe. Gosc nie doliczyl czasu jego przeszukania, ktory zerowy nie jest. W przypadku inta o dowolnej wartosci i 10mln liczb, to rozmiar seta moze byc rowny ilosci danych wejsciowych...
No, ale ciekawa zagwozdka. Mozna zrobic trzy osobne sety dla int8, int16 i int32 zeby zaoszczedzic troche pamieci.

[Czarku]

@tamtokontojuzusunalem: używał unordered seta, którego średnia złożoność to O(1), pesymistyczna O(n) jeśli trafią się wszystkie liczby z takim samym hashem, ale przy randomowych danych, szansa na coś takiego nie jest zbyt duża.

[noxitu]

@tamtokontojuzusunalem: w rozwiązaniu mowa o nieuporządkowanym, którego przeszukanie szacować jako O(1).