Online Coding Round:
Time: 1.5 hr
Questions Format: 20 MCQs + 2 Coding Questions
MCQs were based on Data Structures,OS,Networking etc.
1)find maximum j-i such that arr[j]>arr[i]
Expected time complexity: O(n)
2)find maximum of minimum of every window size in the array
Only optimised solution(O(n)) using stack was able to pass all test cases.
Around 37 students were selected from the coding round and were called for further interview rounds.
Time: 45 minutes
The interviewer was very cool.She asked me to introduce myself and a brief introduction of the projects that i have done.Then she moved on to the data structures part.
One question was that given an array containing equal number of positive and negative elements, arrange the array such that every positive element is followed by a negative element.I told her the O(n) approach by firstly segregating positive and negative elements with 0 as pivot and then arranging alternatively.She asked me to write code for that covering all corner cases.
Second question was simple to reverse linked list in groups of given k size.
She asked me to write code for that.
Time: 45 minutes
The interviewer was very cool and cooperative.He asked me how my previous round went.Then he moved on to the questions.
One question was simple to find boundary traversal of binary tree.He asked me to write code for that.
Second question was find min cost path in matrix.I told him the approach using bfs then finally solved it using recursion with memoization.Then he asked to write my approach on paper.He was very impressed with my performance in this round.
Time: 60 minutes
The interviewer was the manager and head of the panelist.He asked me to introduce myself,what is my favourite subject.He asked me which question i had solved that i found to be hard and what were the problems that came while approaching that question.Then he moved on to the questions.
One question was given a n-ary tree,for every kth level of the tree,print the kth node present at that level on counting form left and if kth node is not available, then print the last node at that level.I told him the obvious approach using level order traversal.He asked me to write code for that covering all corner cases.
Another question was buy and sell stock only once.Then he changed the question to buying and selling multiple times to maximize final profit.He kept on confusing me by modifying the problem constraints.Then he finally accepted my solution and asked me to dry run on that code.
Time: 1.5 hr
This round was mainly based on problem solving and various CS subjects like OS,DBMS,OOP etc.He started the round by asking me to introduce about my project which was an android app.He asked me about the core idea of the app, its layout etc.He asked me about what i had used for storing various information in database and i told him that i used mysql with mysql statements called from PHP script using url encoding mechanism in java.He asked me about the difficulties that i faced during my project and how i had tackled those problems.Then he moved on to the questions.
The statement of one question was similar to the mobile-keypad problem.But there was slight variation that a dictionary of words was also given along with a number and i had to find all words which are present in dictionary that can be obtained by pressing this number.I told him the usual approach using backtracking.He asked me to optimize my approach.He gave me hint that it could be done by using some spaces.Finally i came to the optimized solution by mapping individual letters with digits from which they can be generated by pressing the digit like pressing 2 can generate letters a,b or c so map a,b and c with 2.Then iterate over every word present in dictionary to find if it is the possible solution or not.
Second question was to find next higher element in an array for every element.I told him the brute-force one of O(n^2) time complexity.He asked me to optimize that.I tried it using BST but it was not passing all test cases.Then after some hints, i finally came to the solution using stack.
He asked me to design a class for tic-toe game where size of board given is variable n.I was asked to implement the member function findWin() by checking all rows,columns and diagonals for all 1s or all 0s for any matrix size n.
He asked me questions based on OOP like abstract class,interface,their differences etc. and in OS, he asked me about mutex,semaphore,their differences etc and describe the software life-cycle in detail.Finally the round ended.
9 students went in the 4th round of which 5 were selected.I was one of them.
Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org