Ooit afgevraagd waarom Google zo dominant is geworden? Er zijn vast een heleboel redenen voor te geven, maar het feit dat ze buitengewoon slimme mensen in dienst hebben zal zeker hebben geholpen.

Ik heb mezelf in mijn jonge jaren door een beta studie heen geworsteld. Ondanks mijn minder dan gemiddelde wiskunde knobbel (meer een instulping dan een knobbel, eerlijk gezegd).

Maar wat aspirant Google medewerkers moeten doen om het Walhalla van Internet bedrijven te mogen betreden gaat mijlenver over mijn hoofd. Een paar voorbeelden:

1. You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
2. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

Bent u nog wakker? En heeft u er ook maar één letter van begrepen? Zo ja, diep respect! Zo niet, wees gerust, u bent niet alleen!

En wil je interessant doen op feesten en partijen? Dan zijn hier de antwoorden:

1. N! / 2!
2. It can be solved in O(n), with an extra space of 4294967296 (range of the integers). Take an array of this much size, initialize with an character ‘a’. Take the ‘i’th elt from the 4 Billion array, if it’s value is ‘j’ go to jth index of this newly created array and change it’s value ot ‘b’. In the last look at all the indexes of newly created array whose value is ‘b’, are the number which has occurred more than once. Note: I used ‘a’ and ‘b’ rather then 1 and 0 since size of char is one byte so will be able to save some space.This can be done,without creating any new array also. But in that solution. One have to swap the numbers. Order will again be same (0(n))

Nou, van die antwoorden heb ik ook al niets begrepen.

Met dank aan Bas, die mij verwees naar deze weblog posting.