What a cool way to advertise.
Google almost never advertises with traditional media. However, here is an example of one ad they did run a while back.
The billboard was a math problem: find the first 10-digit prime found in consecutive digits of e. If you were able to solve the problem, and put http://[very_long_numeric_answer].com into your browser, you were directed to Google’s jobs site. Too cool.