Wednesday, July 21, 2010

Nagarro Interview of Prashant Singh

Nagarro @Department


Written: 2 Papers

Paper 1 - Aptitude
This included problems from trigonometry, mensuration, geometry, percentages, profit-loss etc.
The level was above average as compared to other companies.

Paper 2 - Coding
 4 problems to be coded in 90 mins: (I attempted all 4)

1) Given an integer array containing only 0s and 1s, find the longest sub-sequence in which number of ones equals number of zeroes.
2) Given an integer array of size 3*n, containing 3 subarrays - A(a1...an), B (b1...bn) & C (c1...cn) in that order. Write code to change the order to a1,b1,c1,a2,b2,c2...an,bn,cn. You cannot use extra memory.
3) Given a string, find the first non-repeating character. (Eg: abcabd - answer would be c)
4) Print the following pattern, do not store elements in the memory:

                      55555
                      44445
                      33345
                      22345
                      12345

Those who cleared the aptitude test were called for the interviews.

Tech Interview

- I was asked to introduce myself, and I'd mentioned my interest in embedded and mobile systems, so sir asked me which microcontrollers I was familiar with. He then asked me to implement MUL instruction for an 8085 mcu.
- Which is my favourite language and why? I answered C, and gave my reasons : fast, closer to the machine, flexibility, etc. It was his favourite language too!
 
Sir then shifted to the codes I had written, discussed each code one by one. For codes which were not optimal, he asked me for other approaches.
For Question 1: I had used 2 variables to store count of 0s and 1s, sir pointed out that I could have done the same thing using only one variable!
For Question 2: My code did not run for all input sizes, so sir asked me to think of different approaches. I told him a recursive one, and he told me an iterative one. It was the same as my code with a different indexing formula.
For Question 4: I was again asked to think of different approaches, and sir said that best one would be to use the difference between rows and columns.
Then sir asked me about which languages I like? I told him C. He asked me, why C? and what all do you like about it?
Then sir asked me a few questions from C, (dynamically malloc'ing a 2d array, and difference between that and (m*n*sizeof(int)) )

 HR Interview:

- Ma'am asked for my introduction, and asked the usual questions -
- Who all are in your family, interests, where do you live, how would you rate yourself in coding in your class? 
- What technologies would you prefer : .net, java, c/cpp, etc... 
- Why Nagarro? What do you know about Nagarro? I'd looked at the profile the day before, so it helped.
- Finally she asked me if I had any questions, I just asked about the nature of work and that was it.
- Finally got selected, and I would suggest that please attempt atleast 3 out of 4 codes, if not all. 
- My interviewer paid a lot of attention to the code I had written, So be prepared with different approaches,
and know your code inside out!
  
All the best!

Friday, July 16, 2010

Aricent Interview of Rajan Gupta

This year students with any ER were not supposed to sit.

Round 1 (Written Test)
Total duration – 1 hour and 40 minutes
Total sections – 4
Marking Scheme – No negative marking


Section one – 30 minutes, 30 Questions 
Syllogism, data sufficiency questions, deductive reasoning.(Very easy section. Basic Logical questions)
 
Section two – 20 minutes, 20 questions.
There were questions which required concentration and labour work rather than brain work. 
Analytical Reasoning Questions(Coding-Decoding, Series, Picture Matching, Blood Relations etc...).  In all, again a very easy section.

Section three – 20 minutes, 20 questions
Algorithms and data structures. The section was easy. To crack this section, you need to know the basics of all types of searching, sorting and data structures like link list, stack , queue and trees. Two searching were not the usual ones – spread sort and cocktail sort whose running time was being asked.
Concentrate on running time for all three cases for this section. Cormen chapter reading would get you through this section.


There are many links given on the net as well to prepare for this section. Here are they
http://technical-interview.com/DataStructures.aspx
http://technical-interview.com/Algorithms_Questions_1.aspx
http://data-structure-definition.blogspot.com/2009/09/data-structure-defination-part-1.html
http://kundansingh.com/interview/
http://www.careerride.com/Data-Structure-Interview-Questions.aspx
http://www.geekinterview.com/Interview-Questions/Programming/Alogirthms/page4
http://placementsindia.blogspot.com/2008/03/some-basic-questions-on-sorting-and.html
 
Section four – 30 questions, 30 minutes
Programming language Section. Choice between C, C++ or Java. 


Maximum students opted for C. Paper on C was tougher than the previous three sections. You should be thorough with the concepts of POINTERS and Strings. Go through Test your C and Pointers in C by Kanetkar. Most of the questions were based on the logic of questions and how the code is working. So you should be able to trace any given code. Check the exact no of times a loop is running. See the syntax carefully so as to eliminate a compile time error. The section will take time if you have not prepared well for C as you will have to think many times before opting the correct answer.

Most of the people cleared the written and it was time to fill the critical incident form.

CRITICAL INCIDENT FORM
It checks out the ability of a candidate to work in team, his leadership skills and ability to handle any situation with the given resources. The following questions were being asked to us –
1.) Describe a situation during your college days when you were involved in some group work & you had to do something to help meet the group objective/goals.

