## Microsoft Interview Question for Software Engineer / Developers

Team: MS Office Platform
Country: India
Interview Type: In-Person

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

why O(nlgn) ? if the array is sorted and rotated then use binary search to find the element in O(lgn) time.

``````public static int searchInRotatedArray(final int[] a, final int key) {
final int n = a.length;
if (a[0] == key) {
return 0;
} else if (a[n - 1] == key) {
return n - 1;
}

int l = 0;
int r = n - 1;
int m = 0;
while (l <= r) {
m = (l + r) / 2;

if (a[m] == key) {
return m;
} else if (a[m] < a[l]) {
if (key > a[m] && key <= a[r]) {
l = m + 1;
} else {
r = m - 1;
}
} else {
if (key < a[m] && key >= a[l]) {
r = m - 1;
} else {
l = m + 1;
}
}

}

return -1;
}``````

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

``````int binary_serach(int* data, int size, int x) {
if (!data)
return -1;
int l = 0;
int r = size-1;
while (l<=r) {
int m = (l+r)/2;
if (data[m] == x)
return m;
if ((data[l] < data[m] && x>=data[l] && x<data[m]) ||
(data[l] > data[m] && (x>=data[l] || x<data[m])))
r=m-1;
else
l=m+1;
}
return -1;
}``````

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.

### 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.