## Microsoft Interview Question for Software Engineer / Developers

• 0

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

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

Simple binary search with a tweak:

``````public static int searchFirstOccurance(final int[] a, final int key) {
if (a[0] == key) {
return 0;
}

int l = 0;
int r = a.length - 1;
int m = (l + r) / 2;
int keyPosition = Integer.MAX_VALUE;

while (l <= r) {
m = (l + r) / 2;
if (key == a[m]) {
keyPosition = Math.min(keyPosition, m);
r = m - 1;
} else if (key < a[m]) {
r = m - 1;
} else if (key > a[m]) {
l = m + 1;
}

}
return keyPosition == Integer.MAX_VALUE ? -1 : keyPosition;
}``````

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

Do you really need that code:

``````if (a[0] == key) {
return 0;
}``````

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

Worst case would still be O(n/2) or O(n) instead of O(nlogn).
Imagine array as { 1, 1, 1, 1, 1, 1 } find index of 1
here mid would be index 3. Going backwards/forwards to find the first/last index of 1 would be maximum n / 2 traversals. That being said, its going to be O(n)

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

``````// Idea: use binary search: if to find first element, end = median - 1.
//          If to find last element, begin = median + 1
int Min(int a, int b)
{
return (a <= b ? a : b);
}

int Max(int a, int b)
{
return (a >= b ? a : b);
}

int FindFirstIndex(int *arr, int begin, int end, int element)
{
int index = -1;
int med = -1;

if (arr && begin <= end)
{
while (begin <= end)
{
med = (begin + end) / 2;
if (arr[med] == element)
{
index = (index == -1) ? med : Min(index, med);
end = med - 1;
}
else
{
if (arr[med] < element)
{
begin = med + 1;
}
else
{
end = med - 1;
}
}
}
}

return index;
}

int FindLastIndex(int *arr, int begin, int end, int element)
{
int index = -1;
int med = -1;

if (arr && begin <= end)
{
while (begin <= end)
{
med = (begin + end) / 2;
if (arr[med] == element)
{
index = (index == -1) ? med : Max(index, med);
begin = med + 1;
}
else
{
if (arr[med] < element)
{
begin = med + 1;
}
else
{
end = med - 1;
}
}
}
}

return index;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Here is my solution in C#

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AlgoSolution
{
class BSearch
{
static void Main()
{
int[] num = new int[] { 1 , 1 , 2 ,2 , 3 ,3, 4 };
Console.WriteLine(LowerBound(num, 4) + 1);
Console.WriteLine(UpperBound(num, 3) - 1);
}
static int LowerBound(int[] data, int num)
{
int min = 0;
int max = data.Length;
while (min < max)
{
int mid = min + (max - min + 1) / 2;
if (data[mid] < num)
{
min = mid;
}
else
{
max = mid - 1;
}
}
return min;
}

static int UpperBound(int[] data, int num)
{
int min = 0;
int max = data.Length;
while (min < max)
{
int mid = min + (max - min ) / 2;
if (data[mid] > num)
{
max = mid;
}
else
{
min = mid + 1;
}
}
return min;
}
}
}``````

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.