Important Interview Questions

1. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).
2. There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).
3. Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.
4. You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.

Note: Some position may be blank in the game। So your data structure should
consider this condition also.
5. You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.
6. How do you put a Binary Search Tree in an array in a efficient manner.


Hint :: If the node is stored at the ith position and its children are at
2i and 2i+1(I mean level order wise)Its not the most efficient way.

7. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.

Note :: You should not use use any extra space. i.e sorting Binary Search Tree
and storing the results in an array and listing out the fifth element.
8. Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn
9. Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
10. Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?
11. How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?
12. Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi).How do you do the same ?
13. Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?
14. Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
Hint: Some kind of pointer handling with In Order Traversal - anybody in for
writing some code
15. You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
16. Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
17. Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
18. Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
19. Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
20. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
21. Given an array,

i) find the longest continuous increasing subsequence.

ii) find the longest increasing subsequence.
22. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
23. Write a function to find the middle node of a single link list.
24. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
25. Implement put/get methods of a fixed size cache with LRU replacement algorithm.
26. You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

Distance is defined like this :

If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"

Please give a solution in O(n) time complexity
27. Classic - Egg Problem

You are given 2 eggs.You have access to a 100-storey building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Interview Questions

. Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can?t pass the value k to any function also.
2. What are the 4 basics of OOP?
3. Define Data Abstraction. What is its importance?
4. Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
5. Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren?t present.
6. Given a string,find the first un-repeated character in it? Give some test cases
7. You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
8. 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.
9. What is a C array and illustrate the how is it different from a list.
10. What is the time and space complexities of merge sort and when is it preferred over quick sort?
11. Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.
12. Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.
13. Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.
14. Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
15. How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
16. Explain polymorphism. Provide an example.
17. Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
18. You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
19. Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number

Technical

1.What would be the output of the following program.
#include
main()
{
extern int a;
printf("%d",a);;
}
int a=20;
(a) 20 (b) 0 (c) garbage value (d) error!!
2.What would be the output of the following program.
main()
{
int a[5]={2,3};
printf("\n %d %d %d",a[2],a[3],a[4]);
}
(a) garbage value (b) 2 3 3 (c) 3 2 2 (d) 0 0 0

3.What would be the output of the following program.
main()
{
inti=-3,j=2,k=0,m;
m=++i&&++j||++k;
printf("\n %d %d %d %d",i,j,k,m);
}
(a) -2 3 0 1 (b) -3 2 0 1 (c) -2 3 1 1 (d) error
4.What would be the output of the following program.
main()
{
int a,b;
a=sumdig(123);
b=sumdig(123);
printf("%d %d",a,b);
}
sumdig(int n)
{
static int s=0;
int d;
if(n!=0)
{
d=n%10;
n=(n-d)/10;
s=s+d;
sumdig(n);
}
else return(s);
}
(a) 12 6 (b) 6 12 (c) 3 15 (d) error

5.What would be the output of the following program.
#define CUBE(x) (x*x*x)
main()
{
int a,b=3;
a=CUBE(b++);
printf("\n %d %d",a,b);
}
(a) 64 4 (b) 27 4 (c) 27 6 (d) 64 6

6.What would be the output of the following program.
main()
{
const int x=get();
printf("%d",x);
}
get()
{
return(20);
}
(a) 20 (b) garbage value (c) error (d) 0

7.A function has this prototype void f1(int **x),
How will you call this function?
(a) int **a; (b) int a; (c) int *a; (d) int a=5;
f1(a); f1(&a); f1(&a); f1(&&a);

8.pointout the error, if any, in the for loop
main()
{
int l=1;
for(;;)
{
printf("%d",l++);
if(l>10)
break;
}
}
(a) The condition in the for loop is a must (b) The two semicolons should be dropped
(c) The for loop should be replaced by awhile loop (d) No error

9.Can the following piece of code be executed?
int main(void)
{
char strA[10]="compile",strB[10];
my_strcpy(strB,strA);
puts(strB);
}
char * my_strcpy(char *destination,char *source)
{
char *p=destination;
while(*source!='\0')
{
*p++=*source++;
}
*p='\0';
return destination;
}
(a) Compilation will only give a warning but will proceed to execute & will display "compile"
(b) The compilation error char *(char *,char *) differs in levels of indirection from 'int()' will occur
(c) Yes & it will print compile on the screen (d) None of the above

10.What would be the output of the following program.
#include
main()
{
char str[5]="fast";
static char *ptr_to_array = str;
printf("%s",ptr_to_array);
}
(a) Compilation will only give a warning but will proceed to execute & will display "fast"
(b) display "fast" on screen (c) will give a compilation error (d) none of the above

11.What would be the output of the following program.
main()
{
int num,*p;
num=5;
p=#
printf("%d",*p);
}
(a) 6 (b) 5 (c) junk value (d) compilation error

12.What would be the output of the following program.
main()
{
int a[3]={2,3,4};
char *p;
p=a;
p=(char *)((int *)p+1);
printf("%d",p);
}
(a) 2 (b) 0 (c) junk value (d) 3

13.What would be the output of the following program.
main()
{
int i=10;
fn(i);
printf("%d",i);
}
fn(int i)
{
return ++i;
}
(a) 10 (b) 11 (c) 12 (d) Compilation error

14. What will be the value of i & j after the loop isexecuted?
for(i=0,j=0;i<5,j<25;i++,j++)
(a) i=4,j= 24 (b) i=24,j= 24 (c) i=25,j= 25 (d) i=5,j=25

15.What would be the output of the following program.
main()
{
int i,j;
i=10;
j=sizeof(++i);
printf("%d",i);
}
(a) 11 (b) 10 (c) 4 (d) compilation error

16.What would be the output of the following program.
main()
{
int i=7;
printf("%d\n",i++*i++);
}
(a) 49 (b) 56 (c) 72 (d) compilation error

17. What will the printf print?
main()
{
char *p,*f();
p=f();
printf("f() returns:%s\n",p);
}
char *f()
{
char result[80];
strcpy(result,"anything will do");
return (result);
}
(a) f() returns: anything will do (b) f() returns:
(c) compilation error (d) The printf statement is not going to be executed

18.How many times the following program would print 'Jamboree'?
main()
{
printf("\n Jamboree");
main();
}
(a) infinite number of times (b) 32767 times
(c) 65535 times (d) till the stack does not overflow

19.Notice the error in the default statement in the code snippet below.Will it give a compilation error?
main()
{
int a=10,j;
j=fn(a);
switch(j)
{
case 30: printf("the value is 30");
break;
case 50: printf("the value is 50");
break;
default:printf("the value is not 30 or 50");
}
}
fn(int a)
{
return (++a);
}
(a) Will display "the value is 30" (b) Will display "The value is not 30 or 50"
(c) Yes a compilation error would happen
(d) No compilation errors but there will be no output on the screen

20.What would be the output of the following program.
main()
{
struct emp
{
char name[20];
int age;
float sal;
};
struct emp e = {"tiger"};
printf("\n %d %f",e.age,e.sal);
}
(a) 0 0.000000 (b) Garbage values (c) Error (d) none of the above