Removing duplicates from an array

Question

I recently wrote this JavaScript algorithm for removing duplicates from an array as part of a job interview process, but was turned down for the position after submitting the code. I didn't receive any detailed feedback from the company, so I was wondering if a more experienced developer might be able to explain what I've done wrong here.

dedup = function(set){ //loop over function, removing second instance of matching values for (var i = 0; i < set.length; i++){ for (var j = i+1; j < set.length; j++){ if (set[i] == set[j]){ set.splice(j,1); i--; } //special case for objects if (typeof set[j] == 'object' && typeof set[i] == 'object') { //super special case for arrays if (Array.isArray(set[j]) && (Array.isArray(set[i]))) { if ( set[j].toString() == set[i].toString() ) { set.splice(j,1); i-- } } //loop over key-value pairs in sets of objects else { var firstObj = set[i]; var secondObj = set[j]; for (var key in firstObj){ //break loop if differences found if (firstObj.hasOwnProperty(key) == false) { break } else if (firstObj[key] != secondObj[key]){ break } else { set.splice(j,1); i-- break } } } } } } return set } console.log(dedup([1, 2, 2, 5, 2, 7, 3, 9, 1, 9])) // -> [1, 2, 5, 7, 3, 9] console.log(dedup([1, '1', 2, 0, false, true])) // -> [1, '1', 2, 0, false, true] console.log(dedup([8, 3, [1, 2], [1, 2, 3], [1, 2], [2, 1], true])) // -> [8, 3, [1, 2], [1, 2, 3], [2, 1], true] console.log(dedup([1, {a: 'b', c: 'd'}, {c: 'd', a: 'b'}, {e: 'f'}, 'b'])) // -> [1, {a: 'b', c: 'd'}, {e: 'f'}, 'b'] 

I've found the following possible problems:

1. Running time is \$\mathcal{O}(n^2)\$ - there may be a recursive algorithm which removes duplicates more effectively than nested for loops.
2. Code should be refactored rather than all in on big function.

I would greatly appreciate any thoughts on the problems that I've identified, or other issues with my code.

Answer 1

I'll start by trying to address your concerns.

1. Unless in special cases you can't make this function run in less than quadratic time. Typical linear time solutions in other languages involve generating hashes from values in the filtered array and then using a hash-table to filter out characters whose hash value appears to be the same. There is no standard way to obtain a hash of an object in JavaScript, however, some objects may be uniquely written to string, which can be used as their hash. So, there is an O(n) solution for an array of numbers, or an array of strings, but no such solution for an array of functions. JavaScript makes no guarantees with regard to transforming tail calls into iterations, so, if possible, an iterative solution would be better than recursive one.
2. Yes, it's certainly better to let one function do one thing.

Now, to the interviewer reaction: Passing an interview and writing good code aren't necessary (and, most unfortunately, aren't in most cases) the same thing. Interviewers typically want to see the code written in a particular way they believe it should be written. If your goal is to pass the interview, it is in your best interest to find out the exact requirements. Sad but true.

Now, assuming I would have to assess your code, here are the things that I'd find to be bad:

1. The code is too lengthy. It shouldn't take that much space to write it. (I later give my version of the answer).
2. Inconsistent spacing and brace positioning. This is certainly not a crime, but remember that I'm trying to assess your code from small cues. I wouldn't mind this as much, if, for example, I knew that the code was a result of several people working on the same code base, using different editors etc.
3. Changing the iterator inside the loop. Call me superstitions, but I'd make every possible effort to avoid it.
4. Comparison with Boolean constants. There is no need to do that (unless for diagnostic purposes). The language was designed in such a way that you never need to compare anything to true or false. But if you will continue writing JavaScript code, you will find that a lot of people don't understand this trivial concept.
5. You've decided to make the algorithm a destructive one. I.e. the function modifies the argument passed to it. There are reasons for having both versions. I, myself, expect the default to be non-destructive.
6. slice isn't really a way to go here. Not that it matters a lot on JavaScript, since arrays are typically implemented as hash-tables with integer keys, but, in general, the properties of array data structure make repeated slicing a lot more expensive than maintaining the index of last insertion (example follows).
7. Using typeof and other kinds of ad hoc typechecking to me always smell bad. There is a place for it, but in the context of this task it isn't required.

---

Non-destructive version:

function removeDuplicates(array, comparator) { var result = [], i; function insert() { var match, j; if (comparator) { for (j = 0; j < i; j++) { if (comparator(array[j], array[i])) { match = false; break; } } } else match = result.indexOf(array[i]) == -1; return match; } for (i = 0; i < array.length; i++) if (insert()) result.push(array[i]); return result; } 

Destructive version:

function deleteDuplicates(array, comparator) { var i, k = 1; function insert() { var match, j; if (comparator) { for (j = 0; j < k; j++) { if (comparator(array[j], array[i])) { match = false; break; } } } else match = array.lastIndexOf(array[i], k) == -1; return match; } for (i = 1; i < array.length; i++) if (insert()) array[k++] = array[i]; array.length = k; return array; } 

Note that it would be possible to make it even shorter, if I knew that user-provided comparison function isn't needed (isn't part of the task). I still chose to include the possibility, even though I wasn't sure about it because it seems like a good thing to include one in the function's interface. If I had to answer this interview question, I'd probably not bother writing a custom comparator just to save time and spare myself the possibility of making a silly error working on something which wasn't absolutely required.

Answer 2

Shortest javascript I can think of to do it:

function removeDupes(arr) { var hash = {}; return arr.filter(function(x) { var name = typeof x + x; return !hash[name] && (hash[name] = true); }); } 

...I suspect that it's probably not the fastest. Long handing the filter with a for or while loop is probably the fastest, thanks to bizarre speed tradeoffs in current Javascript engines.

If you MUST change the original array, the shortest way is probably to use Array.map() in a similar function, but store the indices of the duplicates, then splice them all out. Creating a new array of the items you need is almost always faster in Javascript, than attempting to manipulate an existing array though. (potentially at the cost of memory, but it's really hard to say what kind of things are going on inside the interpreter)

Answer 3

FWIW, it's pretty easy to do this with newer Javascript:

[...new Set(arr)] 

There are definitely some questions as to the speed of it, though.