Motorola Mobility

Interview Question

Software Engineer Intern Interview Sunnyvale, CA

Write a function in Java that will take a sorted array of

  ints, possibly with duplicates, and compact the array removing all the duplicate numbers. That is, if the contains the numbers - 1, 3, 7, 7, 8, 9, 9, 9, 10, then when the function returns, the contents should be - 1, 3, 7, 8, 9, 10. Be sure your answer is as efficient as possible. Describe the efficiency of your algorithm using big O notation.
java, algorithm

Interview Answer

5 Answers


create temp array;
starting from the second element copy the i'th char if input[i-1] != input[i]
return temp

fearEar on Jun 8, 2009

oh efficiency is O(n)

fearEar on Jun 8, 2009

you can't create a temp array because you don't know the size until after you process. you could count the number of dupes in one pass, then allocate the array, then do the compacting. or you could allocate the array equal to the size of the original and accept that some elements will be null (or -1, or whatever). or you could use some dynamic data structure like an ArrayList to build the compacted list and convert it to an array at the end (ArrayList.toArray(...)).

regardless, it's still O(n) and uses 2x the memory.

makes me think there's a more elegant solution though.

farble1670 on Sep 30, 2010

do bitwise XOR of consecutive numbers. When the xor is 0, you know the number is duplicate. It will require single pass thru the array to identify number of duplicates in the array.

Anonymous on Mar 13, 2011

you can also use 2 index, at the beginning they both = 0, then you will have a previous and a next, if previous value = next value increment next index until next value != previous value then increment previous index by 1 and assign "next value" to it and so forth until you "next index reach the end of the array and then increment all previous index assigning null or -1.
O(n) without using 2x memory. Anyway, I hope it is not too confusing, its late but I hope you got the big picture.

Anonymous on Aug 2, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.