i haven't been interviewed with Google before but i know some guys who have been. the tasks difficulty is comparable to DIV 2 500 on Topcoder , i think this is close to DIV 2 C (DIV 1 A ) on codeforces. and you need knowledge of basic Data Structures (linked list — stack — queue ...etc) and algorithms (DFS — BFS — searching and sorting ...etc ). good luck.

"How difficult those task are in comparison to codeforces tasks ( Div 1C , DIV 1D ? )" — much easier. Once in Jane Street on an onsite interview I got one problem which was ~ Div1D and I miserably failed, but in almost all cases those problems are really easy. My first interview in Google was "Interview tells problem. Immediately after he ends stating it I describe him model solution and implement it." iterated three times and it fitted within 45 minutes :P. But if everything would be about just coming up with solutions I would be much more successful in getting an internship xD.

What they want to test is not your knowledge of complicated data structures but your thought process. Google, Facebook etc. are not factories of tons of solutions to algorithmic problems and it won't be your job here to solve Codeforces problems, what they want to test is your thought process, creativity and ability to write clean code. But as I said, I am not an expert when it comes to interviews, because I already got a few rejections after an interview that I thought went very well xd.

To me it felt very easy (phone screen with Google), 4 questions, 22 minutes. Later I checked my solutions online — they were correct. There was one bug/misprint in last question, but syntax checker caught when I pasted it into IDE. Most people say if syntax checker catches it — it is not that serious.

I know that they are looking at thought process, which I probably failed (never was good at it ;). They don't give comments on the results, only if they have something not revealing mechanics of the process — my only comment was "phone connection was not very good, couldn't hear him well enough" — type of comment you would want to hear right away to fix the situation, not as an explanation for failed interview after week's waiting.

But for me it was mostly fun anyway.

From my experience, their tasks are not about data structures, they are about you solving the problem. Something which on CF you might expect to see under constructive algorithms tag. Problem might be hard or easy but the main point is how you approach it and maybe even more important how you describe your approach. In mine interview problems were of quite different levels, one of the problems was several times changed during the interview to check where you can adjust/optimize your solution given different restrictions or "shapes" of the input data. No complicated data structures were required during my interviews, ideas about basic algorithms or at least some terminology (like LCA for example) was helpful but no more than that. And I should also add that they require you to write at least some code, the amount of code depends on how much time you will actually have after talking through your ideas, my very first interviewer got late on the interview and that took away some coding time.

This is my experience from being on onsite interview, as far as I know they have a shorter phone interview in advance, I have no idea what is happening there.

I had an interview with Google for undergrad summer internship last fall when I just became a yellow coder. I passed the technical interview, but I didn't get the job since there was no match :\

Anyway that was 3 of an hour phone interviews and I can't tell you the actual questions they asked, but I'd say most of them were not very challenging. Like Swistakk said below, most of the time I could answer the questions as soon as they explained or maybe after a few mins of thinking except one problem that took 20~30 min. (and again I just became a yellow coder around that time) Considering the fact that I usually spend 5~30 min on Div 1 A, 30~60 min on Div 1 B, I would say the level was similar to Div 1 A or easier.

Do they require knowledge of specific data structures or they are just tricky modifications of well-known algorithms like dfs

At least in my case, they didn't ask anything weird or very specific. I'm pretty sure what they asked me is taught in any decent undergrad course for algorithm. I had the feeling that they just wanted to make sure I have a deep understanding of those basic algorithm and know how to apply them to solve some problems.

Also, it's not really easy to get an interview with Google at the first place. I know a few friends with very good GPA and research experience and they didn't even get an interview.

I wouldn't say that Jane Street is that hard, yes it harder than most of interviews. But I think the hardest interview for summer internship for software engineers is D.E. Shaw, this interview is very mathematical and problems are very challenging.
P.S. I don't speak of nowhere I got offer from both of them.

I think the difficult of those interview problems are around Div2 B — Div2 C.

Most of the problems can be solved perfectly without any advanced data structure or algorithms. However, there is a slight difference between solving codeforces problems and solving interview problems. You need to try your best to optimize your approach and show the steps and the way you thinking to the interviewers.

For example, if you meet a problem with constraint n=10 0000 and you immediately come up with a O(nlogn) solution. It is ok for codeforces, but it may not be enough for an interview. So, if you are going to have an interview, you may not need to solve very hard problems, solve those relatively simple problems and ask yourself, is your approach good enough?

In addition, from my past experiences, interviewers won't give you a very hard problem unless you claim you are good at algorithm...

I think Div2B, Div2C for normal interview, probably closer to B than C for internships. Focus on asking clarifying questions, coming up with optimal solution and writing clean code (it does not have to be production quality, but it has to be more readable than average Codeforces style junk). Quickly finding and fixing errors in your code after hints from interviewer also helps, as well as ability to provide "unit tests" upon request.