Showing posts with label Bangalore. Show all posts
Showing posts with label Bangalore. Show all posts

Monday, October 22, 2012

National Instruments Interview of Monika Bisla

Written:


  • sqrt(b^2 - 4ac), if a =[0, 0.5] and b=[4, infinity), Whats the range of c?
  • Write a recursive function to get the product of all the digits of a number.(eg: for 123: output 1*2*3; for 56: output 5*6=30)
  • Find the 100th number of the series 2, 4, 8, 14, 22, 32....
  • Find the 20,000th element of the series 1, 2,2, 3,3,3, 4,4,4,4, ....
  • Write a single statement to check whether a given number is a power of 2.
  • T(n) = 2*T(n-1)+2^(n-1); T(1) = 1. Find T(7).

  •  int index, i=0, k=0, j=0;  
     for(index=0; index <= some_number; index++){  
       i = i+1;  
       if( (i/5) == 1 ){  
         i=0;  
         k = k+1;  
         if( (k/5) == 1){  
           k=0;  
           j = j+1;  
         }  
       }  
     }  
    

    What's the value of i, k, j interms of 'some_number' after the the execution of for loop?
  • A bag contains 3 coins out of which * 1 coin is painted RED both the sides * 1 coin is painted BLUE both the sides* 1 coin is painted RED with one side and BLUE with another. Two coins are selected from the bag and tossed. Find the probability of  getting both as RED.
  • What's the effect of(or write a common code) the following code on an array of 8 elements?
     for(i=0; i<4; i++)  
       a[i] += a[i+4];  
     for(i=0; i<4; i++)  
       a[i] += a[i+2];  
     for(i=0; i<4; i++)  
       a[i] += a[i+1];  
    
  • Write a function for generating random number between a given range.
    Using above, write a function to generate random integers between a given range such that probability of each integer is same.
  • How many edges are there in a complete graph of n vertices.
    Using the formula in question above, find number of graphs possible with ‘n’ vertices (graphs need not to be complete).
  • Calculate number of inversions in a given array.
    In general what would be the number of inversions in the worst case and what is that worst case.
  • Let us define a walk from v to v in the given graph:

    Number of 1-walk is represented by W(1) and given by:
            V-V                               // W(1) = 1
    Number of 2-walk is represented by W(2) and given by:
            V-V-V
            V-W-V                           //W(2) = 2
    Find W(3) and W(4).
    Also find W(n) in general.
  • Draw a DFA for a language which ends with 0101.
Interview 1:
In this interview, they basically discussed written test only and some extra questions:
  • Write code for making a copy of Binary Tree.
  • Write code for finding maximum root to leaf path sum.
    Write code for both approaches (top-down and bottom-up).
Interview 2:
  • Given a long formula for a carbon compound, Write a code for counting the number of carbon atoms.
    Ex: (C2H6(CH2)6CH2C3H4)4CH2C6H6C5H5
    Handle all the cases.
    Give code for iterative as well as recursive approach.
  • Given a Binary tree, where internal nodes of the tree represents an AND or an OR gate and leaf nodes consists of values either 0 or 1.
    Write code for finding the final resultant at the root node.
  • In the Question given above, add one more argument to your function which gives the expected value of the result.
    If result calculated by your function and expected values are not same, flip the gates in internal nodes of tree in such a manner such that result and expected values comes out to be equal.
    Do this in minimum number of flips possible.
    Also handle those cases where it is impossible to achieve the expected value.
    Write the code for above problem.
Then, there were some normal HR questions and that was it!! 

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

Thursday, October 22, 2009

Microsoft Interview of Varun Bhatia

The interview started off with my introduction and the interviewee asked me to provide all details about my hobbies, strengths, weakness etc.
Then he shifted to my projects. He asked me details of my few projects. He wanted to know the aim of the projects, my contribution to them, how many team members were involved in it, what was the time limit. He also asked what problems I faced while implementing the project and how I solved them. and if we took someone's help.

