Claudio Cherubino's blog Life of a Googler

10Jun/088

Google Interview Question: Product of other Elements in an Array in O(n)

Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as "How Would You Move Mount Fuji?" or "How many gas station are there in your country?".

It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough.

After that day, I looked for other well-known interview questions and I discovered that Google has a totally different approach, focusing on algorithms, data structures and complexity.

For instance, one of Google interview questions says:

There is an array A[N] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the product of all the elements of A[] except A[i].

Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart.

Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i].

We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i].

We'll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]:

let rec firstpass product input =
    match input with
    | [] -> []
    | x::xs -> product :: firstpass (product * x) xs

For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual:

let secondpass product input arr =
    let rev_input = List.rev input
    let rev_arr = List.rev arr
    let rec rev_secondpass product (input:list<int>) arr =
      match arr with
      | [] -> []
      | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]

    rev_secondpass product rev_input rev_arr

Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls.

With these functions we can just define an input array and apply them to get the result.

The following is the complete F# code:

#light

let input = [ 4; 3; 2; 1; 2 ]

let answer values =

  let rec firstpass product input =
    match input with
    | [] -> []
    | x::xs -> product :: firstpass (product * x) xs

  let secondpass product input arr =
    let rev_input = List.rev input
    let rev_arr = List.rev arr
    let rec rev_secondpass product (input:list<int>) arr =
      match arr with
      | [] -> []
      | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]

    rev_secondpass product rev_input rev_arr

  values |> firstpass 1 |> secondpass 1 values
21May/089

Google Treasure Hunt 2008, second puzzle in F#

Unlike the first puzzle, which required some maths knowledge, in the second one we have to prove to be able to recursively process the filesystem.

I think that this puzzle should be quite easy to solve for the system administrators and in general those used to scripting languages.

Here is the text of the second Google Treasure Hunt 2008 problem:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_1767743498252291641.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing jkl and ending in .txt
Sum of line 1 for all files with path or name containing zzz and ending in .xml
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.

As usual, the puzzle may seem challenging at a first glance, so it is important to break it into smaller (and simpler) pieces.

First of all, we have to get the list of files ending with a given extension and containing a specific substring in their name.

There is an overloaded version of the Directory.GetFiles() function which takes two parameters, the directory to be searched and a pattern to be found in the files.

Then we have to filter the results checking if the complete filenames (path + filename) contain the given substring.

This first sub-problem can be solved with the following F# code:

#light
open System.IO

let file_list dir pattern content =
  let rec allFiles dir pattern =
      seq
          { for file in Directory.GetFiles(dir, pattern) do
              yield file
            for subdir in Directory.GetDirectories(dir) do
              for file in allFiles subdir pattern do
                  yield file }
  let elems = allFiles dir pattern
  let filt (str : string) = str.Contains(content)
  Seq.filter filt elems

Now we have the list of all files that satisfy the requirements of the exercise.

The next step is to open them (they are plain text files, despite their extensions) and take the numeric value from the right line, if present.

Let's write a function to accomplish this task for a single file and then map it to the entire list:

let getvalue numline filename =
  let lines = File.ReadAllLines(filename)
  let linevalue (lines : string[]) numline =
    let realindex = numline - 1
    if lines.Length > realindex then
      System.Int32.Parse(lines.[realindex])
    else
      0
  linevalue lines numline

The File.ReadAllLines(filename) function returns an array of strings, one for each line of the source file.

Arrays in F# have indexes starting from 0, so we have to subtract 1 from the line number supplied by the user to get the real index.

We also have to be sure that the searched line exists. In this case we return its content, otherwise we return zero.

We have now all the elements we need to compute one of the numbers requested by the exercise, we should only supply the appropriate parameters in this way:

let treasurehunt2 dir pattern content numline =
  file_list dir pattern content |> Seq.map (getvalue numline) |> Seq.fold (+) 0

For instance, to solve the first line of my puzzle we have to run the following command, assuming that the archive was unzipped in C:\google:

