Note that I wrote the OP in response to someone who seemed to think they were better than having to memorize/review the basic data structures. The measures I took to reduce stress weren't relevant to why it was necessary to know how basic data structures work, and I didn't mention them.

As someone else has mentioned, the interview process may have changed significantly since I left in 2010. Clearly I don't think Google is perfect, but they try hard to make the interview process as accurate as possible. It's very expensive in terms of opportunity cost alone to interview someone, and every person they stress out in the interview process is going to tell at least 10 good potential hires about their bad experience.

Generally the first thing I did was tell the interviewee that every interview was a clean slate and that I didn't know how they had done in previous interviews and wouldn't tell later interviewers about their performance. I told them the hiring committee takes the independent reports from the various interviewers and throws out any outliers, so they should try and not worry about any one interview. I mentioned that the sheet of paper I had been passed listed which questions they had been asked, but not how the interviewer thought they had done. I explained that I would gradually modify the questions to make them harder and harder until we ran out of the time I had allotted for that particular question, and that I didn't expect them to be able to answer the most difficult parts of the questions in the allotted time. I mentioned that I was more interested in seeing how they thought than seeing one best answer.

I generally tried to structure the interview as a joint problem solving session, trying to use the word "we" as much as possible. I gave hints when people got stuck, and certainly didn't expect them to fully solve the problems without hints. In my writeup, I'd often note if I felt they would have done a bit better if they had been a bit calmer. I really was silently rooting for them to succeed. It's very fun interviewing someone who's bright and excited about the subject matter.

That being said, I had 40 minutes (trying to leave 5 minutes at the end for any questions they had) to try and asses the interviewee's abilities in several categories. I'm not sure how to do that without ratcheting up the difficulty of a question until the interviewee fails, and then repeating with another question. If you don't push them to the point of failure, you don't know where the edges of their abilities are. I tried to minimize the pressure, but in the end, I had to push them until they failed, and failed multiple times. Failure is naturally stressful, and there was only so much I could do to reduce that stress.

The interview process tried to minimize any biases of any one given interviewer, making each judgement as independent as possible, so that meant there needed to be many interviews. There's a lot of opportunity cost spent in interviewing people, and people get worn out if you keep bringing them back in, so that necessitated making each interview short.

I knew a fair number of full-time Googlers who started out as contractors. I'm sure already working at Google helped take a lot of the pressure off, but they still went through technical interviews.

Anyway, the interview process was far from perfect, I'm just saying that it's perfectly reasonable for professionals to be able to cram freshman/sophomore level data structures in order to interview.