## Microsoft Interview Question for Interns

• 1
of 1 vote

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
14
of 16 vote

n=no of elements
x element to found

i=0;
while(i<n && a[i]!=x)
{
diff=abs(x-a[i]);
i+=diff;
}
if(i>=n)
print "element no found";
else
print i;

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

This is a good solution but the problem is the following testcase:

2,2,2,2,2,2,2,2,2,2,2,2,2,2,3

So if you are searching for 3 it will traverse the whole array anyway. I don't know of a better solution, but for the above test case it is O(n).

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

O(n) is a lower bound for the worst-case. Consider that in the example
2,2,2,2,2,2,2,2,2,2,2,2,2,2,3 the value of 3 could have been anywhere and the input would still have been legal. Any location you inspect that has a 2 reveals no information about the location of the 3. As long as you haven't found the 3 yet and there's some entry you haven't inspected, the 3 could be there. Any correct algorithm will therefore have to read all of the input in the worst case.

The best we can hope for is a heuristic that requires fewer than N array reads on some (but not all) inputs, which is exactly what this answer provides.

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

Assuming under conditions given abs() can return either 0 if we found our element, or 1 otherwise, this algorithm is eve worse than brute force!
In case of for(i=0; i<n; ++I) { if(a[i]==x) return i; } you have the same result, but without calculating abs on each step.

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

Find the Min and Max of Array and see if the given number is in the range.

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

What do you mean by "find a given number of x in the array"?
let say the array is: 4,4,5,6,7,6,5,5,4,3,2,3
and I want to find search for "6" then I should return "4" because the first "6" is in the 4rd place from the beginning? or "2" beacuse there are 2 occurrences of 6 in the array?

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

Right, returning the first index is good enough.

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

``````int CountOfX(vector<int> a, int x)
{
int occurences = 0;
int i = abs(a[0] - x);							// min index to look for values
int end = a.size() - abs(a[a.size() - 1] - x);	// max index to look for values
while (i < end )
{
if (a[i] == x)
{
occurences++;
i++;
}
else
{
i += abs(a[i] - x);						// this is the minimum index our value can now be at
}
end = end - abs(a[end - 1] - x);			// based on our current max, this is the maximum distance
}
return occurences;
}``````

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

``````//Naive O(n)
int find(int value, int[] a) {
int n = a.Length;
for (int i=0; i<n; i++) {
if (value==a[i])
return i;
}
return -1;
}

//binary search ... ish
int find(value, a) {
int n = a.Length;
Queue q = new Queue();
q.Enqueue({ 0,n/2,n }); // START,MID,END of a subrange to search
while (q.Count > 0) {
int[] sub = q.Pop();
int start=sub[0], mid=sub[1], end=sub[2];
if (a[mid]==value) {
return mid;
}
int gap = mid - start;
int range = Math.Abs(a[mid]-value);
if (gap>=range) {
q.append( (mid-start)/2+start, start, mid);
}
gap = end-mid;
if (gap>=range) {
q.append( (mid-start)/2+mid, mid, end);
}
}
return -1;
}

//index    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18
int[] a = {7,8,9,8,8,7,6,5,4,5,5,4,3,3,2,2,4,5,6}
int i = find(2, a);
System.Console.WriteLine(i); //output 14``````

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

the binary search u implemented is not O(log n).. yes, it splits the array in half but you will search both sides so it is still O(n)

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

good point, it's not logn, but it is dependent on the array and the search value, meaning that subsets of the array are skipped over, the tricky part is that it could be in both sides

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

