Department : CME
CGPA : 9.1
The First Round was a Computer Based Test. It consisted of 1 coding question and remaining technical and aptitude based questions.
The coding question was to find the number of series of consecutive numbers that add up to a particular given sum. I solved it using normal loops in O(n^2) time complexity. The most efficient approach was to use dynamic progamming.
As for the remaining questions, 2 maths based questions were there namely, finding number of BSTs for a given number of nodes and the no of sets formed if i element is present and i+2 element is not. They also asked the number of functions calls to a given binary search function to find a given value. The catch in the question was to include the initial funciton call apart from the recursive calls.
Remaining questions were on time complexity.
Goldman Sachs took a cummulative score based on the coding round score and CGPA to finally shortlist the candidates.
My first technical interview round was about 30-35 minutes long. The interviewer asked me questions which had direct applications to data management in their company. He mainly asked the following questions:
1) Given a number with limit upto 9999, print it in words.
Example - 123 : One Hundred Twenty Three.
I solved it using Maps , to store the words, and Conditional Statements.
2) Perform Transpose of a Matrix.
Solved using Vertical Traversal of the Matrix,
3) Given a string containing the name of a college, extract the city where the college is.
Example - Pune Institue of Technology - Pune is returned.
I solved this by first checking the first and then the last word as they will have a higher probability to contain a city name. If not found, it sort the remaining words and perform binary search on them.
He then asked me to demonstrate basic binary search.
I was asked only 2 questions in my 2nd interview round and it lasted about 45-55 minutes.
1) I was asked to impement a program to find minimum number of steps to go from one initial word to another final word by changing one letter at a time.
Example - DAB -> DAD -> BAD -> BAN
I implemented this using recursion with a global min variable to stop recursion if the number of steps for that recursion exceeds min. The interviewer later asked to use graphs. I was not very familiar with them. I responded with the same. But i put in the basic logic of using graph by keeping a count of number of steps needed to reach the final word from a given word so that if i encounter a visited word midway between another recursion i need not run the entire recursion.
2) For my 2nd question, I was asked to implement the game Tic-Tac-Toe.
Firstly, i was asked to make only valid moves but later was also asked to make the best moves. I can be implemented using conditional statements with checks for safety and then winning move.
My last interview round was relatively easier. I was asked the following questions:
1) Given an array containing zeroes, push all the zeroes to the back maintaing the sequence of the remaining array.
It can be easily implemented using 2 pointers in O(n).
2) Given an inflowing stream of words, group all the anagrams together.
I used a Hash Function which was a 26 length string containing the count of the number of occurences of each letter in the word which uniquely defines an anagram.
There was no HR Round in particular. But in each interview round they used to ask HR based questions in between. Most significantly i was asked HR questions in my 3rd round which were basically about myself and in-depth about my Summer Project.