Interview Cake
← course home

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

Find a duplicate, Space Edition™ BEAST MODE

In Find a duplicate, Space Edition™, we were given an array of integers where:

  1. the integers are in the range 1..n
  2. the array has a length of n+1

These properties mean the array must have at least 1 duplicate. Our challenge was to find a duplicate number without modifying the input and optimizing for space. We used a divide and conquer approach, iteratively cutting the array in half to find a duplicate integer in time and space (sort of a modified binary search).

But we can actually do better. We can find a duplicate integer in time while keeping our space cost at .

This is a tricky one to derive (unless you have a strong background in graph theory), so we'll get you started:

Imagine each item in the array as a node in a linked list. In any linked list, each node has a value and a "next" pointer. In this case:

  • The value is the integer from the array.
  • The "next" pointer points to the value-eth node in the list (numbered starting from 1). For example, if our value was 3, the "next" node would be the third node.

Here’s a full example:

An array [2, 3, 1, 3], so 2 is in the first position and points to 3 in the second position.

Notice we're using "positions" and not "indices." For this problem, we'll use the word "position" to mean something like "index," but different: indices start at 0, while positions start at 1. More rigorously: position = index + 1.

Using this, find a duplicate integer in time while keeping our space cost at . Just like before, don't modify the input.

Drawing pictures will help a lot with this one. Grab some paper and pencil (or a whiteboard, if you have one).

We don’t need any new data structures. Your final space cost must be .

We can do this without destroying the input.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

time and space.

Our space cost is because all of our additional variables are integers, which each take constant space.

For our runtime, we iterate over the array a constant number of times, and each iteration takes time in its worst case. So we traverse the linked list more than once, but it's still a constant number of times—about 3.

There another approach using randomized algorithms that is time and space. Can you come up with that one? (Hint: You'll want to focus on the median.)

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Wanna review this one again later? Or do you feel like you got it all?

Mark as done Pin for review later

Reset editor

Powered by qualified.io

. . .