### Armyx's blog

By Armyx, history, 4 years ago, ,

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 ?

• +56

 » 4 years ago, # |   0 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.
•  » » 4 years ago, # ^ |   +17 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.
•  » » » 4 years ago, # ^ |   +11 "Most common data structures that come on the interviews are binary trees, binary search trees and TRIEs." — I confirm :P
•  » » » » 4 weeks ago, # ^ | ← Rev. 4 →   -16 me toooooo , as in my internship coding test at google , there is a question that I have a binary tree each vertex has 2 values (index , value) . you have to find the level of the tree with the maximum sum. you will given the tree as an array as follow : [-1 , 7 , 0 , 7 , -8] the above array mean that the root with index 1 in the array have the value = -1 and there are 2 nodes in the next level (ie:index 2 with value 7 and index 3 with value 0 and so on. the photo below will explain the question more. https://pasteboard.co/IkWxlZd.png I thought in using BFS to get the level that have the max sum but , I think there is a corner case that cause the rejection
•  » » » 4 years ago, # ^ |   +14 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.
•  » » 4 years ago, # ^ |   +8 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?
•  » » » 4 years ago, # ^ |   +26 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!!).
 » 4 years ago, # | ← Rev. 3 →   +13 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.
 » 4 years ago, # |   +22 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...