Given a sorted array of integers, write a function to remove any duplicates. Give algorithm, then code and finally list how you would test your program.

Question

Jason · Accepted Answer

The easy way is to create a new array with the same size.
Add only non repeating integer to the new array.
Return new array in the end of loop

For in place solution:
loop through array
compare n+1 with n
create one reference idx  and set idx = n
loop through array from 0...n and n+1 < length of array
if array[n+1] == array[idx], set array[n+1] == null
else array[++idx] = array[n+1]

Jason · Answer

To test you can want to have various array size
1. array = null
2. array is zero
3. array is xth size but some are null values
4. array does not have duplicate values
5. array have all the same values
6. array with multiple duplicate values
7. array with one value
8. array with duplicate values in the end
9. array with duplicate values in the beginning
10. array is not ordered, function should check if it is ordered

Bob · Answer

Adding the elements of the array to a HashSet would remove the duplicates without requiring extra logic.

Ryuho · Answer

In C++11, assuming that the function takes a pair class with array and array size, and returns a pair with array and array size. Slightly inefficient memory wise, but it's a lot simpler and it works.

pair deduplicateIntArray(pair input)
{
	set mySet;
	mySet.insert(input.first, input.first + (input.second));
	int* newArray = new int[mySet.size()];

	int idx = 0;
	for(auto s : mySet)
	{
		newArray[idx] = s;
		idx++;
	}
	return make_pair(newArray,idx);
}

Google

Pregunta de entrevista de Google

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo