DEV Community

loading...
Cover image for And then the interviewer asks, "Can you do this with less code?"

And then the interviewer asks, "Can you do this with less code?"

Michael Solati
Developer 🥑 for Google with a love for Java (think Android), Java (think Starbucks), and JavaScript.
・3 min read

I LOVE fun solutions to interview problems. When prepping for interviews, I believe it's important to understand the capabilities and data structures in any given language as they can help you solve menial problems more efficiently.

An interesting interview problem I once had was, "Given an array of n numbers, how would you find if there are any duplicates?"

When faced with this problem as a junior JavaScript developer, I thought the solution would be simple. Just sort the array and then loop through it, while comparing the current index with the previous index. If they match, a duplicate is found!

const duplicateCheck = (numbers) => {
  // Sort the numbers
  numbers = numbers.sort();

  // Loop through the numbers
  for (let i = 0; i < numbers.length; i++) {
    if (i > 0) {
      // Compare the current index with the previous
      if (numbers[i] === numbers[i-1]) {
        // If they match we found a duplicate, we can stop here
        return true;
      }
    }
  }

  return false;
};

Sure this works, and your interviewer seems happy, but then they ask, "Can you make it faster?" Then you realize that maybe this isn’t the best solution... While the initial sort is fairly fast, running with a time complexity of Θ(n log(n)), we also have a loop after it with a time complexity of Θ(n). At the end of the day, the function itself runs at Θ(n log(n)) and it may not be the fastest solution.

Okay, let's simplify this to a single loop. We could just loop through the unsorted array and keep track of the values already found. If we end up finding a value we already checked, then we know we have a duplicate and we can stop there.

const duplicateCheck = (numbers) => {
  // Store found numbers
  const found = {};

  // Loop through the numbers
  for (let number of numbers) {
    // If number has been seen
    if (found[number]) {
      // End it here, we found a duplicate
      return true;
    } else {
      // If we didn't see it yet, let's log that we've seen it once
      found[number] = true;
    }
  }

  return false;
};

This is neater and faster! Its time complexity is now Θ(n) since we loop through the array, but we skip the sort. This is a faster solution, and you start to feel good about how the interview is going. And then the interviewer asks, "Can you do this with less code?"

After your heart skips a beat and dread sets in, you remember something your friend (me) said: "It's important to understand the capabilities and data structures in any given language." In JavaScript, you have access to the Set object!

Set objects are collections of values. You can iterate through the elements of a set in insertion order. A value in the Set may only occur once; it is unique in the Set's collection.

So you write the following:

const duplicateCheck = (a) => new Set(a).size !== a.length;

By passing the array into a new Set, you know that the Set will not allow for any duplicate elements to be added. You now have an iterable without duplicates. The final step is to compare the size of the deduped Set against the length of the original array. If they're the same, then there are no duplicates. If they're different, you know that duplicates were removed.

You now have a solution that keeps the time complexity of Θ(n) without the need of a for loop and without needing to keep track of numbers already seen. Instead, you have a neat one-line solution.

I love these one-line solutions! Hopefully, you found this helpful. If you have any interesting or clever solutions to interview questions, I'd love to hear them in the comments. Or if you have a better solution to finding duplicates in an array, I'd love to hear that too.


To keep up with everything I’m doing, follow me on Twitter and dev.to. If you’re thinking, “Show me the code!” you can find me on GitHub.

Discussion (25)

Collapse
dak425 profile image
Donald Feury

My answer to "Can you make it faster" is:

Do we need to? Has this become a bottle neck performance wise?

If not, don't care, lets spend time building a better product where it actually matters.

Collapse
twistacz profile image
Michal Haták

While I completely agree with that, I think main purpose of that excercise is to identify that developer know what performance limits of that code are.

I mean, You don't have to worry about performance issues when your devs are delivering optimized code by default, while avoiding premature optimizations :)

Collapse
dak425 profile image
Donald Feury

Of course, if they answer with "Lets assume that yes it has become/will become a bottle neck", then I would do my best to optimize.

Collapse
ky1e_s profile image
Kyle Stephens

^^^^ This ^^^^

Users don't care how a product is built. They care what the product is and that it solves their problems.

Collapse
dak425 profile image
Donald Feury

And this extends beyond programming

Hows the marketing?
Hows user retention?
Is it actually solving the target group's problem?

You can have the most efficient and well engineered product but if no one knows about it or it isn't solving their problem, none of that matters

Collapse
ahferroin7 profile image
Austin S. Hemmelgarn

