I would argue that back then leetcode-style interviews probably filtered for the real talent Google was looking for (and that made possible many things). Then companies started cargo-culting it and people started gaming the system.

My first job, in California, was just transitioning to leetcode-style interviews in 2007 following the industry trend. So it was probably spreading around that time.