Freshers Space

Here are 10 most frequently asked questions that are asked to fresh graduates time and again, during technical interviews,

TOP 10 Fresher FAQs:

1. An array of size k contains integers between 1 and n. You are given an additional scratch array of size n. Compress the original array by removing duplicates in it. What if k << n?

ANS. Can be done in O(k) time i.e. without initializing the auxiliary array!

2. An array of integers. The sum of the array is known not to overflow an integer. Compute the sum. What if we know that integers are in 2's complement form?

ANS. If numbers are in 2's complement, an ordinary looking loop like for(i=total=0;i< n;total+=array[i++]); will do. No need to check for overflows!

3. An array of characters. Reverse the order of words in it.

ANS. Write a routine to reverse a character array. Now call it for the given array and for each word in it.

4. An array of integers of size n. Generate a random permutation of the array, given a function rand_n() that returns an integer between 1 and n, both inclusive, with equal probability. What is the expected time of your algorithm?

ANS. "Expected time" should ring a bell. To compute a random permutation, use the standard algorithm of scanning array from n downto 1, swapping i-th element with a uniformly random element <= i-th. To compute a uniformly random integer between 1 and k (k < n), call rand_n() repeatedly until it returns a value in the desired range.

5. An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.

ANS. Scan array in pairs. Remember largest-so-far and smallest-so-far. Compare the larger of the two strings in the current pair with largest-so-far to update it. And the smaller of the current pair with the smallest-so-far to update it. For a total of <= 3n/2 strcmp() calls. That's also the lower bound.

6. Write a program to remove duplicates from a sorted array.

ANS. int remove_duplicates(int * p, int size)
{
int current, insert = 1;
for (current=1; current < size; current++)
if (p[current] != p[insert-1])
{
p[insert] = p[current];
current++;
insert++;
} else
current++;

return insert;

}


7. What is virtual function in C++?

What happens if an error occurs in constructor or destructor. Discussion on error handling, templates, unique features of C++. What is different in C++ ( compare with unix).

It is theoritical so i am not providing the solution, and it is left upto you!

8.Given a list of numbers ( fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).


9. If you are on a boat and you throw out a suitcase, Will the level of water increase.

Smart guys don't need an answer for this one! Do you?

10. Print an integer using only putchar. Try doing it without using extra storage.

Refer to my other website: www.c-cplusplus.com for solution!

Hope that you make the most out of these suggestions!