My advice in project related questions will be that only mention those projects in your resume that you are comfortable with..... Also this comfort level will come only by doing these projects themselves...also tell only what you have actually implemented....do not try to fool the interviewee by telling things that you did not actually implement in your project.... also use only those terms to exlpain your project that you are comfortable with...do not use heavy terms unless you are well prepared with what they actually mean.....

After half an hour discussion on my projects, he shifted to data structures and algo...
Firstly he asked me to write the code of preorder....i easily did that recursively...next he told me to do the same without using recursion....i was prepared with this problem and answered that.....  
the last and final question was that you are given two arrays and you have to place those elements in the third array that are common to both.....
ex arr1 = {1,2,3,4,5,6,7}
     arr2 = {5,6,7,8,9,1,2}
then arr3 should be {1,2,5,6,7}

I told many approaches to it but he wanted to listen to the approach that he had in his mind....i was not able to figure that but since i gave 2-3 approaches for the same problem...next he asked me to write the code for implementation i gave.....since it was a telephonic interview, and he could neither see my code nor was he writing when i was telling the code, he asked me to test my own code and find bugs in it.....i found two to three syntax as well as logical mistakes and he was ok with it...maybe he was testing my testing ability......

thats all  !!

All the best for your placement preparation.....
Just stay confident.... any company does not expects the perfect answer from the start....your problem solving techniques are also important and they matter a lot....

Wednesday, June 17, 2009

Adobe Interview of Sandeep Jain

Hi all,

Here it goes... :)

Written

I am not putting down the written questions as they were same to almost everyone else. But I would sincerely request that you practice all the written questions that are already available to you.


Interviews

I went through four rounds of technical interview. In all these they mostly asked about my internship at Trilogy, my current work in Decho. (So if you are going off campus make sure you are clear about your past experience)
Secondly since my interview was in Bangalore (arranged separately), The Bangalore interviewers were not aware of me being an on-campus, and they treated me more as an off-campus/experienced candidate. Probably thats why they asked a lot about my current and past work-ex.


Round 1

- Tell me something about yourself (and all those regular questions)
- Write the basic structure of linklist node?
- Now using this structure waf for reversing a link list? (I wrote iterative one)
- Show me the stack trace on this function for atleast three nodes.
- Write a similar recursive code, he again asked me to show the stack trace?
- How will you find whether a link list has loop in it? (and the stack trace of my code)
- How will you find kth node from the end? (again with stack trace of my code)
- How will you write a zip command? (basically file compression)
I gave him two ans: One replace char with char and frequency (but then I pointed out the -ves of this approach myself). Second was using Huffman code
- What are function pointers, how to use them, why to use them?

75% interview was bout, Trilogy's project, so Java, JavaScript, etc etc. BUT strictly project specific, which will never be asked to you people.

Note: I had to write these questions on white board, and he wanted me to teach him.


Round 2

- Started with puzzle, that 4 people, 17 minute river crossing question. Which we all did in the starting of our preparation. I said I already know this.
- Virtual functions, why we need them?
- Why or Why cant Constructors & Destructors be virtual?
- What happens when we make a Destructor virtual?
- Can we call virtual functions in constructor?
I said yes we can, BUT the there is no point of using the word virtual here, because polymorphism doesn't come into picture during construction.
- He gave a list of integers, asked me to make a heap out of it, then usage of heap, complexity of heap, complexity of binary search, why is it the fastest.
- Now came the big question. Write a Generalize Link List program. I didn't know what it was. So he explained: Its a list that can store any kind of data, int, char, float or double.
I gave him 3 solutions using unions, void*, and a mix of both.
- Then he asked about Templates, I said, I only know basics, not much.
- STL... I said (an assertive one) NO, never used, jst heard of it. :P
- Then he moved to pointers :D :D \:D/
- Function pointers, asked me to write 2-4 complex declarations using function pointers.
- Give a practical e.g. where you have used function pointers, where in windows do you think we use function pointers. (Thanks to windows programming & VC++)
- What happens when we throw an exception?
- How will you check if a link list is corrupted?
- Data Break points their usage (this had to do with checking of corruption)


