Praktyki w Mountain View? Nie tym razem.

Złożyłem papiery na praktyki w Google. A co mi tam, przecież każdy chce tam pracować. Po jakimś czasie (ok 1,5 miesiąca) mejlem odezwała się grzeczna pani, i ustaliliśmy termin na dwie 45-cio minutowe rozmowy.

Obie rozmowy odbyły się z regularnymi pracownikami Google - w pierwszej rozmawiałem z gościem z ładnym angielskim akcentem, a podczas drugiej z facetem, którego ledwo mogłem zrozumieć, bo strasznie terkotał po amerykańsku.

Rozmowy przebiegały mniej więcej podobnie: najpierw gadka na rozgrzewkę, potem pytanko z baz danych, pytanie lub dwa z algorytmiki i na koniec zadanie do którego trzeba napisać (podyktować) krótki program.

Nic nie podpisywałem, więc raczej mogę swobodnie mówić o pytaniach, które mi zadano. Oto one, może komuś pomogą:

Pytania z baz danych:

1. left inner join, right inner join , outer join itp.
2. pytanko na użycie Count i Group by
   (dwie tabele, pierwsza: id_pracownika, wynagrodzenie, id_działu; druga: id_działu,id_managera, podać liczbę pracowników na dział, i średnie wynagrodzenie pracowników dla podległych managerowi)
   

Proste algorytmicze:

1. Tablica jednowymiarowa, rozmiar N. Trzeba utworzyć na wyjściu tablicę P w której w każdym polu P[i] będzie iloczyn wszystkich elementów tablicy N za wyjątkiem N[i]. Czyli dla N=[2,3,4] wynikiem będzie P=[3*4, 2*4, 2*3]. Podać złożoność i koszt pamięciowy proponowanych rozwiązań. Ja wpadłem od razu na koszt O(n), ale doprecyzowano zadanie, że nie mamy operacji dzielenia :)
2. Jak znaleźć medianę i jakim kosztem?
3. Jak scalić i jakim kosztem, dwie tabele A=(aid, akey) i B=(bid, bkey) zakładając że obie są:
1. posortowane
2. tylko b jest posortowana
3. obie są nieposortowane

Pytanka algorytmiczne, trzeba napisać prostą funkcję która je rozwiązuje:

1. Pusta tablica NxN, zaczynamy chodzić po niej od lewego górnego rogu, trzeba dojść do prawego dolnego. Mamy możliwe tylko ruch w prawo i w dół. Napisać program, który wypisze wszystkie możliwe ścieżki dojścia od początku do celu. Oczywiście chodzi o to, żeby pokazać czy się umie zastosować rekurencję.
2. Mamy dostępne trzy literki A, trzy literki B, trzy literki C.
1. napisać funckcję która wypisze wszystkie ciągi trzy literowe możliwe do utworzenia z tych liter
2. jak wyżej, ale ciągi pięcio znakowe

Jeśli komuś te pytania w czymś pomogą to proszę postawić mi piwo.

Podczas rozmowy bardzo miło mi się rozmawiało, ale niestety nie przyjeli mnie.

Ich strata, może czas zacząć karierę, w Polsce?