Implement Even Occurrence in JavaScript

Interview Questions
September 21, 2016

This is the second in a series about programming interview questions and how to think through and solve them! Have you already solved this one? Check out all permutations of a set.

This article is covering the even occurrence programming interview question in JavaScript. Find the first item that occurs an even number of times in an array. Remember to handle multiple even-occurrence items and return the first one. Return null if there are no even-occurrence items. For example, if given the input of [1, 2, 2, 3, 4, 4, 4, 4], the output should be 2.

Analysis

My first thought was to use an object to store each value as a key, then associate it with the count of each value. From there, we know we can’t just loop through the object because an object doesn’t keep order like an array.

We can then loop through the original array and check to see if the current value has an even number of occurrences within the object. If we find one, we’ll return that first value. If we don’t come across one, we have to return null.

Pseudocode

function evenOccurrence(array) Define storage Loop through input Add each unique value to storage, keep count of each value Loop through input Check to see if the current character inside storage is even return current character if nothing, return null

Time Complexity

The time complexity of the above algorithm should be the same as the number of items produced. Therefore, with an input size of n the time complexity is linear — O(n).

Code

// Prompt: Find the first item that occurs an even number of times in an array. Remember to handle multiple even-occurrence items and return the first one. Return null if there are no even-occurrence items. function evenOccurrence (array) { // Store counts var storage = {}; // Store each value within the storage object to keep count array.forEach(function(value, index) { storage[value] = storage[value] + 1 || 1; }); // loop through array to find first occurence of an even count for (var i = 0; i < array.length; i++) { var current = array[i]; if (storage[current] % 2 === 0) { return current; } } // If no even occurrence found, return null return null;

Nice job making it through this one! Work through the next one, all permutations of a set which is a very common one asked in advanced programming interviews.

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

More Blog Posts