2.) Tell me something about a recent incident where you were involved in a task & you kept making efforts to learn whatever was needed to improve the performance and to achieve the desired results.

3.) Tell me about a recent situation when you faced a problem and you had to identify the issue & related information, analyze them and solve the problem.

4.) Describe a time when you were faced with a task about which you had no or very little info /knowledge, but were responsible to accomplish it.

5.) Describe a situation when you had to make others understand & comprehend some idea or a plan to which he/she didn’t have prior knowledge.

6.) Describe a situation when you faced opposing views to your some original plan of actions or when you were doing a task, some conditions changed forcing you to accommodate.

7.) Describe a situation when you had many tasks/projects due at the same time. What steps did you take to get them all done.



They want to know what steps you took to combat the situation and how you managed to get out of it. What was the final result. Make sure you give real life events and don’t try to make stories.


Examples: Sankalan, Graduation college fest, projects in department and various other events.
Note: It would be a good idea to prepare for this form a night before the Aricent day.

Round 2(GD)
8-10 students in each group. They were divided into 2 subgroups randomly. Scripts were given to all the members on the same topic. The only thing checked here is communication skills. Even if you don’t come up with any view point, you will be asked by the HR in the end to summarize the GD.
Topic given to us was – "Should Euthanasia(Mercykilling) be legalized?" & We had to speak in favor of it.

Round3(Personal interview)
My Interview experience was good. The interviewer was super cool person.

He straight away started with my resume and asked me about MATLAB which I had mentioned in languages known. I told him that I made my security projects in matlab due to many inbuilt functions on matrices.

Then he asked me about my projects. Since aricent is a networking based company, so to his delight, he found the trap in my resume – FTP implementation. He asked me what is it. I explained him the concept of File transfer
protocol and told him that its based on Berkley Socket Interface. So he asked me what it was and how it worked. Both client side and server side were discussed in detail. He asked me all the calls – Socket(), connect(), bind(), listen(), accept(). He told me about the data structures used in this project. How to connect two systems and about ports and ip addresses. He then asked me differences between TFTP and FTP. He again asked about the commands implemented in FTP and their logic. How packets are being transferred for a file.



Then he came to my Shell implementation. How it was done. I told him about internal commands like ls, change directory, etc and external commands like pipes, input output redirection and background processes. We had a discussion over their working. He wanted me to write code for LS command. I was shocked to hear this. It took almost 4 days to implement Ls command during project, and wanted me to write that within 3-4 minutes. I refused him politely saying that I don’t remember the exact flow of but I can tell you the concept. Then he asked me to write the pseudocode for Ls but again I was not sure. I asked him again to explain him verbally. So I did that only.

Then he asked me about fork() command. How can a process be created without using fork. What is exec(). How is it implemented. I was able to handle this part. He then asked, when a system starts in unix, what all steps takes place. I explained him the concept of Bootstrap loader program and the INIT process. He then asked me more details on it n wanted me too explain about a process X creating another process Y without using fork. What would happen and how it would happen?