int count()
{
int a[10] = {4,5,5,2,4,5,5,3,7,1};
int i,j,temp,min=0,max=9, search= 5,count =0;
for(i =0;i<9;i++)
{
for(j=0;j<9-i;j++)
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
while(1)
{
i = (min + max)/2;
if( a[i] < search)
{
min = i;
}
else if(a[i] >search)
{
max = i;
}
else
{
break;
}
}
for(i = min ;i<max;i++)
{
if(a[i] == search)
{
count++;
}
}
printf("%d count %d\n",search,count);
}

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

``````int srchEff(int arr[10],int iSrchEle)
{
int i=0;
int iDiff  = iSrchEle - arr[i];
while(i<10)
{
if(arr[i]==iSrchEle)
{
cout << "found the element  "<< i ;
return 0;
}
else if(iDiff == 1 || iDiff ==-1)
{
i++;
continue;
}
else
{
i=i+2;
continue;
}
}``````

}

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

``````int srchEff(int arr[10],int iSrchEle)
{
int i=0;

while(i<10)
{
int iDiff  = iSrchEle - arr[i];
if(arr[i]==iSrchEle)
{
cout << "found the element  "<< i ;
return 0;
}
else if(iDiff == 1 || iDiff ==-1)
{
i++;
continue;
}
else
{
i=i+iDiff;
continue;
}
}``````

}

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

Here is my algorithm:

1. check the difference between the number and the first element of the array
2. If the absolute value of the difference is zero, return true;
3. if the difference isn't zero, check the number whose index is equal to the difference.
4. Repeat step 1 to 3 until the index you find in step 3 is greater than the array size.

Here is a C++ implementation:

``````int find(vector<int> &A, int start, int v) {
if(start >= A.size()) return false;
if(A[start] == v) return true;
int offset = abs(v - A[start]);
return find(A, start + offset, v);
}``````

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

``````int FindIndex(int[] arr, int num, int start=0)
{
if (arr[start] == num) return start;
int diff = arr[start] - num;
if (diff < 0) diff *= -1;
return FindIndex(arr, num, start + diff);
}``````

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

``````int foundInPlusMinus1VectorINT(int ai_number, std::vector<int> ai_vector, int ai_l, int ai_r)
{
int med = (ai_l + ai_r) / 2;

int delta = std::abs(ai_number - ai_vector[med]);

if (delta == 0)
return med;

int ret;

if (delta <= med - ai_l + 1)
// Look in r side ...
if ((ret = foundInPlusMinus1VectorINT(ai_number, ai_vector, med + 1, ai_r)) >= 0)
return ret;

if (delta <= ai_r - med + 1)
// Look in r side ...
if ((ret = foundInPlusMinus1VectorINT(ai_number, ai_vector, ai_l, med - 1)) >= 0)
return ret;

return -1;
}

int foundInPlusMinus1Vector(int ai_number, std::vector<int> ai_vector)
{
return foundInPlusMinus1VectorINT(ai_number, ai_vector, 0, ai_vector.size() - 1);
}``````

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

``````int find(int[] A, int x) {

int i =0;
int n = A.length;

while(i < n) {
int j =Math.abs(A[i] - x) + i;
if (A[j] ==x) {
return j;
}
i = j;
}

return -1;

}``````

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

``````import java.util.*;
public class GivenNumberX {
public static void main(String[] args){
int i= 0;
int count=0;
int difference = 0;
int input[] = {5,6,7,6,5,5,4,4,3,2,1,2,3};
System.out.println("Enter the value of x");
Scanner input1= new Scanner(System.in);
int x = input1.nextInt();
while(i< input.length && input[i]!=x){
difference = Math.abs(x - input[i]);
i = i +difference;
}
if(i > input.length){
}else
System.out.println("First position for "+ x + " is " + i);
for(i=0;i<input.length;i++){
if(input[i]==x){
count++;
}
}
if(count==0){
}else
System.out.println("The number of times "  + x +  " appears in the array is " + count);
}
}``````

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

``````/// <summary>
/// Find if the element is present in the array.
/// Property of array is that each neighbor element is not more than 1 difference
/// </summary>
/// <param name="a">Array to be searched</param>
/// <param name="x">Element to be searched</param>
/// <returns>Returns the index of the element</returns>
public static int FindElement(int[] a, int x)
{
if (a == null || a.Length == 0)
{
throw new ArgumentNullException("a");
}

for (int i = 0; i < a.Length; )
{
int jump = 1;
if (x == a[i])
{
return i;
}

jump = Math.Abs(x - a[i]);

i += jump;
}

return -1;
}``````

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

find last-first element.
case 1.If the difference is more than one it was an increase way.
case 2:If the difference is less than one it was a decreasing array.
case 3:If the difference is 0 it means that array increase and then decreased with flip exactly in between.In all cases you can do a binary search.

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

``````A <- Input Array
X <- Key
I = 0;N = A.Size;
While(i < N)
If X > A[i] or X < A[i]
i = i + |X-A|
else
Return i
end``````

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.