Armyx's blog

Google interview — task difficulty
By Armyx, history, 9 years ago, In English

I am going to apply for an internship at Google. I know there are mostly algorithmic questions, so my question is : How difficult those task are in comparison to codeforces tasks ( Div 1C , DIV 1D ? ) Do they require knowledge of specific data structures or they are just tricky modifications of well-known algorithms like dfs ?

  • Vote: I like it
  • +56
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +55 Vote: I do not like it

"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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I had interviews with a bunch of companies and Jane Street interviews were by far the hardest and I enjoyed them the most. :D

    Other interviews (Facebook, Microsoft, Google) were much much much easier than Div1C / Div1D problems. I can't solve Div1C / Div1D problems, but I got offers from all of the above companies.

    Like Swistakk said you won't be asked to code some complicated algorithms and data structures, but knowledge of them can be very helpful. Couple of times on my interviews I used some data structures in order to solve the problem with no thinking even though it could be solved without those data structures with some additional thinking.

    Most common data structures that come on the interviews are binary trees, binary search trees and TRIEs.

    If you use complex data structures be sure to know how to explain them to the interviewer, because they probably didn't use them / used them long time ago and they forgot them. I had to explain binary indexed trees and segment trees a couple of times.

    My advice for you is to read Cracking the Coding Inteview. I found it to be an awesome resource for preparing for interviews.

    Also you can find a lot of tasks on Glassdoor and CarrerCup.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      "Most common data structures that come on the interviews are binary trees, binary search trees and TRIEs." — I confirm :P

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      The difficulty of the interview really depends on which person interviews you. For instance, in my interview at Jane Street I got fairly simple questions. In fact, the onsite questions were easier than the phone screen questions.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I am very surprised that someone asked problem of Div1D level in interview. Did they give you all constraints & tell you that your code must fit some time limit? Could/did you try answering with some brute force?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      No, they didn't give constraints, I suppose noone does it during interviews. They probably would appreciate bruteoforces and there was one in O(n2) which would be comparable to Div1A or sth, but I was so stressed that I could come up with only exponential solution >_>... Moreover I claimed tons of false statements during this interview xd. However in the end after some hints I figured out how to solve it in , but I felt like they just wiped floor with me (in algorithmics!!).

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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...

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I totally agree with the difference between interviews and codeforces.

    One of the problems they asked was "Given an array A of length N, find ...".

    It sounded like Div 2 A and it had really easy O(N) solution. It felt really weird since it was way too easy, but I thought it's good enough since if we have time to read an array of length N as input, we usually have time to run O(N) algorithm.

    But that problem was actually solvable in O(log(N)) or something like that. I wouldn't have even tried if the interviewer didn't ask for a better algorithm lol

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Yeah, I experienced exactly the same xD. Interviewer told me the problem about two arrays, I immediately started coding linear solution and after sth like 10-15 mins of coding when I ended he asked about better approach and I was like "Bbb, but, but how :o? ......... * facepalm *" :P

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it +26 Vote: I do not like it

        on whiteboard
        Interviewer asked me about an array problem first solved it in O(N^2) after O(N^2) solution
        Interviewer: can you do better ?
        yes man we can do O(N log(N)) and start to implement it.
        Interviewer: can you do better ?
        mmmm yes man we can optimize it O(N log(k)) k is much smaller than N
        Interviewer: can you do better ?
        mmmmmmmm I have no Idea but we can use multi-threading
        Interviewer: Implement it O.o O.o :D

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          You should have started from O(2^N) or something even worse ! You will have a better chance of cracking the interview then :P

          → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply