Microsoft Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 1 vote

int binarySearch(int a[], int key, int low, int high)
{
  if(low > high)
     return -1;
  int mid = (low + high) / 2;
  if( key == a[mid] )
     return mid;

  int result(-1);
  if( key < a[mid] )
  {
    if( key >= a[low] && key <= a[mid-1] )
        result = binarySearch(a, key, low, mid-1);
    else
        result = binarySearch(a, key, mid+1, high);
  } else {
    if( key >= a[mid+1] && key <= a[high] )
        result = binarySearch(a, key, mid+1, high);
    else
        result = binarySearch(a, key, low, mid-1);
  }

  return result;
}

- Manish July 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect Solution:)

- Monty January 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

try finding 15 in 5 7 11 13 15 1 2 3
sol:
instead of "if( key < a[mid] )", the check should be
"if (a[low]<a[mid-1])"
This allows looking for the half where the numbers are in perfect order and then checking if the key lies in that half or not

- Anonymous January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First find out where the array has a spike which can done in logn
divide the array into two arrays from that number
then search the number both the arrays

- Aditya July 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cant it be done in just one pass of O(log n)

- Soulslayer July 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done using merge sort, without merging.

- Badri July 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int search(int a[],int l,intr,int x)
{
while(l<=r)
{
mid=l+(r-l)/2;
if(a[mid]==x)
retun mid;
else if(a[l]<=a[mid])
{
if(x>a[mid])
l=mid+1;
else if(x>=a[l])
r=mid-1;
else
l=mid+1;
}
else if(x<a[mid])
u=mid-1;
else if(x<=a[r])
l=mid+1;
else
u=mid-1;
}
}

- brahmasani99 July 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Binary Search, Simple

- jitender July 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@brahmasani99: your code and idea is crct, only this lil modification is required in binary search
*Replace 'u' with 'r' in 2nd elseif of your code

- jitender July 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@brahmasani99
The code wont work in case the input is -456789123 and we are searching for 2.

- rahul July 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int search (char * a , char x) {

int low=0;
int up =sizeof(a)-1;

int mid= low+up-low/2;
while(low<=up) {
if (x==a[mid]) {
return x;
}
if(a[low] < a[mid]){
if (x<a[mid])
up=mid-1;
else
low=mid+1;
}
else if(x > a[mid])
r=mid-1;
else
l=mid+1;

}

}

- rahul July 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Cant it be done in just one pass of O(log n)

- Soulslayer July 17, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More