Round 3

This guy looked scary, serious, intelligent and I was damn nervous just after looking at him (wat lag gayi thi).

- Began in the usual manner, about yourself, about the projects in Trilogy & Decho. Since both were on web apps, so he asked about EJB, how do Apache or JBoss servers work. Thn lots of things about Trilogy's project. (I answered to the best of my knowledge, thou I don't think that was sufficient)
- One puzzle, rope of uneven thickness burns in 1 hr, measure half hr. (bacho wala tha ye :P)
- Another Puzzle, two robots are designed to move either right or left, if they collide with anything they will stop, otherwise they will keep moving. Write a module such that, if I put the two robots on an infinte line, nd run Your module on both of them, in an infite loop, they shud have a high probability of collision.
- Waf that takes root of a tree and a sum. & returns if the tree has a path(root to leaf) such that sum of the nodes on this path is same as the input sum.
- Templates again, I gave the same ans.. that I know very little... (but is baar main nai bacha) he said tell me how much do u know, rather whatever you know.
- STL again, I said no.
- Benefits of using templates and STL, followed by a discussion on Java vs C/C++
- This guy also moved to function pointers, I gave my prev e.g only. but he asked for code, nd advantage of my code.
- I am developing a project that I want to work across different platforms, what would you suggest I should do? I said strictly use language standards, and no compiler dependent features.
Then he said but I need to use certain libraries of different platforms. Like we have certain ones on linux. I said you can use conditional compilation using #if & #elif etc... cuz we have certain inbuilt symbols like ___win somethin something___ whenver we need to use such code. We can keep them in such blocks (while giving this answer one more variation clicked so) I said OR you can put all dependent code in individual modules. and make an independent module that uses these. (wrapper kind of thing) in this wrapper you can use the ususal #if #elif


Round 4

This was from noida, video conference with some engg. head in Noida

- WAF which takes an integer input i (i can be 1 or 2) and returns 2 or 1 (alternates) respectively.
- Then a lot about project in Trilogy, and Decho
- Difference between GET nd POST, which is better?
- He almost exhausted me bout Decho projects. Everything and anything that I had learned in past 1 month was covered. XML, XPath whatever I knew.
- Last question, I want a sort function that can sort anything, ints, doubles, structures, even arrays, anything you can imagine. Write the prototype. Then he asked me to explain the parameters I had taken, and why I had taken them.


HR Round

This was more of a formality.
General questions on family background, brothers n sisters, what I do for leisure, why I wanted to go to Noida and all those stuff.

I hope I was of some help...
All the Best... :)

Wednesday, April 29, 2009

Decho Interview of Sandeep Jain

Hi,

This is my Interview Experience at Decho, Hope its helpful... :)


Round 1: One hour Aptitude test

It contained the usual apti questions like
- pipe
- ratio proportion
- seating/arrangements
- % related
- speed distance

It seems easy with the captions but there were few really tricky ones.

These two were different:

There is only one correct soultion to the following, what is it?
A) Ans is A
B) Ans is A or B
C) Ans is C or D
D) None of this

How many questions have you solved correctly?
A) All of them
B) None of them
C) All of them except this one
D) Only this one




Round 2: 30 Minutes Technical written

5 questions we had to do any 3

1) Reverse a Link List
void reverse(node **head)

2) Count the number of leaves in a binary tree.
This question was not that clear it seemed as if they wanted to know minimum & maximum number of leaves in a Binary tree with N nodes.

3) Write a function to Reverse the words in a sentence.
void reverse_words(char *sentence, int sentence_length);

For e.g.
Input: This is a book
Output: book a is This


4) Given a Binary tree, write a modify function that replaces a nodes value with the sum of the values of its children.
void modify(node *root);

