Swift Interview Style: Duplicates in an Array
The beauty of interview questions are that the interviewer can ask follow up questions to challenge the candidate. For every solution that can be come up with, an extension task can be considered that push the candidate further and further and reveal their fundamental understanding of the principles in use.
Prerequisites:
- Arrays
The question
You have a sorted array. Remove duplicates.
Candidate questions
How large is the input {don’t worry at first} ?
What is the input type {an array of Characters}?
Can you give me an example {[“1”,”1",”2",”2",”3",”3",”3",”4",”4",”4",”4",”4",”5",”6",”6"]
->
[“1”, “1”, “2”, “2”, “3”, “3”, “4”, “4”, “5”, “6”, “6”]}?
Initial solution — Remove elements
We have to be careful here as it is possible that you can move outside the boundaries of the input array.
We solve this by using a while loop as we remove elements, and only increment our index if we don’t remove an element.
step by step:
A more elegant (perhaps) solution is to reverse the list before traversing and looking for repeated elements.
Initial solution — Criticism
Removing an element is an O(n) operation, meaning this solution is quite slow. Can you speed it up?
Dictionary solution
One possible solution is to traverse the input list, and use a dictionary to count the number of each element.
Then the dictionary itself will need to be sorted, and the elements written out:
Dictionary solution — Criticism
That solution uses extra space. Can you think of a solution which is in-place and does not use extra space
In place solution
One way of doing this is to use multiple pointers.
Maintain a pointer that is the end of the list of single elements (first pointer). Then traverse the list, and copy the current element to the first pointer if it is not a repeated element. When you reach the end of the list, the output list is the array of elements between the first element and the pointer to the end of the array.
Where to go from here
You could get asked how to remove the duplicates where there are 2 + duplicates in the list. Or how this might work with a reversed list.
The Big O notation of the final solution is O(n) — does it always traverse every element?
What is a real-world application of this algorithm?
There are loads of questions to do with every algorithmic challenge. Do you have more?
Want to get in contact? Use the link here:
