Microsoft Interview Question: In a given sorted array of in... | Glassdoor

## Interview Question

Software Development Engineer In Test (SDET) Interview Seattle, WA

# In a given sorted array of integers remove all the

duplicates.

2

Iterate the array and add each number to a set, if number is already there, it won't be added again, thus removing any duplicates. Complexity is Big-O of N

Anonymous on Mar 7, 2012
2

The array is already sorted, no need for a set.
example: 2,2,5,7,7,8,9
Just keep tracking the current and previous and the index of the last none repeated element when found a difference copy the element to the last none repeated index + one and update current and previous, no extra space and it will run in O(n)

Valentino on Mar 19, 2012
1

public RemoveDuplicates()
{
int[] ip = { 1, 2, 2, 4, 5, 5, 8, 9, 10, 11, 11, 12 };
int[] op = new int[ip.Length - 1]; int j = 0, i = 0; ;
for (i = 1; i &lt;= ip.Length - 1; i++)
{
if (ip[i - 1] != ip[i])
{
op[j] = ip[i - 1];
j++;
}
}
if (ip[ip.Length - 1] != ip[ip.Length - 2])
op[j] = ip[ip.Length - 1];

int xxx = 0;
}

Rajababu K on Apr 19, 2012
1

def removeDuplicatesSecondApproach(inputArray):
prev = 0
noRepeatIndex = 0
counter = 0
for curr in range(1,len(inputArray)):
if (inputArray[curr] == inputArray[prev]):
counter = counter + 1
prev = curr

else:
inputArray[noRepeatIndex+1] = inputArray[curr]
noRepeatIndex = noRepeatIndex + 1
prev = curr
inputArray = inputArray[:-counter]
return inputArray

A on Nov 3, 2015
0

if(inpArr[i] == inpArr[i+1]) {
int repeats = 1;
opArr[opPos] = inpArr[i];
int j = i + 1;
while(j+1 &lt;= inpArr.length - 1 &amp;&amp; inpArr[i] == inpArr[j+1]) {
j++;
repeats++;
}

opArr = Arrays.copyOf(opArr, opArr.length - repeats);
i = i + repeats;
}
else {
opArr[opPos] = inpArr[i];
}
opPos++;
}

for(int i =0; i&lt;=opArr.length-1;i++) {
System.out.println(opArr[i] + ",");
}

Anonymous on Jan 23, 2017
0

Apologies for the previous incomplete answer

int[] inpArr = {1,2,2,3,4,5,5,5,8,8,8,9,13,14,15,18,20,20};
int[] opArr = new int[inpArr.length];
int opPos = 0;

for(int i= 0; i&lt;=inpArr.length - 1; i++) {
if(inpArr[i] == inpArr[i+1]) {
int repeats = 1;
opArr[opPos] = inpArr[i];
int j = i + 1;
while(j+1 &lt;= inpArr.length - 1 &amp;&amp; inpArr[i] == inpArr[j+1]) {
j++;
repeats++;
}

opArr = Arrays.copyOf(opArr, opArr.length - repeats);
i = i + repeats;
}
else {
opArr[opPos] = inpArr[i];
}
opPos++;
}

for(int i =0; i&lt;=opArr.length-1;i++) {
System.out.println(opArr[i] + ",");
}

Anonymous on Jan 23, 2017
0

public static void removedup(int[] input){

int count =1;
int i=0;
for( ;i

Anonymous on Nov 13, 2018
0

public static void removedup(int[] input){

int count =1;
int i=0;
for( ;i

Anonymous on Nov 13, 2018