Microsoft Interview Question
Software Engineer / DevelopersTeam: MS Office Platform
Country: India
Interview Type: In-Person
// 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;
}
Here is my solution in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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;
}
}
}
Simple binary search with a tweak:
- zahidbuet106 May 29, 2014