5) There is a string, and a pair, count the occurrences of this pair in this pair.
E.g.: String = "abceabcdefqw", Pair = "ab"
int count_pairs(const string &str, const string &pair);




Round 3: First tech interview

Q) Tell me something about yourself
Q) About the project in Trilogy, He only wanted a basic introduction of the project
Q) I have to maintain an integer which can be in two states, i = a or i = b.
i.e. i can have only these two values. Write a code that toggles this value of i from a to b or vice versa. Without using if, switch, for, while, do-while, ternary.
I gave a XOR solution, but then he said do not use any XOR either.

Q) Write a function to find the first non-repeating character in a given char array.

Q) There are three ants sitting at the vertices of an equilateral triangle. They can only move along the edges of the triangle. If all of them have equal speed and all of them start moving at the same time. What is the probability of collision of any two ants?

Q) I have a group of people standing in a matrix form (i.e. rows & columns) I select a person A who is the tallest of the shortest of every column,
person B who is the shortest of the tallest of every row.
Out of A & B who has the chances of being taller than the other.

Q) What are const functions?
Q) How do you make a member variable modifiable even if the object itself is const?
Q) What are the ways in which you pass arguments to a function? (call-by-value, call-by-reference) Give examples and explain the working.
Q) I gave an e.g of using int type arguments. So now he asked What if are dealing with objects?
Q) When are copy constructors called? write a sample copy constructor.
Q) What is a singleton class? Write a sample.
Q) Why do we use virtual destructors?
Q) Suppose you created a class, can you prevent your users from using destructors?
Q) What happens when you use a static variable in a function? What if we have multiple threads facing race condition for that static variable?
Q) Where is the data that is used by a process stored? (he wanted details of storage in terms of local variables, global, static, dynamically allocated ones)
Q) Write a fully functional Queue class.




Round 4: Second tech interview

Q) Started with the Trilogy-project. Asked for a detailed description. What the project is, how it works, what have I done till now?
What kind of bugs I fixed? What was the biggest challenge during internship? etc etc... I spoke everything I could recall at that time.
Q) Write a function that will convert a binary tree into its mirror image.
Q) There is an underground electric wire from city A to city B, The wire has broken at some point. The only way to check the wire at any point is to dig that place and then check whether it is broken or not. Give an efficient way to do it, so that our time & cost is minimal.
I gave a solution(think a little, its easy) then he said, what if do not know the distance, we only know that wire starts from city A, and that it is broken at some point.
Q) Prisoners on a staircase with either red/blue hats. The one who tells the correct colour lives or he dies. Its a famous puzzle.
Q) Pirates puzzle, 5 Pirates, have 100 bucks. They follow a hierarchy all 5 being at different levels. The superior one decides how to distribute the money. Then there is a poll among the five, if there are more than 50% votes against the distribution the top most pirate is killed. Then the distribution has to be made by the 2nd pirate in the hierarchy and so on. Assuming that all pirates are really smart, greedy, and want to live as well. How would the leader distribute it.
Q) In a village there are 100 people & everone has a strange disease, all those who have this disease have a halo over their head. If anyone comes to know that he has the disease(by looking at his halo or if someone else tells him) he dies the next morning. i.e. Awareness of disease leads to death. :P
A magician, in an attempt to save them, cast a spell over the entire village. Because of which "NO one shall see his own halo, and no one shall tell anyone else about their Halo" NOW the questio is, For many days will they live?



Round 5: Third tech interview

Q) Write a recursive function to compute the number of binary 1's & 0's both.
Q) Write a function that removes extraneous spaces from a string. For e.g.
Input: "I______am_____a______Boy"
Output: "I am a Boy"
Input: "______I_____am_____a____________Boy____"
Output: "I am a Boy"

I gave them the code, but they insisted my code to have a fatal bug. & I kept disagreeing, finally they said, its correct telling me that they forgot to see the last line of code (which handled null)

