This feels like it should be simple, but I'm just not getting it for some reason. I decided to take on an apparently common programming interview question to test my skillset:
"Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does."
(source: https://codefights.com/interview-practice/task/pMvymcahZ8dY4g75q)
I believe I have the correct code, but I can't get the loop to stop running. Given the example array, the function should return "3", since that is the first number that repeats (not the first number seen). However, no matter what I try, it either returns 2 or an error.
console.clear();
// create new object to store numbers and counts
var myObj = {};
// array for testing output
var arr1 = [2, 3, 3, 1, 5, 2];
// this will store the "key" number
var firstDuplicateFound = "";
function firstDup(a) {
// loop through each value in numerical array
a.forEach(function(num, i) {
// if associative array has property that is value of current num:
if ( myObj.hasOwnProperty(num) ) {
// increment value by 1
++myObj[num];
firstDuplicateFound = num;
// If first duplicate is found, the code should jump out of the
// loop and return from the function. It should NOT continue
// to process the code in the forEach. At one point, I tried
// "return firstDuplicateFound" here, but it just returned 2.
} else {
// create new array key and assign count of 1
myObj[num] = 1;
}
if (firstDuplicateFound && firstDuplicateFound != NaN) {
return firstDuplicateFound;
}
});
console.log(myObj);
return false;
}
var firstDupNumberFound = firstDup(arr1);
console.log("firstDupNumberFound = " + firstDupNumberFound);I've tried everything I can think of. I read about the difference between break and continue and tried using "break" right after assigning firstDuplicateFound = num, but it just gives me an error about "illegal break statement":
Uncaught SyntaxError: Illegal break statement at Array.forEach () at firstDup (:15:4) at :49:27 firstDup @ VM80757:15 (anonymous) @ VM80757:49
I tried moving the break to other positions, but everything I have read says break only works inside a loop.
Then I dug a little deeper and found several articles stating that return is correct statement to exit out of the function. When the first duplicate is found, I want the loop to stop executing and the function to exit and return the value of "num", without processing the rest of the numerical array. This does not happen. I have tried return, return firstDuplicateFound, and return false in various locations.
What am I doing wrong and how do I get the code to return the first duplicate found?
What am I missing in my understanding to make this work? Shouldn't "return firstDuplicateFound" be the best solution? I'm really trying to get a solid understanding of how to do this right.
Stack Overflow asked me if (this post, the one you are reading) is a duplicate of this post here, and asked me to explain why not if I disagreed. This is not a duplicate - even though similar answers are offered, and it seems the poster of the other question is working on a similar problem - because my question is about something not working at all, whereas the other question is about optimizing something that already works.
Also, someone who is looking for "why doesn't this work" is not likely to see "how to optimize ..." and think that pertains to them. A thing has to be working first before one can begin to start optimizing it.
What went wrong :
You simply can't return/exit from a forEach loop. That's it. So if you want to code imperative and not functional (by using break, continue, return) you should use a simple old style for loop:
function firstDup(array) {
//A hashtable to check for dupes
const hash = {};
// loop through each value in numerical array
for(var n of array){
if(n in hash){
return n;
} else {
hash[n] = true;
}
}
return false;
}
My approach:
As far as I understand
return the number for which the second occurrence has a smaller index than the second occurrence of the other number does
Just means return the first dupe
And that's quite easy:
function dupe(array){
return array.find((n,i) => array.indexOf(n) !== i);
}
or using a set:
function dupe(array){
const set = new Set;
return array.find(n => set.has(n) || (set.add(n), false));
}