treasurehunt2 "C:\google" "*.txt" "jkl" 5

I hope you don't need my help to run this command twice with different parameters and multiply the results to get your answer to the quiz!

19May/083

Google Treasure Hunt 2008, first puzzle in F#

A couple of days ago Google launched a contest called Treasure Hunt 2008, which will be composed of 4 puzzles.

Only the first of these quizzes is already available at http://treasurehunt.appspot.com/, and the new ones will be posted once per week.

At the end of the four puzzles there will be some prizes, even if nothing has been revealed yet.

Here is the description of the first puzzle:

A robot is located at the top-left corner of a n x k grid.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number. Image not to scale.)

Google Treasure Hunt 2008

If the number of rows is r and the number of columns c, the robot can move r-1 steps down and c-1 steps to the right to get to the bottom-right corner of the grid.

The number we want to find is the combination of r1 and c1, and this can be easily computed using the binomial coeficient:

Binomial coeficient

Let's assume r1 = r-1 and c1 = c-1, and write some F# code to get the solution to our problem:

#light
open Microsoft.FSharp.Math.BigInt

let robot rows columns =
  let r1 = rows - 1I
  let c1 = columns - 1I
  (factorial (r1 + c1)) / ((factorial r1) * (factorial c1))

This first puzzle was very easy to solve, if you go to the Treasure Hunt website now, you'll find the next exercise.

I'll give it a try, if you are interested just drop a comment and we'll discuss it here.

14May/080

Powerset, il motore di ricerca rivoluzionario

Quando una decina di anni fa venne lanciato Google nessuno avrebbe mai potuto immaginare che sarebbe diventato il colosso che è adesso.

Alla fine si trattava semplicemente di un nuovo motore di ricerca che cercava di entrare nel mercato dominato da due realtà affermate, Altavista e Yahoo.

Nonostante ciò Google, grazie al suo sistema di ricerca molto più efficiente degli altri, riuscì ad attirare sempre più utenti e diventare leader assoluto del mercato.

Ma questa è storia nota, quello di cui vi voglio parlare oggi è un nuovo motore di ricerca chiamato Powerset che tenta di strappare lo scettro a Google, sfruttando un approccio rivoluzionario.

Mentre i motori di ricerca classici si basano esclusivamente sulle keyword presenti nelle pagine e i link che le collegano, Powerset è in grado di comprendere interrogazioni espresse in linguaggio naturale, sebbene per adesso solo in inglese e limitate alle informazioni contenute in Wikipedia.

Ad esempio è possibile fare ricerche del tipo "what is chemotherapy" o "what is the surface of mars composed of" e i risultati sono sempre azzeccatissimi.