Q) Why do we need multi-threading on a single processor? (He wanted the concept of DMA & I/O devices)
Q) There are 6 boxes numbered 1,2,3,4,5,6. Box 1 contains infinite balls of 1 kg. Box 2 contains balls of 2 kg and so...
However one of the boxes contains defective balls. All balls have the same defect and thus there weight is different than the expected weight. For e.g. in Box 3 we have all balls weighing 8 kg instead of 3 kg.
Given an electronic scale so that measure accurate weights of each, In how many least weighings can you find out the defective box, how many balls will you will take out from the boxes?



Round 6: The F-2-F with the General manager of Decho

Initially she did not ask any questions she just explained how the company works, what the project is, how the current project works etc etc. Then she asked me what I did or didn't understand. If I would like to ask any questions to her. This all seemed pretty good. Cause she made it appear as if I was selected. She also explained how Decho is a part of EMC^2 (It was acquired by EMC^2)
Then she told me that the HR will meet me next.



Round 7: HR round

- Tell me something about yourself starting from your school, Please skip the technical details.
- What about your family, fathers business, siblings etc etc.
- How did you get into this IT field, you already have a family business?
- Who are the people you met today? (I told her that in sequence :P)
- From the time you came to our office till now, what new have you learned?
- What was the best experience in Trilogy?
- What was the worst experience in Trilogy?
- Why not Aricent? Why not Nagarro?
- Why Bangalore & not NCR?
- She asked some resume related stuff, as well.
- What your strength? Weaknesses?
- (I answered being short tempered as a weakness) then why do you think you get angry?
- Why do you think people get angry?
- Next she wanted me to ask her questions, as much as I wanted to?

I asked her the following:
-- What do you think I should or must improve on?
-- What are the office timings? I hope its not a school.
-- I asked her about EMC^2 & how does EMC^2 effect Decho. What about recession's effect on EMC and thus on Decho?
-- How does the appraisals work? (Cause she said its the task of manager to check on the performance)
-- If the compnay provides cab facility or accomodation?

There were sone questions related to compensation as well, which I am not listing here... :P :P

And thats it...
Through with it... :)

All The Best to all of you.

Friday, April 17, 2009

Amazon Interview of Varun Maini


Telephonic Interview :

1) Explain ur current company project.He wanted to know in depth, at each step he said , can we go into more details of implementation.
2) You are given a very huge string ,u have to beautify it.
beautify means that wherever there are multiple spaces / tabs repace it with single space.Whenever there is a full stop make the next char in Upper case,
no characters except the start of new line should be in upper case except when they are enclosed in single/double quotes,
U have to do this all in a single traversal and const space.
3) Implement a stack so that push,pop and max would take O(1) time.(gave 4-5 approaches)
4) Given a date as 2001/10/02 its a palendrom , find the palendrom date that occured just before this.


Round 1: (focused just on coding)

1) given an array find three numbers whose product is maximum.

(NOTE : looks easy but dont be fooled , there could be -ve nos too !!!!
gave 3-4 approaches , finally gave code for the approach taking O(n) time and const space)

2) Given a binary tree , convert it into a doubly linked list where the elements in DLL will be in same order as inorder traversal of the tree.

3) Given a sorted array , rotate it from a given Kth index in best possible manner

4) given a sorted array that is rotated find the index from which rotation happened ( O(logn) soln )


Round 2 : (focused on coding and DS )

1) given an i/p string AAABBCCCAA , o/p = A3B2C3A2 etc .. requirements : single traversal of string and const memory

2) give me a data structure such that if there could be values between 1-1000 then u could do the following operation in o(1) time :

insert(x) , delete(x), giveAnyElement()

where 'giveAnyElement()' will return any element present in the Data Structure.

U can assume that memory is no issue .. just concentrate on O(1) time .

