The online test consisted of 20 questions and the time limit was 30 minutes. The questions were objective and tricky. The questions covered almost all the core computer science subjects. They were all based on basic concepts. Special attention required for C, DBMS, OS and CN.
The company had lots of expectations from the students in terms of their competencies in coding, knowledge in core subjects, especially that of data structures and algorithm.
2nd round (Tech 1 - F2F Interview) :-
From the previous round, only 10 students were shortlisted. The interview was a long drawn process. It started with a basic introduction of myself. Then he asked a few questions based on my projects. Then he started with the actual questionnaire.
Q1: How to find the least common ancestor of two nodes in a binary tree.
>> I instantly came up with an idea to solve using pre-order traversal. I explained him my logic. The logic was to traverse until we get the nodes by pre-order traversal, store them in two separate arrays. now find the smallest array and the last element would be the least common ancestor, He didn't seemed that satisfied, but he asked me to code it down. I coded it in C. He was little satisfied now. The best thing about the interviewer was that he never smiled at me nor changed the expressions. He started testing my code. Later, we discovered a bug. This logic would wok if both the nodes were in the same subtree of the root, either left or right. But will not work if they are in different subtrees, in which case the root would be the least common ancestor. Then later i took some time and came up with another logic. Now I traverse the tree breadth-wise and store it an array. Like in heap sort, we find the parents of nodes directly by using the index. start from the given nodes, fix the parent of one and vary the parent of the other until we get a common parent. This solution was correct as it would answer all cases. Now again he asked me to code it down and derive its time complexity.
Time taken : 40-50 mins.
Q2: Discussion on various sorting algorithms, their complexities, etc
>> This was a detailed discussion on various sorting algorithms like quick sort, radix sort, merge sort, heap sort. Their time complexities, drawbacks, advantages, growth of their time complexities, comparison of the same in graphs, the best sorting algorithm and so on.
Time taken : 20-30 mins
Q3: Breaking a loop in a linear linked list.
>> Geeksforgeeks was very handy. This is a very common question in interviews for data structures. I went forward with the hash table technique. He asked me to write the pseudocode. Later asked why fast-pointer, slow-pointer method not a better choice and so on. He was testing my knowledge of linked list.
Time taken : 30 mins
Q4: A simple SQL query based on recursive relations.
>> Gave an employee table and asked to write a query which will fetch employees and their manager's name using employee id and manager id which are from the same relation.
Time taken : 2 min.The overall time taken was around 2 hours.
3rd round (Tech 2 F2F-interview ):-Started with a brief introduction about myself, went through my resume for sometime. She was looking over my mini projects. She started asking queries based on my DBMS project. She started asking very complicated nested queries which I was asked to further optimize upon. But I didn't waste much time and answered all in quick succession. The biggest tip for solving SQL queries is to first solve it logically as to how are we going to break things and join again. If we visualize the tables properly and have a good basic knowledge of DBMS, we can solve any type of nested query. They only ask tricky questions based on our basics. We need to be patient and we'll get it.
She then asked me to tell something about me which was not there in the resume. Next we had a long questionnaire based on data structures.
Q1 : How to traverse a binary tree column-wise from left to right.
>> Instantly my mind jumped into inorder traversal as thats the way we traverse a binary tree behind the implementation, columnwise from left to right. The problem was the nodes will be traversed from down to up and not up to down. She wanted it to be from up to down. I tried various strategies to solve. But wasn't getting any breakthrough. She too kept giving me hints and suggestions. Then she felt I wasn't nearing the solution and already 30 to 40 minutes was gone. She gave me the below question. After solving that we came back to this question and gave me another hint. I got the logic. We maintain a counter when it starts from root. Initialise it to 0. Whenever we go left, decrement to counter, and whenever right, increment the counter. These would be the keys of a hash table. Now traverse the tree by any of the depth first traversal. add the nodes to the hash table values to appropriate counters. Then traverse the hash table appropriately and print the nodes. She was satisfied. Now she asked me to code it down in pure C. Never in my life had I implemented Hash tables in C. But luckily I got the idea of structures and started coding on spot. I consumed around 8 pages coding the whole thing. The way I was thinking and coding pretty much impressed her and she was happy about it.
Q2 : Link all siblings of a node and also the nearest siblings (for example, suppose we have siblings s1 and s2, then the right child of s1 and left child of s2 will make a nearest sibling).
>> Solution was easy, just we should add necessary conditions while traversing and link the necessary nodes. She again asked me to code it down in pure C.
Q3 : Sort an array of just 0s, 1s and 2s linearly.
>> First i suggested radix sort blindly as it takes linear amount of time to do so. But she asked me not to use any sorting techniques as such. not even comparitive sorts which would do in linear logarithmic time. Then I came up with the idea of pushing all the 0s to the left and 2s to the right. and left over places fill it with one. Now she asked me to code it down. I came up with a two pass solution where we use another array and fill the values accordingly. She then asked me to do so in a linear time in the same array (in place). I though for sometime and I got the logic. had to maintain 4 iterators and traverse the array. 2 were to flag to swap 0s and 2s and the other two iterators to traverse from left to right and right to left. She was happy about it and moved on to next questions.
Q4 : What is multithreading? Have you used it anywhere? Implement it and show in Java how 2 threads would print odd and and even numbers in a synchronized( pseudocode will do )
>>Explained multithreading, how I had used it in my research projects. Then I started implementing in java code. She basically was looking at my knowledge of threads.
She was pretty much impressed by my performance and said there will be a puzzle round followed by HR round.
The overall time for this round was a little more than 2 hours and 30 mins.
4th Round (Puzzle round F2F )The interviewer asked me if I was comfortable with puzzles and I replied in the affirmative and the round began. He asked me two questions. Basically he was looking for my approach and my thought process. This is what most of the interviewers lookout for. Our confidence, our approach and our knowledge.
Q1 : We have a camel which can carry 1000 bananas at a point A. The camel needs to travel to point B which is 1000 km away. There are 3000 bananas at point A. The camel eats a banana every km as it travels or it ll die of starvation. Devise a strategy and get the maximum number of bananas which the camel can carry to the other end.
>> I asked various questions and finally came up with the strategy. It is to throw bananas midway and come back to initial point until destination is reached. Varying this bufferzone we can arrive at the optimal solution. He was impressed by my thought process.
Q2 : Convert a 8*3 rectangle to 12*2 rectangle. You can cut it only once into two pieces and jion once.
>> This was easy. Just cut the rectangle in a ladder like manner and readjust the pieces. To be visualized properly.
Final Round (HR round ):-
A brief discussion about myself. My hobbies, testing if what i wrote in my resume are true or just farce.
Final words and advice:-Never panic during the process. Drink water whenever necessary. Be hydrated, calm and positive. Be well prepared from the basics. Dont lose confidence and hope. All the best.
#Accolite
Final words and advice:-Never panic during the process. Drink water whenever necessary. Be hydrated, calm and positive. Be well prepared from the basics. Dont lose confidence and hope. All the best.
#Accolite
for what package were you placed for..?
ReplyDelete