He then asked me what is a pointer? What is the difference between a single pointer and a pointer to a pointer. I explained him diagrammatically showing the addresses and values. Then he asked me application of pointer to a pointer. I explained him about call by value funda of C and gave him example to pass a pointer to a pointer to head node of a list while performing any operation on a link list. He was not satisfies this answer. So explained him about an array holding pointers to strings. So to access those strings, pointer to pointer was required. He was happy as I explained him diagrammatically. He then asked me about a Queue. He asked me to write functions to perform addition and deletion in a queue through array. I started writing the code and in the meanwhile he was going through my critical incident form and resume.
Then I thought he would end this interview. But he asked me explain my code. And then discussed. How can it be changed. I was nervous while a writing a code for enqueue and dequeue.



Then he discussed about my research papers. I explained him about images. How they are stored. About pixel values. And then explained him about the algorithm that I had implemented on the images. Since mine was for lightweight devices, so we discussed on the usage of memory and speed. The discussion was long on research papers.



Then he said technical part is over. He told me after talking to me and going through my resume and critical incident form, its evident that I have always been associated with so many extra curricular activities and group management task. So he need to ask anything from my Critical incident form. But still he said what would you like to be, a team member or a team leader. I said its situation dependent. Then he said, explain a situation when you had to accommodate with the plan of others in your group. I explained him an incident from my graduation life. He was happy to hear that. It was the end and said do you want to anything. I asked him I hope it was fyn from my side. He said yeah. And said that your concepts and algo is good but coding requires more practice.


That’s it. My interview got over in 1.5 hours. (2.30pm – 4pm)

Note: It wasn’t a conventional interview with standard algo ds c/c++ os dbms networks questions being asked explicitly, But through projects in my resume he checked my concepts in all.

Saturday, May 8, 2010

One97 Interview of Yayati Rajpal

Experience @ One97

We visited company and when we reach there we got to know that D.C.E was also there, So there were total of 36 students.

Written Test 1:

Out of 20 questions we had to attempt any 15 (subjective test)
Few of which I remember are as follows:

Q. Given a M x N matrix we have a robot which can move 1 step right or 1 step down, At any places there can be wall at A[i][j] where 0 is < i < M and o < j < M, starting from A[0][0]. We have to print all paths to reach A[M][N]
Q. Write a subroutine to print Fibonacci series recursively?
Q.  Write a program to reverse singly linked list?
Q. Difference between aggregation and composition.
Q. Difference between Process and Threads. What are different ways to do multithreading(something like this).
Q. Write a program to do binary search on sorted array.
Q. Given some code….tell whether it compiles or not, with reason.
Q.Given a regular expression write preorder, postorder equivalent to that.
Q.Difference between truncate and delete?
Q. 3-4 objective type questions
    Train question …………. Which conclusion follows???
In java, which command is used for garbage collection
1. system.out.gc()
2. system.gc()
3. setgarbagecollection()  something like these

Written 2 : Aptitude test
It includes questions on verbal ability, logical reasoning, numerical ability (more calculative) , data Interpretation, Good one but calculative.

Technical Round 1:
He started with
1. Tell me something about yourself? What more u want to add? What u hav learned new in last 5-6 months….?
I told him about my VisTree project (Generic decision tree inducer and visualizer) which we have implemented in java………..then he went into java……..
2. How are Interfaces different from Abstract classes?
3. Is interface there in C/C++?
4.Given a program in java called as a.java which is :
C:\abc\pqr\xyz\a.java where abc, pqr, xyz are the packages

How to compile this program on command prompt give different ways?? Few more question in java.

