Microsoft Microsoft Interview Question for Software Engineer in Tests

• 0

Team: Office
Country: United States
Interview Type: In-Person

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

``````bool IsSet(int * a, int n)
{
int t = 0;
while (t < n)
{
if (a[t] <= 0)
return false;
if (t == 0)
continue;
if (a[t] <= a[t - 1])
return false;
t++;
}
return true;
}``````

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

There is a minor problem here: The question doesn't say whether it is incremental or not.

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

this solution doesn't address one of the condition mentioned;
the "non-duplicates".

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

@sw, the only way there can be any duplicates without violating the sorted order property is two same numbers being consecutive which is checked by the <= operator. Otherwise duplicates would violate the sorted order property.

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

cltpyrc -> Nice explanation ;) ..

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

@Anonymous: sets are incremental..isnt it?

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

isnt this an infinite loop, or am i mistaken?
the continue makes the next iteration start and t is never incremented

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

infinite loop is there. just put a t++ before the continue for that if statement..

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

condition:
if (t == 0) {
continue;
}
can be removed. Just start t = 1

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

Following condition could be placed before the loop too : if (a[0] <= 0)
instead of if(a[t] <= 0) inside the loop

if first element is greater than zero, all other elements in the set would be greater than zero as set is expected to be incremental, else it is caught in the condition :
if (a[t] <= a[t - 1])

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

I think the problem can be solved using a bit vector.
public static boolean isUnique(int[] a){
int prev = 0;
int res;
for(int i=0; i<a.length;i++) {
res = prev ^ (1<<a[i]);
if(res<prev) return false;
prev=res;
}
return true;
}

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

Please tell if there are any mistakes.. :)

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

Let n = array size;
int i = 1;
bool ifArrayIsSet(int* arr, int n ) {
int i = 1;
while( i < n && arr[i] > 0 && arr[i] > arr[i-1] && i++);

if(i == n)
return true;
return false;
}

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

``````#include<stdio.h>

void main()
{
int a[10],i,k=1,l;
printf("\nenter elements");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
i=0;
if(a[i]>=0)
for(i=0;i<9;i++)
if(a[i]>a[i+1])
{
k=0;
break;
}
else
k=1;
else
printf("Not a set");
if(k==0)
printf("it is not a set");
else
printf("SET");
}``````

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

1. sort direction is not an issue, cause if descending, just traverse the array from tail.
2. only check <= is fine, it will cover the duplicate case.
here is the c# code

``````public static bool IsSet(int[] array) {
if(array == null || array.Length == 0) return false;

if(array[0] <= 0) return false; // if ascending, only need to check once
for(int i=0; i<array.Length-1; i++) {
if(array[i] >= array[i+1]) return false;
}
return true;
}``````

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

Any solution to check if the array has duplicates will take O(n^2) time or O(n) time with O(n) space.

Sorted and positive numbers can be checked otherwise in O(N)

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

I think this problem can be solved by Balanced binary search tree.
Case 1:
when we scan the array simple check it is positive or not.
Case 2:
When you create the BST inorder traversal will automatically gives you element in sorted order.
Case 3:
For searching complexity will be log(n) which also for inserting the element.

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

wont creating bst make it nlog(n) solution? Why not do it simply in linear scan by comparing each element to 0 and previous one?

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.