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.
Answer

Interview Answer

8 Answers

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 <= 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 <= inpArr.length - 1 && 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<=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<=inpArr.length - 1; i++) {
            if(inpArr[i] == inpArr[i+1]) {
                int repeats = 1;
                opArr[opPos] = inpArr[i];
                int j = i + 1;
                while(j+1 <= inpArr.length - 1 && 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<=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

Add Answers or Comments

To comment on this, Sign In or Sign Up.