Search Algorithms

Linear Search

It is the easiest search algorithm.The algorithm intends so check each and every element and stops when the required element is found.

Implementation

int getindex(int a[], int n, int target)
{
for(int i = 0; i < n ; i++)
if (a[i] == target) { return i; }
return -1;
}

void main()
{
int a[]={3,4,5,2,6,8,10};
int n=7; //no. of elements in the array
int index=getindex(a,n,6);
printf("index of 6 in array "a" is::%d",index);
}

explaination::The above code returns the index of element to be found...


Binary Search

Binary Search use Divide and rule algorithm to find the reqd. element in an already sorted list. The algorithm is deceptively simple. Pretend I was thinking of a number between 1 and 100. Every guess you take, I'll say higher or lower. The most efficient way to discover my number is to first guess 50. Higher. 75. Lower. 62. Higher 68. Yes!

Implementation

int findIndex(int a[],int n, int target) {
return binarySearch(a, target, 0, n);
};

int binarySearch(int a, int target,int start,int end) {
if (start > end) { return -1; } //does not exist

int middle = (start + end) / 2;
int value = a[middle];

if (value > target) { return binarySearch(a, target, start, middle-1); }
if (value < target) { return binarySearch(a, target, middle+1, end); }
return middle; //found!
}

int a[]={1, 4,6,8,9,12,32,45,56,58,78};
int n=11;
findIndex(a,n,12);

Microsoft Placement Paper

My experience....MICROSOFT....conducted on 22nd Dec 2010

First round was a written test of an hour. There were 6 questions(4 programming and 2 test cases) 10 marks each.

1)find output of following code??

void main()

{

void *ptr;

char *a='A';

char *b="TAN";

int i=50;

ptr=a;

ptr=(*char)malloc(sizeof(a));

printf("%c",*ptr);

ptr=i;

ptr=(*int)malloc(sizeof(i));

printf("%d",++(*ptr));

ptr=b;

ptr=(*char)malloc(sizeof(b));

printf("%c",++(*ptr));

}

ans: A51AN

2) Write a program that takes a no. from user and prints the no. subtracting 5 each time from the no. till the no. doesn’t crosses/reaches 0.And again prints the nos. now increasing 5 each time till the no. doesn’t reaches/crosses original no.

don't use any loops or goto stmnt.And don't declare any local variables.

ans: use recursion.

3)convert a no. from string to integer.

eg: str:"1234"

convert to int a=1234;

ans:while(*ptr!=NULL)

{

a=(a*10)+(*ptr-48);

}

4) Find the subarray of an array that has the greatest sum? Array contains both +ve as well as -ve nos.

ans:I did it using 3 loops but when I went for the 2nd technical round the interviewer told me a very simple and optimal program for the same.

sumtillnow=0;

sum=0;

for(i=0;i

{

sumtillnow+=a[i];

if(sumtillnow>sum)

sum=sumtillnow;

if(sumtillnow<=0)

sumtillnow=0;

}

5) Write test cases for a student regestration form.

6) Write test cases for a web search engine.

--------------------------------------

20 students were shortlisted after the written test.

1st technical round...

First he saw my resume and asked me few ques about my BE Project and the TE Project.

Then I was asked many questions from OOP concepts...mainly about virtual functions,pure virtual functions(application based) and v-table etc.

Then he asked me some ques from OS...

1) Critical section

2) Semaphores

3) Processes

4) Threads

5) Reader Writers problem

Then there were a few questions from Logic Gates

1) Half adder....circuit and functionality

2) Full adder....circuit and functionality

Then he asked me 2 puzzles...

1) There are 3 buckets full of oranges, apples and mixture of both. Buckets are labeled with orange, apple and mixture. And it is known that all labels are false. Now just pick up 1 fruit from any 1 of the buckets and label all of them correctly.

Ans ::hint: pick the fruit from mixed labeled basket.

2) There are 5 bags containing marbles. All are identical.4 of them weight 9g one of them is 10g.you have a weighing balance. In one go can u tell which is the bag with 10g.

ans::i was blank.min I could produce was in 3 chances.

-------------------------------------------------

In 1st round other students were also asked ques. from DBMS (Normalization, few queries and ER diagrams).

And ques from TOC (Finite automata machine)..... Draw a finite automata to accept a binary no. that is divisible by 5.

-------------------------------------------------

2nd Round

He asked me some test cases.

Then the interviewer asked me to optimize certain codes...

1)4th ques of the written exam. (Subarry sum)

2) An array of n elements contains elements 1-(n-1) in random order and 1 entry is duplicated. Find the duplicate entry???

ans::I told him to take one more array. Now pick the elements from 1st array and put them into respective index of the 2nd array. If duplicate occur then report and end the loop.

he asked me to optimize the code. Then I suggested a BST. He asked me to optimize more and more and more and more......this ques fucked me..

But somehow I was advanced for the 3rd round..I was very excited.

---------------------------------------------------

3rd Round

HR...Some test cases and Why should I take you in Microsoft.

---------------------------------------------------

But unfortunately I wasn’t able to make it :( But may be these questions will help you for your placements. Best of Luck to all...