Swift Interview Style: Duplicates in an Array

Image for post
Image for post

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:

Image for post
Image for post

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.

Image for post
Image for post

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:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store