13 problems to crack interviews

These 13 problems would suffice as a good preparation material to crack the interviews of Microsoft, Amazon and Myspace.

All the below questions requires you to give the most efficient algorithm interms of time and space complexity.

1. Given a circular linked list remove all the duplicate nodes.
2. Given a linked list sort them and explain what is the best sorting method, pros and cons. Remember this is not array sorting this is a linked list sorting.
3. Given a string find the first unique character in the most efficient way.
4. Given a array say for example 20 numbers, you need to generate an output array that will have the product of all the numbers for every index, except the value in the index. for ex: 2, 3, 5 output would be 15, 10, 6 -
Write the test cases to test your app.
5. Find the permutation and combination of a given string.
6. You are given a method void fun(int num) => the output will be a string for example: abc for 1, def for 2.
Now you need to find all the combinations for the given set. say I give you 1, 2, 3. you will get output from the fun() as abc, def, ghijk
final output should be along these lines: 1. adg 2. aeg 3. afg
At any time only one character from a set should appear, which means a and b are mutually exclusive as they are both part of set 1.
7. Given an array and a value called sum, find the minimum set of numbers that could result in the sum value. Find the first any set you obtain. example: sum is 10 and array is 1, 0, 3, 15, 6, 47, 3, 4, 23, 7, 5
the answer should be 3, 7 and not 1, 3, 3, 4
8. Write the same prog. in which the largest set of numbers will be taken in to account for finding such a sum. This is just the opposite of the required in question 7.
9. Given a BTree each node has an extra data information like sibling. The class for node is like class node{int data; node left, node right, node sibling). You are given a tree that is populated with data, left & right. Now you have to obtain the sibling and add it to each node.
If the tree contains ex: three nodes,. root->left and root->right. for the left node you should add it's sibling as right. ie. left->sibling = right. and right->sibling will be null.
10. Implement a queue using stacks. I give you stack with pop, push and isempty methods, using this you should implement the enquee() and dequee().
11. Implement a queue using an array, tell me when is the queue empty and when is the queue full.
12. Explain the efficient way to store a hash table in memory, if the hash table is so huge that it cannot be fit in to memory what are the possible solutions you would come up with?
13. Remove duplicates from an array in O(n) time.

some more questions:
-------------------
1. Find the value in the deepest node of an un-sorted BTree.
2. Given two string, with millions of digits, you need to multiply them. (Half adder/full adder)
3. Count the number of bits set in a dword (See programming pearls book)
4. Print all the nodes in the tree by level (Breadth first traversal)
5. Given N number of people sitting in a round table, each one will start counting the number until M, when M is counted the person who said ‘M’, should quit and the same follows until the end. What data structure will you use to implement this game?
6. You have a set of points which will have a 1:1 connection. Say from a to z are the names of node. What data structure will you choose to implement this? (Obviously vector, but the time to access is more, since it is like a->b-c>….->z so better implement in an array, so that to go from one node to other it is just o(1). Worst case is a->z which will be o(n).
7. How will you calculate the distance for say m->…->U in the above? (the distance to be stored as a cumulative distance, so that we avoid more calc. So while adding ‘o’ to the link n, it will have the cumulative distance from m, this will make the operation faster.

STAY TUNED will post the answers

If you are done with the above, this tip might help.
Donot forget to ask the interviewer what they are looking for and make sure you understand the problems stated.

In some cases it is as simple that the given array is sorted and the solution we are looking for is o(n), but the interviewer never explicitly tells you that the array is sorted. You as the interviewee should ask the interviewer whether the array is sorted etc etc.
Coding is not all the interviewer wants to see in you, the way you think and analyze the problem is all the more important.