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.

[leoha]

Jeśli ktoś lubi takie zadania i chciałby się czegoś nauczyć to polecam książki i filniki pani Gayle Laakmann McDowell - autorki książki "Cracking the coding interview".

[Czarku]

@leoha: Jak ktoś lubi takie zadania to raczej powinien klepać jakiegoś HackerRanka albo innego CF czy TopCodera :V

[noxitu]

@leoha: Jeśli ktoś szuka trudnych zadań to prawdopodobnie najlepszym miejscem będzie main.edu.pl.

[shdw]

Jak by ktoś się zastanawiał:

function isSumPossible(a, n) {

_ const dict = a.reduce((acc, el) => {

___ acc[el] = true

___ return acc

[mhib]

@shdw: O(n+1) = O(2n)

[karer]

jak to? przy 100 elementach będziesz miał od 101 do 200 operacji.

@shdw: no tak i wychodzi 200:101 to jak 2000:1001. Zwiekszajac ilosc elementow 10 krotnie zwiekszamy ratio tez 10 krotnie. Dlatego jest to taka sama zlozonosc obliczeniowa

[A.....k]

Mireczki, w czym moje rozwiązanie jest gorsze od tego z filmu?

[Czarku]

@Analityk: comp.find jest to metoda unordered_set i ma średnią złożoność O(1)

[JaroslawPolskeZbaw]

Ale koleś robi comp.find w pętli for,

@Analityk: Wcześniej powiedział dlaczego tak robi, że na hash secie to złożoność O(1)

[p.....n]

Aż sobie nasmarowałem kod do tego zadanka: https://play.golang.org/p/Hj9n3jxXC7

[Mimimimimimimimimimimi]

@pop-corn: Dlatego nie dostaniesz pracy w googlu. Raz że nie masz racji, dwa że wypowiadasz się mimo że nie obejrzałeś do końca. Hint: 18:50.

[Mimimimimimimimimimimi]

@pop-corn: Niestety, za uważne oglądanie filmików na YT pracy nie dają.

[Abgan]

Czemu nikt nie zauważył, że pierwsze rozwiązanie tego Edgara, to dla posortowanej tablicy jest złe?
Nie zadziała dla wejścia [-100, 1, 2, 4, 4] i szukanej sumy: 8 W warunkach było podane, że ujemne mogą być (wyjaśnienie w 2:30) i dla takiego wejścia suma (-100 + 4) będzie mniejsza niż 8, więc zmniejszy prawy indeks (zmienna hi) i przegrał - już nic mu się nie zsumuje do 8.

Gdzie mogę odebrać moje

[noxitu]

@Abgan: Nie oglądałem filmu by sprawdzić czy gdzieś się nie przejęzyczyli, ale jeśli suma jest mniejsza to oczywiste jest, że jeden z indeksów trzeba przesunąć w prawo, a nie w lewo jak zrozumiałeś. Algorytm Edgara jest jak najbardziej poprawny.

[Abgan]

@Abgan: Bleee... edytować już nie mogę, ale głupotę napisałem. Algorytm jest poprawny, poległem na porównaniu -96 < 8 ( ͡° ʖ̯ ͡°)

To by było na tyle, jeśli chodzi o 15k...

[Linuksiarz1]

Nie mogli wybrać jakiejś ładniejszej pani? Ciężko się ogląda... ( ͡° ʖ̯ ͡°)

[s.....u]

@Linuksiarz1: Zamknij oczy i sluchaj.

Pomoglo.

[B.....n]

public static void main(String[] args)
-------{
-------------int[] tablica = {1,2,4,4,6,7};

-------------for(int i = 0;i<tablica.length;i++)
-------------{

[kroxintu]

@Brodeon: Uprzedzając twoje wątpliwości. Minusy najprawdopodobniej dostajesz za zdanie "Rozczulają się nad zadaniem nie wiadomo ile czasu. Gdyby było z milion elementów w tablicy to być może zastanawiałbym się nad lepszym algorytmem".

Otóż sposób rozwiązania problemu zależy od założeń i kryteriów oceny - każde z nich są zmienne, dyktowane tokiem myślenia aplikanta i rekruterki/egzaminatorki.
Sam przykład na kilku liczbach też jest uproszczeniem, przecież kobieta nie napisze ci na tablicy miliarda znaków,

[Czarku]

@Brodeon: Tak będzie lepsze i szybsze, bo Twoje rozwiązanie to kwadrat, a jego to liniówka. Polecam poczytać o złożoności obliczeniowej :>

[elppa]

Za 15k nie chciałoby mi się nawet tak banalnego zadania rozwiązywać..

[Wooferek]

@elppa: don't feed the troll guys

[elppa]

@Wooferek: Mówię prawdę. Trzeba cenić swoją wiedzę i umiejętności.

[bobolak]

Hehe z tego co widze to gorace laski tam raczej nie pracuja ( ͡° ͜ʖ ͡°)

[lovelypl]

@bobolak: byś się zdziwił :)

[bobolak]

@lovelypl: no wiesz ten filmik to nie jest pozytywny przekaz - jakis piwniczanin i niezbyt atencyjna loszka rozwiazuja jakies kiepawe zadanie. nie chcialbym tam pracowac gdybym swoja opinie budowal wylacznie na filmiku. btw i tak nie chcialbym tam pracowac ( ͡° ͜ʖ ͡°)