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.

Question

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.

Anonymous · Accepted Answer

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.

farble1670 · Answer

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.

Anonymous · Answer

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.

fearEar · Answer

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

fearEar · Answer

oh efficiency  is O(n)

Motorola Mobility

Motorola Mobility interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?