N+A Member Technical Staff Interview Questions and Answers

Round: Test
Experience: Quantitative and logical reasoning.Type : Objective, single answer correct, no negative markingTypical apti questions. Quantitative section was not very tough, high school geometry, ratio proportion etc.
Duration: 45 minutes
Total Questions: 45

Round: Test
Experience: +(578*35)] has matching braces (a+(b) does notI did a stack type solution. Keep pushing opening braces onto a stack, when you encounter a closing brace, see if it matches top of stack, if yes pop and proceed; else return false.-Write a program to multiply 2 numbers recursively and without using * operator (use least number of additions)Simple solution add the big number as many times as the smaller number.Later in interview same question was asked, but implement with bitwise operators.- every number ending in 3 has a multiple of the form "111...111" e.g 3 has 111, 13 has 111111 so on..find the algo for finding the number for an input number ending in 3.ideas on solutions : -----
Duration: 60 minutes
Total Questions: 10

Round: Test
Experience: Type : Subjective
Questions were related to C syntax. Code snippets given and we had to predict the output, decide whether code will compile or give error etc.Related to pointers(lots of pointers!), unions (nested unions), pointer to function.
No. of people shortlisted after the aptitude test for the interviews  = 15 (1 MTech, 5 IT, 2 tronix, 7 Comps)
Duration: 60 minutes
Total Questions: 10

Round: Technical Interview
Experience: Data Structures, basic object oriented concepts, algorithms, calculating running time of an algorithm (No code asked)Questions :- He asked me my interests. I said algo, programming and web because i've done a project related to it(TGMC). Then he asked me in brief what all technologies had you used in your project.- Explain virtual function, how does that create polymorphism? I explained and mentioned static binding v/s dynamic binding. Then I was asked how all this is implemented in the back-end, what is v-table etc. I said I didn't really know the working of vtable etc so he dropped the question and just explained it to me in brief.- Design a data structure where you can perform three operations- push pop and min (push, pop same as in stack; min should just tell you the min value and not remove it)I initially started off with a normal stack with another pointer pointing to the min value. Then he said, but what if you pop off that min value. So I said ok we should keep back-trace pointers to previous mins every-time the min is updated. This will work for all situations, even for repeated values because our aim is to find min value and not where it is located in the stack.He then suggested the simplest way to do it was that in each cell, store two things the currently pushed value and also the current min value. This way pointers and all will not be required.- There are 'k' arrays. Each of size 'n'. All the arrays are sorted. Give an efficient algo to merge all these into one array (of kn size obviously)He then gave a hint that the optimal solution is O(knlogk)I started thinking of mergesort style merging. Compare first elements of all, take smallest and put in our result array, then update front pointer, then compare. But in mergesort we compare 2 elements so that takes constant time. Here we have to compare k elements so that will take O(k) time. Hence this method will be O(k^2nlogk)Then I tried to think of merge first 2 arrays; then merge result with third, and so on. Again not optimal.Finally he said try tournament method. Merge 1,2 then 3,4 then 5,6 and so on to get lots of 2n size arrays. And then next stage do same thing to get 4n size arrays. And so on. At each step you do O(kn) work and the depth of this tree that forms is atmost O(log k) so this is optimal solution.- Above question modified. Again k arrays. Now they are all unequal size. Total number of elements is N. Now how will you merge?He said we're aiming for O(Nlog k) and that tournament method will not work here.I thought a bit then he said go back to what you were trying earlier, mergesort style, and think about which data structure you'll use. I said in Nlog k the log k reminds me of heaps. So i'll use a heap to compare front elements of each array. Building the heap -minheap- for first time takes O(k).Later all you have to do is remove min, add a new element and heapify at every step O(log k) So for N elements O(log k) work each so total O(Nlog k)

Round: Technical Interview
Experience: He looked at my school, college scores, asked me which Boards I had done my education from etc. 
-Took my resume. Since I had written android development internship asked me android related questions. --What are the components of andoid app? Services, Activities, Intents etc--How to write an app in C etc instead of JavaNative Development Kit (NDK instead of SDK)--Why would you prefer a language like C over Java in the first place?You can manipulate memory etc so more control over the hardware especially when you want to so system level tasks--Why is C++ better than JavaIn java object oriented is compulsory whereas C++ allows you to do C style functions and procedural programming if you want and OOPs if you want.- Then I just explained what my internship project was about and how we built it etc
-Modified version of apti question. Multiply 2 numbers using bitwise operators.Spent a large amount of time on this question. He helped me at every step. Logic and C/C++ code was required.Basically imagine how you would solve it by hand if you had to convert the numbers to binary and then multiply them. 
- You have a pointer:int **ptr = null;Using this you have to allocate 10x10 square array memory space to this pointer. Use malloc or new or whatever you are comfortable is.Initially my solution stored each row of the matrix is separate separate locations. In the next step he said now it all has to be stored in one contiguous 100 memory spaces.He wanted to see syntax as well as knowledge of memory allocation and pointers but he did not stress sooo much on syntax.
-Since I had HTML, CSS in my resume he just asked me simple questions regarding their syntax, how will you style a div with some id=" ..." and how will you make some text italic or superscript.
-Noticed that I had written git(version control system) in my resume but did not ask me any questions on it.- Functional programming v/s object orientedI said I don't know much about functional programming so he dropped the question
-Why doesn't java have pointers. The compiler does the memory allocation for you. Also pointers are risky since you can play with and currupt memory. Hence java doesnt have pointers at all.-In C++ you yourself discard the memory you allocated using pointers. So what happens in java?Garbage collector does it for you.-How would you implement a garbage collector.I gave vague solution. Basically keep track of all variables etc declared in a particular scope and once the scope finishes, dispose that memory.Then he said but what if you pass a reference to outside that scope. Then you shouldnt be disposing that memory.I couldnt come up with a satisfactory solution so he dropped the question-PuzzleThere is a bridge and a torch. Initially 4 people on one side. They have to cross to other side. They can only go two at a time and they need a torch while crossing so someone will have to come back with the torch.They each walk at different speeds so take different amt of time to cross. When 2 ppl go together they cross at the speed of the slowest. Make them cross in least amount of time.Time taken by each is 1,2,5,10
Optimal Solution(17 units of time)1,2 cross first. 2 units1 comes back. 1 unit5,10 cross. 10 units2 comes back. 2 units1,2 cross. 2 units(I tried two three ways before I reached this solution)

Round: Technical Interview
Experience: - Tell me about yourself.
-Write code for printing nodes of binary search tree in inorder form.I gave a recursive solution. (2 recursive calls in the function) with some if statements. Then he said ok can you reduce the number of if statements. I did that. Then he said can you reduce one recursive call. I tried out a bit but could not come up with a proper solution so he moved on to next question.
- Write a program. You take user input from console. The input consists of many names. A space separates one name from another. Newline means end of input. Something like:abc defgh ij klmnop qrstuvwxyznNow you have to store each of these names in a separate memory location and finally print all of the names in the same sequence you received them.The basic challenge is that you dont know how many names are there and what is the size of a name so how will you allocate memory for these names.
I suggested that initially you should allot some amount of space(say 5 names 5 chars each) Then when you reach the end of this space, allot a larger space, transfer contents from here to there and free the old space. You could add or multiply when you increase the space. 
He expected code for this too. But again not sooo strict on syntax, I got confused on one line he said its ok invent your syntax and move on and just tell me what you intended to do :-P 
- In a singly linked list is it possible to do binary search. If no. why?I said no, unless you store some more pointers and all. That is because in binary search you directly check middle element and keep eliminating half the array. But in linked list just to find middle element you will have to traverse n/2 elements so its not a constant time operation.
-He wrote a function:
void f(int i){ return ++i;}
Is the above function thread safe?
I said yes, since i is local variable and its pass by value each thread will have its own copy so no conflict possible.
He wrote another code snippet:
int i = 5;void main(){ i++; sleep(100); printf("%d",i);}
If we compile this, create an executable, and then run multiple instances of the executable (run the program from many terminals simultaneously) will there be conflict...do you need to do any synchronization?
No, because i is a global variable but each process has its own copy of global variables in its own address space. They do not access a common one. So we're safe.
Finally he asked ok but if I want many processes to share some data then what should I do?Could not think of a proper answer initially then I just said I've heard of something called interprocess communication (IPC) and thats how processes exchange data and parameters and messages. Basically happens through the OS with some shared space(like a mailbox) that both processes can either read from or write in.

Round: HR Interview
Experience: HR round. This round was just a formality. She asked whether moving to another city would be a problem for me. Who all is there in my family etc.Then she asked me if I had any questions and answered them thats it.

General Tips: Think aloud and say how much ever you know. No interviewer expects perfect answers and they give a lot of hints and help you a lot. They just want to see your approach. Say everything you can think of related to the question.-While preparing just focus on your concepts. It is humanly impossible to practice all possible interview questions of that company etc. See all that just to get an idea of which domain the company focuses on in the interview, and not as a question bank for an end sem paper :-P-A techy comapany like this does not bother so much about HR. They care about whether you know your stuff or not. Ofcourse dress properly and behave properly but don't let minor fumbles make you nervous (My phone rang in the middle of the first interview. Obvously apologise and disconnect and put on silent etc but my interviewer did not seem like this went the wrong way with him at all); interviewers are usually pretty cool and understanding.-Interviews are long ordeals usually one hour per round and generally they take all the rounds one after another with no breaks; so make sure you're well fed, not thirsty or tired or sleepy before you come for an interview so that you can survive that long.Good Luck!
Skill Tips: In data structures, learn - Trees, Arrays, Linked List,Stack Queue,Heaps How they are stored , how operations are performed on them,which is useful in what situation,how much time it takes for each operation.

In Algorithms - Calculating the running time is an absolute must! In general know basic techniques like divide and conquer-recursion, and sorting algorithms and why and how each of them work

In C/C++ - Pointers, dynamic memory allocation,how arrays unions etc are stored in memory is an absolute must. Max questions based on this

In Operating System - Synchronizations and other process related topics. Also memory allocation. Know the basic concepts.
Skills: Data Structures, Algorithms basics, , , , , , , C/C++ , , Operating system basics
College Name: vjti