The Remove Duplicates From A List Interview Question
March 20th, 2010
A very common interview question at technical companies like Microsoft and Google is some variation of, “How would you remove duplicates from a list?” The first step when answering this, or any other, question is to qualify it to make sure you understand exactly what the scenario is. One of the reasons this is a common question is that there are many ways to approach the problem. One way is to sort the list, then iterate through the list checking to see if the “next” item equals the “curr” item. Another approach is to iterate through the list, placing each item into a hash table, using the built in functionality to not add duplicates, and then scan through the resulting hash table. Yet another way is to perform a O(n^2) double scan through the list using nested for loops. The important thing is to demonstrate several different ways and explain when each approach is appropriate. I haven’t checked, but I’ll bet Wikipedia has a good discussion somewhere of the topic of duplicate removal.
Entry Filed under: Interviewing
Trackback this post