Then he moved to OOPs concepts: Encapsulation, Polymorphism, Inheritance
- Difference between abstraction and encapsulation??
- Write binary search program recursively.
Then he switch to DBMS,
- Normalization, outer joins, inner join, left outer join.
- Given two relations perform outer join on this (He wanted to know whether I knw it correctly or not.
- He looked into my written test paper and ask to explain reverse linked list code which I had written.
Then he switch to O.S.
Virtual memory, Page fault etc.


Technical Round 2:

He started with  how was your first tech?

- Rate urself in C/C++?? Then asked me 2-3 output questions of pointers…
- From O.S-----Paging
- What is segmentation fault ?? give situations where it occurs??
- IPC Semaphores----- counting semaphore hw it works…
- From Netwrks------TCP,UDP ?
- Sockets? I told them very basic which I knw about.
- Hav u done any socket programimg earlier??
- How connections established?
- Difference between 16 bit O.S and 32 bit O.S?

Immediately after this round I was called for 3rd tech round

Technical Round 3:

He started with how was the day??
- Then ask me to write your own atoi function??
- How to find in single line code whether 5th bit is set or not??
- 2-3 questions on C/C++ concepts……..(dnt remember)
Then little bit of HR
- Are u willing to work late hrs….
I told them if required and if work is very crucial for company, then he smiles and said every work is crucial..
- Why do you think person has to work late hrs????
- What r ur areas of interest??
- About my future plans


HR Round:

She was very nice... She first looked into my resume ask questions like
- About my favourite subjects in BSc and MSc.?
- Interests
- Future plans….What you aim to be??
- She ask me whether I knew how much package they were offering?? I told her
- Then she went out to confirm with her colleagues
In the end she smiled and said you are part of One97……. Welcome to One97

Finally I got selected 
All the Bbest... :)

One97 Interview of Shefali Sharma

Two written tests:

1. Engineering Test: Questions from Data structures (you have to write algorithms or codes), theoretical questions on DBMS, OS, networks and C/C++ (questions on concepts)
2. Aptitude Test: Basic Quant, Logic and Reasoning, Basic English, Data Interpretation

Interviews:
Basic concepts of C/C++, OS, Networks. They may ask JAVA also.
The difficulty level of technical interview will increase from one round to another. There can be 2 to 3 Technical rounds and one HR interview. 

I faced 1 technical round (roughly 50 min) followed by 1HR round