OK, now I'm curious: Does the ECMA standard actually guarantee Θ(n) time complexity for instantiation of a Set from an arbitrary Array?

I could easily see all the implementations happening to have Θ(n) time complexity for it, but unless the standard says that it always will be, you can't really say it's Θ(n) without specifying an implementation.

Collapse
michaelsolati profile image
Michael Solati Author • Edited

So the first method is Θ(n log(n)), Mozilla and Google's implementations are a Merge Sort and Timsort respectively.

As for the the ECMA standard for a Set, internally they're recommended to use hash tables (or something similar). Insertion in hash tables run at Θ(1), so an array of n elements would reasonably be Θ(n).

Collapse
polmonroig profile image
Pol Monroig Company

Well yes, but worst case of hash tables is linear. If you don't mind the space you can create an auxiliar array and mark the positions. This is the "same" idea used in the hash table but it guarantees a O(n) solution. This solution requires O(n) extra space complexity, but hash table in worst case is also O(n) ( when all numbers are different)

Collapse
leob profile image
leob

Good point, the fact that it's built-in doesn't necessarily mean faster.

Collapse
cullylarson profile image
Cully Larson • Edited

Great idea for an article. It's a good reminder that interviewers may want to drill down into a question. Just FYI, the original function is O(n log(n) + n) which is O(n log(n)). It isn't O(n). So your second version is actually quite a bit faster. Also, big-theta (Θ) is different from big-oh.

Collapse
michaelsolati profile image
Michael Solati Author

You're right, it's been a while since I've had to do time complexity, I'll update it.

Collapse
cullylarson profile image
Cully Larson • Edited

I had to double-check myself that n log(n) is higher order than n :)

Collapse
jochemstoel profile image
Jochem Stoel

You can do it with less code, the parenthesis can be omitted here. :P

const duplicateCheck = a => new Set(a).size !== a.length;
Collapse
elmuerte profile image
Michiel Hendriks

If you are going to assume a is an array, then you could even use !=.

Collapse
michaelsolati profile image
Michael Solati Author

Haha, I thought so too. And I guess we could use let instead of const since it's one letter less.

Thread Thread
jonrandy profile image
Jon Randy
const duplicateCheck = a => a.length - new Set(a).size;

Shorter and more useful since it returns the number of duplicates

Thread Thread
elmuerte profile image
Michiel Hendriks • Edited
const duplicateCount = a => a.length - new Set(a).size;

And now with a meaningful name. Because, what does duplicateCheck mean, that is has, or does not have duplicates. For the boolean version hasDuplicates would be the better name.

Collapse
jpantunes profile image
JP Antunes

I really like one-liners, reminds me of how fun it was working with Perl way back when :-)

Here's one that I came up with a couple of days ago:
How to convert RGB values to a capitalised hex string? Mind you that valid decimal values for RGB are 0 - 255. Any values that fall out of that range must be rounded to the closest valid value.

const rgb = (r, g, b) => Buffer.from(new Uint8ClampedArray([r, g, b])).toString('hex').toUpperCase()
Collapse
easrng profile image
easrng

Golfed, but less checking:

const rgb = (...a) => Buffer.from(new Uint8ClampedArray(a)).toString('hex').toUpperCase()
Collapse
jpantunes profile image
JP Antunes • Edited

Nice one! Here's a list I made a few months back: dev.to/jpantunes/js-warmup-exercis...

On a second look, your version only shaves off 2 characters and introduces a possible bug imho because you don't control how many parameters are passed to the function, so calling it either less or more than 3 values it will output a wrong value, right?

Collapse
leob profile image
leob

I love the "FP" (Functional Programming) style enhancements that have been added to Javascript and various other programming languages ... whenever I see a chance to replace an old-fashioned loop with a more concise map-filter-reduce construct I'm not hesitating to do so.

Collapse
steelwolf180 profile image
Max Ong Zong Bao • Edited

Great stuff, I might ask the interviewer "what is the reason for it?", "May i know In what area for this piece of code will be used?" to buy yourself time to think and help to understand the question better instead of just doing what you are told?

Collapse
michaelsolati profile image
Michael Solati Author

It's always important to try to extract as much info about the problem you're solving for. I agree with that.

Collapse
codingsafari profile image
Nico Braun

Clickbait title, you show the solution in the header image and make it look like this should be shortened.

Collapse
michaelsolati profile image
Michael Solati Author

Haha, true. Honestly coming up with titles is hard 😅. Buuut that's the solution to the question, which I guess requires you to click and read the article to see...