Google SDE (Software Development Engineer) Interview Questions and Answers

Round: Test
Experience: The MCQs were based on C.C++,Java and some Operating System questions. Around 200+ from our college sat for this round.

Tips: Solve C C++ output related questions.
Difficulty level : Medium
Duration: 30 minutes
Total Questions: 15

Round: Test
Experience: After the first round around 100 (consisting of the internship students as well) students were shortlisted for the second round
Everyone got different sets of questions. The questions I got were :
Given two arrays were digits of one array represent a number,maximize the number by replacing it with elements of second array.
eg:
arr={3,1,4,5,6}
rep={1,9,5,2,3}

after replacement
arr={9,5,4,5,6}
one digit of rep can be used to replace only once.
For this almost everyone who got this question used a brute force method.But I had used a different approach .I constructed a max heap of rep array.And ran a loop checking if the max element of rep was greater than the element in arr and then replaced it in arr and deleted the same from the maxheap.

Given a matrix ,where each cell represents a value of strength.The value could be positive negative or zero. At each cell the strength value is added.You have to reach from point (0,0) to point (m-1,n-1) if at any point the strength becomes zero or negative then you cant proceed further.Find the minimum strength required before starting to reach the end of the matrix.
eg . {{ 1,-3,0},
{-2,1,-1}} Ans: 2 ( (2+1+(-2)+1+(-1)=1 path taken )
I gave a DP solution but was unable to pass a few test cases in this question.
Tips: Practice problems on Data Structures like Trees, Arrays , Heaps , Linked Lists ,etc
Duration: 90 minutes
Total Questions: 2

Round: Test
Experience: Around 30 students consisting of students from other colleges as well were called On-site. This was a written round.Everyone was given around 45 mins and 1 question.
Given the root to a binary tree, a value n and k.Find the sum of nodes at distance k from node with value n.
This is similar to this question on geeks ->-----/
I was able to do this quite quickly :D I even explained my answer to the HR and he asked me to write different types of test cases to exhaustively check if my code works on all of them.
After this round around 14 people were shortlisted.

Round: Technical Interview
Experience: These were fairly easy questions . I knew the solutions and explained it to the interviewer.He asked a few questions on them , seemed satisfied.Asked me if I had any questions for him . So I asked him about the different technologies that a new SDE would work on and things like that. I had a pretty good discussion with him he told me many things from his end too.
I made it to the next round then :D
Tips: Well one thing I realized after giving interviews was when they ask the candidate for any questions then you should always ask something , shows that you are interested.

Round: Technical Interview
Experience: He told me to take my time and give the solution. I gave him a solution of considering the text as a linked list of words . Where each node in the linked list contained the word string and an index .And for every node in the linked list I will have Trie structure. I used trie for efficient search.What I suggested was that I use the trie whenever the user enters a word and insert it into the trie and the leaf of that word will contain the index of that word plus the pointer to that node in the linked list . If suppose the trie already has the word then i increase the word count in the leaf and the leaf will contain a vector that has the list of indexes where the word has occurred and the list of pointers where the word is present in the list.I wrote the code and explained how it can handle all corner cases . We discussed the the solution and he asked me certain questions on different test cases . My approach handled them well. He seemed satisfied . He added to the question that the search query could contain words or phrases . So my use of indexes could handle the phrase search :) . I also suggested that instead of Trie data structure we could use a Ternary Search Tree as that would be more space efficient.
Tips: Practice Design questions too besides Data Structure problems

Round: Other Interview
Experience: This was a HR+Technical Interview

The interviewer was quite experienced and very pleasant. He asked me how my previous rounds went.He was going through my performance review from the previous rounds. He took a glance though my CV and asked me about the projects I did. He saw that I had interned at IITB so he asked me a lot on that project. He also asked me some basic HR questions like Why should Microsoft hire you ? Where do you see yourself in the next 5 years ?.He was very impressed with my academic record and my AIEEE rank. Asked me how I handled my 12th board exams and entrances.He made it very comfortable and was almost chatting and getting to know about me.
Question 1:
Thankfully I was just going through this question just before this round :D . I suggested the solution using Trie and Min Heap.
Similar to -> -----/
Question 2 :
First I gave him the brute force approach . Similar to ->-----/
But I knew it wasnt using the fact that we have a Binary Search tree . So the interviewer gave me some hints - like what is main criteria of a BST . I immediately figured out that the minimum path will always be on the right side of the node because it has the larger value. I told him the solution he seemed satisfied.
He then asked if I has any questions for him . So I asked him about where I can improve myself , he said I didnt need any improvement I am doing very well and that I should jus keep doing what I am doing :D That certainly made my day :) I asked a couple more questions about Microsoft and then left.

Finally after a week the results came I received the mail that I had been shortlisted for a Full Time Position :D
Tips: Have a good grasp on Data Structures. Solve as many problems possible from Geeks4Geeks
Be confident in the interview . Have a smiling face and be adaptable to the question . The interviewer can anytime change or twist the question just to confuse you.
The interviewers are very helpful , if you feel stuck communicate with them ..explain your approach they will give you hints.
When the interviewer gives the question listen to it carefully do not immediately rush to writing the code .. ask him about the different criteria and restrictions pertaining to the question.
Check your code with all possible test cases and list them.
Lastly , even if you arent able to get the right solution then just explain your approach . Recruiters analyse how you tackle the problem not necessary that you have to have the accurate solution.


General Tips: Be confident in the interview . Have a smiling face and be adaptable to the question . The interviewer can anytime change or twist the question just to confuse you.
The interviewers are very helpful , if you feel stuck communicate with them ..explain your approach they will give you hints.
When the interviewer gives the question listen to it carefully do not immediately rush to writing the code .. ask him about the different criteria and restrictions pertaining to the question.
Lastly , hard work goes a long way ! Never loose hope. I got placed in Oracle Applications and Microsoft after being rejected by almost 6 companies :) And believe me those interviews also taught me a lot .
Learn from your failures and don't lose hope :)
Skills: Object Oriented Programming (OOP) Basics, Basic C/C++, C Programming, Algorithms And Data Structures
College Name: NIT Bhopal
Motivation: Microsoft is dream company for any Computer Science Engineer. And I am glad I got this opportunity.