(My soln : take a array[3][1000] array wherein
for each of the 'i' index :
array [0][i] = a int having value 0 or 1 , where 0 means element not present , 1 = element is present
array [1][i] = index of next value in the list
array [2][i] = index of previous value in the list

Basically u need to implement a doubly linked list on in an array and u are done :)

3) given a linkedList where each node has two pointer fields next and Random
where next points to the next node of linklist , while random could point to any node in LL
so create a copy of the linkList.


Round 3 : (focused on Algo,DS and coding)

1) given a NxM matrix , where each array entry is a character, write a code that will find all the words that can be formed using elements in a row, oolumn and diagonal

2) given a binary tree , each node apart from left and right has a tail pointer attached to it , where each tail should point to a node which would
come to the right of the current node , if a inorder traversal of tree is done.
So u have to devise a O(n) algo to find out which all nodes have their tail pointers set incorrectly.

3) given a huge string of size n (where n = about one billion ), there are m strings each k characters long u have to find out all the occurences of these m strings
in a single traversal of the big string.

(soln started from naive string matching, then kmp,then sorting the m strings and using buckets,then using binary trees, tries, hashing etc .. )


Round 4 : (focused on my ability to Design )

1) u have a function where there is an infinite loop thats running and in that loop , getRandomNumber() is called, at any point of time i should be able to track
the maximum, minimum, second max , sum , mean ,median etc of the nos.

Also i should have the flexibility that i can add more features , ex i can also add feature to find mode of the nos found so far

more importantly :a) i should have the flexibility to 'Remove' any feature as and when i want
b) i should be able to change the implementation of any of max, minimum methods without needing any change in my class


(My soln : after a good long discussion , i used Observer Design Pattern)

2) what is the diff between interface and abstract classes
give real world examples for them.

3) What do u know about JDBC , what is the purpose of the driver, when u do a preparedStatement.execute() then what all happens

4) Discuss the Collections API , what all interfaces and concrete classes does it provide , if u had to create ur own Varun-collections API then what all interface
and abstract classes would u provide

5) U have to design a database schema denoting the entire recruitment process , wherein storing info about candidates , interviewers , the interview results etc ..

Round 5 : (foucussed on Algo and how efficiently can i convert my algo to code)

1) given a NxM matrix where each row has elements in sorted order , and each column has element in sorted order , u have to find a given no in O(n) time and no extra space
ex :
1 4 10
3 6 11
4 7 15
find if 7 is present or not .

2) Given n sorted arrays merge them into a single sorted array

3) If i give u an N then ur code should give me the no of distinct binary trees possible with N nodes
ex i/p = 3 o/p = 5

4) once again went back to first question , now its given that all the arrays are increasing continously
ie
1 4 10
12 16 20
24 30 35 now find if a given x is present of not



Round 6 : (Focussed on HR,Data Strcuture , Algo)

1) whats the best thing about trilogy
2) if u have to change something in trilogy what would that be
3) biggest challenge u faced there
4) biggest accomplishment
5) Why amazon , there are 100 of companies out there ???

6) if u have to design the algo for searching that would be used for google , then what algo are u going to use.

7) extension of 6th : u have a huge file and u enter some key words , now u need to find the closest set of characters that enclose the entire set of keywords.

ex : let String Be "ABAACAAABXYABX....BXAC.." where these A,B,C... are words (not a single characters)
suppose user enters the keywords A,B,C then ur answer should be "BXAC"


Round 7 : (DS, Algo , OS, Puzzles)

1) what all have u read in OS. Can u describe features of any OS.

(I told lot of things that i had read in Galvin , then i started to describe UNIX , giving details about inode, the kind of scheduling algo it uses, singal
mechanism it uses ,system call mechanism , the dual mode operations , the access control of files, talked about (datablock,superblock,inodeblock,bootblock)
talked about its shell and how can its functionality be easily extended etc ... )

2) in amazon we have millions of customers daily , if we wanted to give some gift to the customer who buy 3 or more items during the last 7 days , what DS and Algo
are u going to use to store and retrive this info