Nella homepage di Powerset (http://www.powerset.com/) vengono anche presentate una serie di interrogazioni di esempio per iniziare a provare questo servizio.

Il passo avanti rispetto alle ricerche a cui siamo abituati è evidente, quello che bisognerà capire è come faranno ad estendere il sistema a tutto il web e come supportare altre lingue diverse dall'inglese.

Dite che Powerset potrà diventare veramente il nuovo Google?

23Apr/087

Remove duplicate values from a List in F#

Once in a while I give a look at the web server log to find out how people landed in this blog and yesterday there was someone that entered the following search string into Google:

Given a random List of integers, write a function that removes all the duplicate values

This site appears as the first result, even if there is no solution for that problem, but I want to help you anyway, unknown visitor!

In fact, we can make use of the Set data type to easily solve the problem.

According to the definition, a Set represents a collection of elements without duplicates.
So, if we create a Set from the given list, all duplicate values will be automatically filtered.

This can be done in a single line, I'll call the function nub because this is the name of the corresponding Haskell one:

let nub xs = xs |> Set.of_list |> Set.to_list

As I said, to return a List without duplicate values we just need to create a Set from it and then create a List from the new Set.

Do you think it is fair to act this way or should I say that I'm cheating? :)

5Mar/087

Il miglior posto di lavoro

Ogni anno il Great Place to Work Institute stila una classifica dei migliori ambienti di lavoro in Italia e nel mondo e al primo posto per il 2008, senza grandi sorprese, troviamo Google.

Eppure ho scoperto che esiste un'azienda nel mondo che tratta i dipendenti meglio di Google e si tratta di una software house chiamata 37Signals, famosa per i suoi prodotti dall'interfaccia innovativa, primo di tutti Basecamp.

Cosa rende 37Signals tanto speciale?

Come si può leggere nel blog aziendale, in 37Signals si lavora solo 4 giorni la settimana, dal Lunedì al Giovedì, per dare al dipendente più tempo per riposare.

Inoltre, l'azienda partecipa alle spese legate alle proprie passioni, siano esse lezioni di volo, di cucina o di qualunque altro genere.

Infine, ad ogni dipendente viene fornita una carta di credito aziendale, con l'unica raccomandazione di "non esagerare" nelle spese!

Non avevo ma visto un'altra azienda motivare in questo modo i lavoratori, voi avete anche uno solo di questi benefit?

14Dec/071

Perchè si studia informatica?

Google, come per qualunque altra cosa, ha una risposta, che si può leggere in un banner pubblicitario di Google Apps:


Google Apps

Chissàse gli amici con i computer pieni di virus saranno d'accordo...

31Oct/076

Google mi ha assegnato PageRank 5!

Ultimamente nella blogosfera si parla molto del recente aggiornamento del PageRank di Google, quell'amato/odiato valore compreso fra 0 e 10 che viene usato dal motore di ricerca per classificare i siti.

Era passato molto tempo dall'ultimo aggiornamento del PageRank, tanto che questo sito non era mai stato ancora valutato dalla sua nascita, ed è anche per questo che mi sono fortemente stupito quando ho scoperto che mi era stato assegnato un rating di 5/10, che è ottimo, soprattutto per un blog come questo.

Comunque non è tutto rose e fiori, molti blogger (ad esempio Napolux) sono stati penalizzati per aver inserito nelle proprie pagine dei link a pagamento, e sempre più gente chiede di abolire il PageRank.

Speriamo non lo facciano presto, vorrei godermi ancora un pò questo risultato! :mrgreen:

3Oct/070

Google Web Masterminds Day

Si è tenuto oggi a Milano il primo Google Web Masterminds Day, una giornata interamente dedicata al mondo delle applicazioni di Google.

In questa occasione sono state presentate le ultime novità  in casa Google, tra cui Google Sky e GData, e io sfortunatamente non ho potuto essere presente, quindi non mi resta altro che attendere la pubblicazione dei resoconti dei partecipanti e magari delle presentazioni che sono state utilizzate oggi.

Però ho avuto almeno l'occasione di vedere l'intervista effettuata da DownloadBlog a Stefano Hesse, il responsabile della comunicazione di Google Italia, il quale ha concluso con una frase che mi fa ben sperare per il futuro:

"Molto probabilmente organizzeremo il prossimo Google Web Masterminds Day al Sud"

Io sono già  prenotato!

3Jul/073

Phishing anche per Google

Non mi era ancora capitato di ricevere tentativi di phishing che riguardavano GMail, ultimamente andavano di moda quelli relativi a Poste Italiane, ma pochi minuti fa ho ricevuto questa mail, con oggetto "URGENTE - Il vostro conto GMail sarà  chiuso":

Caro cliente GMail,

URGENTE - Il vostro account GMail sarà  chiuso nel massimo 3 giorni, per la manutenzione dell'assistente. Se desiderate continuare usando il vostro conto gmail, la preghiamo di confermare a :

Confirma GMail

Riguardi migliori,

GMail Team

Molto credibili in particolare "la manutenzione dell'assistente", il link "Confirma GMail" o i "Riguardi migliori".
Eppure molta gente ci casca, ma come si fa???