Technical Interview:
1. May I have your CV?, ( I did not have an extra copy of my CV so i handed over my file which had my CV, certificates and marksheets of B.Sc and M.Sc)
2. Why percentage drop in 12th class?  kahan masti zyada kari hai B.Sc. or M.Sc.?
3. What is the admission process in M.Sc? Did u face any interview during admission in M.Sc.? What is the syllabus of the entrance test? What subjects have you studied in Msc?  What is your favorite subject? (I answered DS and OS)
4. What is the running time of binary search? What is the base of logarithm in the running time u mentioned, why is it 2 ? Discussed a variation - what if we divide it into 10 partitions instead of 2? How will the running time change? (per bucket/partition compare with the maximum element in that bucket/partition to decide which partition to explore next)  Can you think of any algorithm which uses the search approach you mentioned?
5. What are preemptive kernels? 
6. What are system calls? What happens during a system call? 
7. What is an interrupt? What is the difference between interrupt and system call?
8. What is the difference between Real-time OS and general OS? (this was followed by a little discussion on linux versus windows)
9. What platform have you worked on since past 5 years? What all programming languages you know?
10. What algorithm will you use to search a word in dictionary? Suggest a DS to store words in a dictionary? (This was followed by a discussion on how elements are searched from # tables and B+ trees (just a mention of B+ as advancement to # tables)) 
11. Have you heard of Trie DS? (My answer was No sir, he said think a little..., i asked him is it acronym for some DS, he replied NO.  i said i will explore it after interview. )
12. Write a 1 line code to print 3rd bit of a integer? cout << ( ( num & ( 1<< 2) ) >> 2 );
13. What are segments? (in OS) 
14. Why is TCP protocol called connection-oriented? Discuss what happens while connection establishment? (Followed by little on discussion on socket number matching)
15. What is t-test and z-test? What is it used for?
16. What is normal distribution? Give a real life example of normal distribution? Does the distribution of heights of people in a city in a given year follow normal distribution?
17. Why is linear programming a subject in itself? (I could not answer this question ...)
18. What have you studied in AI? What is a genetic algorithm? Give an example (practical use) where you may apply genetic algorithm?
19. What is NP-Hard problem? What is NP-Complete problem?
20. What DS will you use to reverse every word in a list of words?
21. Which book did you refer for studying networks? (Tanenbaum)  Who is Tanenbaum, a Girl or a Boy?    You know any senior, from DU placed in one97?
Which book did u study C++ from in 12th? Have you heard of a book named Bugga and Kulkarni, who is Kulkarni can you guess? Male or Female ? (He was trying to refer to Vidhya kulkarni ma'am :-|  ), the interviewer was a senior, MCA batch pass out, DU.  
22. What is Data Mining? Industry application of this subject? (followed by my Project discussion: Feature Selection in Data Mining Task) 
23. Which of these is correct? Give the storage representation for each?
int i =10;
int *j = i;
int **k = j;
int **l = &j;
int ***m = k;

24. Write a recursive code to reverse a linked list?


HR Round:
1. How is your experience at one97?
2. Tell me something about your family? about yourself?
3. What do you know about one97 ? From whom ?
4. Your strengths?
5. Your favorite subjects? 
6. What platform have you worked on in M.Sc.?
7. What all programming languages you know? Rank yourself on a scale of 1 to 10 in C++?
8. Will you be able to code insertions and deletions in a tree if I ask u right now? ( I said Yes, ma'am :))
9. When can you join us? (I discussed about my project presentation date), she said yes U r selected and gave me the joining date, there itself.


All the best to all who aspire to be here in One97. :)
Be prepared for long interviews, and the interviews might stretch till 11pm. 

Friday, April 23, 2010

Amazon Interview of Sangeeta Pillai

My Amazon Experience:

Amazon interview experience was awesome. I can write an entire blog over it :D. This is not only because I got selected  :P  :P , but also because during the interview you get to meet so many good  and bright people that your motivation to be one amongst them will automatically increase day by day :) :)

Round 1 (Written): It mainly consisted of some normal Puzzles and data structure Qns. I don’t remember them exactly, but they were quite simple.

Round 2 (Telephonic Screening Round): This focused mainly on DS/Algo
Questions were as follows:
1)      A person can climb stairs in 3 ways: Either a single stair at a time or 2 steps together or 3 steps at a time. So, if you have total N stairs give a recurrence relation to solve the above problem.
2)      You have a circle and a point inside it. You have to find the probability of having the point near to center than the circumference of the circle. This one was pretty easy.
3)      Reverse a stack without using Extra memory (U can use recursion).
4)      If I give you a binary number, get me the nearest multiple of 8 which is greater than the number. Use bit manipulations.
5)      Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.
6)      There is an array (of size N) with an Element repeated more than N/2 number of time and the rest of the element in the array can also be repeated but only one element is repeated more than N/2 times. Find the number.

Round 3 (Telephonic Screening Round): This focused mainly on coding (any language)
1)      Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time. (Remember the array size is infinite that is no upper bound) .I was asked the approach first and then the code. I gave a C code.
2)       Given a doubly linked list such that every node has not only next, previous pointers but also an extra pointer called child pointer that points to some arbitrary node out of the given DLL. But the child Node itself can be part of another bigger linked list. Now write a code for flattening the linked list .remember the child node can itself have its own child nodes and so on ….Hence the level of this hierarchy can go on….
3)      Once you get the output of the above question, write a code to reconstruct the original DLL from the output.
4)      Design a Jigsaw Puzzle with appropriate data structures and give function signatures for the game.








Round 4 (Face 2 Face Interview) The TL of the team which was hiring took this interview
1)      Given an array of size N such that both of its 2 halves are sorted individually. Now we need to sort the entire array with O(1) space . Give the psuedocode for the same.
2)      Find the first K smallest element from 1 million sized array . Assume your ram memory is so small that it cannot accommodate all 1 Million element at once.
3)      What are threads? -- > Race condition à Semaphores àdeadlocks ---- etc etc etc
4)      What is synchronization in Java and what does the synchronization method do. If you have to develop your own synchronization method, how will you proceed?
5)      Given an array all of whose elements are positive. You need to get maximum sum of a subsequence such that no 2 numbers in the sequence should be adjacent in the array. So  4 2 6 10 should return 14
6)      Why Amazon?

