I haven't worked at Google, but I have interviewed with and reviewed feedback from Xooglers, and 4's are not impossible -- but they are rare and you have to essentially be smarter than your interviewer about the particular problem to get one. This can be pretty hard, since many interviewers pick problems that they are extremely familiar with.