1. How many golf balls can fit in a school bus?

Answer :

The point of the question isn't to see how golf balls you think are in the bus, but to see what your deduction skills are like. Do you just make a random guess or try to cop out by saying a lot, or do you actually try to come up with a legitimate answer by going through a logical series of steps.

2. You have given an array. Find the maximum and minimum numbers in less number of comparisons.

Answer :

Only 3n/2 comparisons are necessary to find both the minimum and the maximum. To do this, we maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, however, at a cost of two comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then compare the smaller to the current minimum and the larger to the current maximum, at a cost of three comparisons for every two elements.

3. There is a portal with two billion users registered. If you store all the 2 billion users in a conventional databases it will take more time to retrieve the data about a particular user when that user tries to login. How do you handle this situation to make sure that the user gets the response quickly.

Answer :

Every row has a primary key. Suppose the primary key for this particular database is the name of the user then we can sort the names based on alphabets and do secondary indexing based on the starting alphabet . If the data is uniformly distributed we can go for multilevel indexing or hashing.Similarly if we have a registration number as the primary key then we can sort the table based on registration number and then do indexing either secondary level or multilevel or apply hashing techniques based on the distribution of data. Many efficient algorithms are available for indexing and hashing.

4. You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.

Answer :

The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array.

Sum of first N natural numbers=N*(N+1)/2

and S=N*(N+1)/2 - K.Now putting this other way around we get K=N*(N+1)/2 -S !!

Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.

We solve this problem by solving 2 essential equations.

They are X+Y=N*(N+1)/2 -S---------->(1)

X*Y=N!/P-------------------(2) where S and P are the cumulative sum and product of the array entries.

5. How would you find out if a machine’s stack grows up or down in memory?

Answer : 

Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function's local is higher, the stack grows away from address location 0; if the function's local is lower, the stack grows towards address location 0.

6. Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.

Answer : 

The simple recurrence relation governing this problem is f(N)=f(N-1) +f(N-2)(why?),which is a fibonacci sequence.

Nth state can be arrived directly by taking 2 step movement from N-2 or 1 step from N-1.Remember N-2 -> N-1 -> N is not a direct path from N-2th state to Nth state.

Hence the no of solutions is no of ways to reach N-2th step and then directly taking a 2 jump step to N + no of ways to reach N-1th step and then taking 1 step advance.

7. You have all the English words with you. you would like to manage a dictionary so that you can look up when ever you have doubt. Which data structure would you like to use and why?

Answer :

Dozens of different data structures have been proposed for implementing dictionaries including hash tables, skip lists, and balanced/unbalanced binary search trees -- so choosing the right one can be tricky. Depending on the application, it is also a decision that can significantly impact performance. In practice, it is more important to avoid using a bad data structure than to identify the single best option available.As the frequency of look ups for a word is also important,weighted binary search tree with weights in proportion to the frequency of lookups and determining the depth, can be effective.

8. Explain a database in three sentences to your eight-year-old nephew.

Answer :

A database is like a file cabinet. The files, or data, is stored in it and can be arranged in categories. But unlike an actual file cabinet, you can do a lot more cool stuff with a database like being able to make it accessible through the internet.

9. What is the Space complexity of quick sort algorithm? how do find it?

Answer :

Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that

• in-place partitioning is used. This requires O(1).
• After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration.

The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.

However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space.

10. Question 2 was pretty easy right? Now do again the same question but the data structure this time around is a Deque.
Input: 12345Data Structure: Deque ( Doubly Que )Note: Deque is a data structure into which you can do enque    and deque from both sides.Some thing like this__________________________________enque ---> <----enque dequeue <---- ----->dequeue__________________________________

Answer :

It is N!. Guess why?(no constraints).Convince yourself by proving that every permutation can be generated by a set of valid operations.This prove can be using the principle of strong mathematical induction.So for this specific input the answer is 120.