3) There is a file that has N lines
where 'i' th line says : "There are exactly i lines in the file which are false"

ie .. There are exactly 1 line in the file which is false
There are exactly 2 lines in the file which are false
..
..
There are exactly n lines in the file which are false

now u have to find out which of these n lines are true.

4) given a village with demons and a sleeping man, The man is always sleeping ,never wakes up. Now a demon can eat the sleeping man , but after that
he will fall asleep , any demon can eat another sleeping demon.
If demons are very smart and would always choose to stay alive than to eat the man and risk their lives.
so if initially there are 65 demons and 1 sleeping man ,, what would happen in the village ???

Monday, March 16, 2009

Kuliza Interview of Sangeeta Pillai

It was a telephonic interview.

They wanted recruitment for the post for Database Developer, however once they interviewed me; they said that later my domain might be switched over for development related to web-application. Hence my interview largely focused on DBMS and Java.

(Main focus for Database was oracle)

  1. They gave me set of tables each having around 3 to four attributes and asked me to write a Query, which updated certain tables from the set based on a condition in one of the table. Basically they wanted me to use triggers.
  2. There were certain questions related to decode.
  3. Next Question was to create a cursor and write procedure for the same. She wanted an optimized solution for the same that is using nested tables.
  4. What is an Optimizer and how does it work?
  5. Granting and revoking privileges to users in Oracle
  6. What are Transactions?
  7. Data structure used in RDBMS
  8. Insertion in b+ tree with code.

Once these set of questions were over they gave me a break of 5 minutes and called again. This time another person was on the other end. He asked me about my interests in Java and also the work I was doing in Trilogy.

He asked the following Questions:

  1. Implementation of Multiple Inheritance in java.
  2. Difference between String and String buffer in java
  3. Garbage Collection in java and how does it work?
  4. Making objects in JavaScript and using them
  5. Use of ‘packages’ and ‘import’ in java.


Next was the HR Round Questions, which was largely focused on ‘Why Kuliza?’ and ‘why the switch from Trilogy and what about my other on campus placements? ’

Thursday, November 27, 2008

Trilogy Interview of Sandeep Jain

Written:

There were 4 questions, 3 of coding & 1 was for debugging. We were asked to write algorithm, code with comments & proper naming conventions

I attempted-
1st question completely
2nd was correct, but my approach was not the best
3rd was able to write only the initial approach about the problem
I couldn’t attempt the 4th one

So as such you guys need not worry about attempting all the questions. There were two telephonic interviews, and in both the interviews the interviewer first gave his formal introduction & then asked me for my intro.

So here goes the description...


First round tech Interview:

TRI: Tell me something about any recent project that you did, the one you like the most.
I described the GSD project, and my role in it. (GSD was the best project in terms of what I had learned)

TRI: Given a general stack implementation, can you write a function MAX(s) that returns the current maximum value in the stack?
ME: I gave him two O(n) solutions, basically to scan the array or link list used to implement the stack
TRI: Which is a better approach, array or Link list in terms of efficiency?
ME: Array, due to locality of reference
TRI: Good, but I want the MAX to be returned in O(1)
ME: (After 2 mins of thinking) Can I modify the Data Structure

Well he agreed to modify the DS but by using my approach the original push/pop operations became O(n). He had some discussions even thou he was satisfied with my approach he wanted me to improve my approach. His only requirement was to have push, pop & max functions to be O(1). I got stuck at this point. Then he gave me sample data to work upon. Using the given data I was able to correct my approach and finally gave him the correct solution.

TRI: The next problem goes like this, suppose I give you an integer array, Can you generate all triplets such that a^2 + b^2 = c^2 where a, b, c are all elements of the array?
ME: I said, I have done a similar question, where we find all pairs a[i] & a[j] such that a[i] +a[j] =X, I can you use this approach.
TRI: Ok go ahead.

