I think brainteasers were used in PM interviews fairly early on (I want to say 2004-2007, but I'm not sure on the exact dates). I've met people that were familiar with the brainteaser-type interview question, but such questions were banned before I started in 2009.