Round 5 (Face 2 Face interview) Manager of the hiring Team Took this interview
1)      Tell me about yourself , your work in Kuliza etc etc…
2)      What do you know about Amazon (both as a product and as a company)
3)      Design a Parking Lot using Java classes and data structures like Vectors , hashmaps etc.This question took most of the time .Although I was able to come up with a logically correct design but still he seemed to be dissatisfied as I missed out quite a lot edge cases, which he said are very important and should never be ignored …..

Round 6 (Face 2 face interview) This was taken by a senior developer.
1)      Design and code a crossword puzzle. I was asked to first tell the DS that I m going to use and then the approach. After this he asked me to code my approach.
2)      Given a string , pattern and error count  we need to write a function which return true or false based on the fact that whether the string matched the pattern with an error value given as error count. i.e. suppose string is : “abcdef”  and the error count is say 2 and the pattern is “adef” , then there are exactly two characters missing in pattern to form the string , hence there is a match.
Simialry with the same string “abcdef” , the pattern “adef”  as well as “atcdyf” also matches with error count 2 since in the former there is 2 deletions and in latter there are two replacements.
Write an optimized code to implement the function.
3)      Given a 2X2 matrix. Find all valid words ( a dictionary being given) present in all rows, columns and diagonals in the matrix in the most optimized manner. Write Code also.

Round 7 (BAR RAISER) Betta ,  isme to lag gayi…
The specialty of Bar raiser round is the fact that here you will be interviewed by 2 interviewers at the same time. Although only one of them  may be asking qns , but the other one would constantly be observing you and making notes of your spontaneity , enthusiasm ,  and of course  attitude. The one who asks qns will concentrates on your approaches and code.
Instead of giving the questions, I would like to give my suggestions over here coz I felt that your attitude matters the most here.
For clearing this round I will suggest the following:
a)      Never lie in your resume.
b)      Never write about project or technologies on your resume which you are not confident about.
c)      Tell the truth and be honest .It will help.
d)      Tell the roles played by you in your current company in as much detail as possible.
e)      Whenever you are answering any qn (be it designing or coding) , start from simpler soln and go ahead with optimized ones.
f)       Don’t think that your answer may be stupid, because those may indeed be the answers that they are looking for.
g)      They asked me few DS/Algo questions which were easy to start with like they wanted me to store names, marks and other details of students in a school. Then they started adding constraints to their problem like O (1) time retrieval, O (1) time insertion and all. Whenever I suggested a DS, they would introduce a new constraint and so on .Basically they were pushing me to the right DS . I ended up with hash tables but still in hash table we can have collisions because the key here was not ID of student but last name, first name combination. They now wanted me to give them a hashing algo which introduces no collision. (solution : Perfect Hashing)
h)      In this round there is no chance that you get familiar questions. So, don’t get disappointed by the questions as it is also possible that the qns may not have any optimized answers. For e.g. they asked me an NP complete problem. I tried my level best sitting there trying to figure out the optimized solution. I gave them many solution, but all failed some or the other way .In the end they told me that it was NP complete .But throughout the discussion for the question the person observing me was making notes and the person asking the questions was giving me hint just to ensure that, if given hints will I be able to progress ……

Round 8 (Final Round) Finally, the Hiring manager round. The person who took this interview was the Project manager for the hiring team.
He asked me questions related to Oops and since in KULIZA I worked on java also, he asked me some amount of java also like difference between hash maps and hash  tables , refection methods in java etc..
Since In Kuliza, we use Spring framework for our web –applications, he asked some basic questions about MVC framework also.
In the end he asked me a puzzle, which I was able to solve after he gave me a hint.
Interview was over after his and I went home. J