I gave him an O(n^2) solution. Then I told him that I can optimize by calculating the square and replacing the contents of each element by the corresponding square. This will reduce computations regarding squaring of elements again & again. He was impressed with this approach. The problem then reduces to finding triplets such that X+Y = Z.

TRI: Can you write the code for it? Take your time & then dictate me complete error free code. (He asked me about the signature of the function, name & type of variable too.)

TRI: You must know about tree, traversals. Can you write code to perform a level wise traversal of a binary tree?
ME: Sir I know this problem, Shall I continue.
TRI: Is that so, well then just give me an overview.
I dictated him the entire code. :D

TRI: Suppose we have two nodes of a binary tree; find its least common ancestor. I hope you don’t know this one.
ME: Not, exactly, but I did this problem, a few months ago.
TRI: Ok then do it for a BST
I gave him the approach; he was satisfied with it & asked me to tell the order of the algorithm. Its O(lg N) guys.

TRI: Well, Mr. Sandeep your interview went pretty well & that’s all I wanted to discuss. Would you like to ask me anything?
ME: I do not have any particular question. I just hope there is no problem with my call getting disconnected.



Second round tech Interview:

This was a tough one; I can’t give the entire description. But trust me I was shivering & sweating during the interview. There was only one question; I had to implement a game.

It goes something like this-
There are two 3-letter words for e.g. CAT & TRY
If you are allowed to alter any single letter then in how many steps can you convert CAT into TRY, the only constraint is that the intermediate words should be valid 3-letter words.
I asked him if we have a repository of words. He said I can assume a dictionary with all possible 3-letter words.
We discussed the algorithm for around 25-30 mins. After which I was asked to write a code for it, such that we can calculate the minimum number of steps required (as there are many chains possible or we may have none).
So return -1 if we cannot convert Source to Destination.
After 15-20 mins of coding. He further made me optimize the code. I had given him a recursive approach, which scanned the DB in a DFS manner. He made me convert my code to BFS, & then asked me to compare the two in terms of efficiency & space.

This one question covered: String matching, Hashing, General Tree, BFS, DFS, Recursion, Tail-Recursion, Tree pruning, & god knows what...
One thing was for sure I was exhausted after the interview... BUT it was an awesome experience.

All The best... :)

Friday, August 29, 2008

Trilogy Interview of Manmohan

Hi these are the question asked to me in Trilogy Interview.
Hope these questions help you too :D All the best :)


1st Round

Only postorder of bst given regenerate the tree
Approach
Code
Complexity
Optimization improve the order of ur solution


2nd Round

1) Spiral printing n*n matrix not m*n actually discussed for that also but coded for n*n only

2) LCA least common Ancestor

3rd Round

LinkList merging Y shaped find the common point or merging point
char array is given find the first repeating character in the array

eg. char a[ ] = "abcdcad"

return "a" here...not "c"

Reverse link list: Code and explanation of calls made
Test case : when llist contains a loop then it will fail then what will u do

1) Then find the loop

2) Remove the loop then reverse the list using this function

3) Camal Banana puzzle 4000 banana and 1000 km and 1000 banana max limit per trip
What is the maximum number of bananas u can take to the other side.
4) Pure virtual function

5) Sinlgeton class Implementation

6) Diameter of a tree: Code and Complexity


4th Round

1) 1-d array given find the sum of the elements between 2 indices say i and j in constant time
eg. a[] = "1 4 2 5 6 3"
and if i = 2 and j = 4 then it should return the sum 4+2+5 from the array in constant time .
U need to do some preprocessing on array for this
2) Now the same for a 2-d array. Now two indices are given say (i1,j1) and (i2,j2)
Find the sum of elements of the rectangle formed by these indices in constant time again do some preprocessing computation for this and return the result in constant time.
3) check IsBst() check if a binary tree is bst or not
do it in o(n) now
do it in o(n) with o(1) space complexity now
4) 2 candles each burns 1 hr Measure 45 minutes