Problem

/**
 * Returns the first repeated item from an array if any
 */
export function repeatedItem<T>(array: T[]) {

}

Solution

export type RepeatedItemResult<T> =
  | { type: 'found', item: T }
  | { type: 'not-found' };

/**
 * Returns the first repeated item from an array if any
 */
export function repeatedItem<T>(array: T[]): RepeatedItemResult<T> {
  const set = new Set<T>();
  for (const item of array) {
    if (set.has(item)) return { type: 'found', item };
    else set.add(item);
  }
  return { type: 'not-found' };
}

Transcript

00:00

Today's coding interview question is something that is quite easy to solve naively and the efficient solution also serves as a nice introduction to a really used built-in JavaScript data structure. So let's go now. The problem that we have to solve today is to find the repeated item within a given input array. However, before we look at an actual solution to this problem, let's discuss what we are going to return if we don't find a repeated item. One solution is to throw an error in case no duplicates are found.

00:32

Now this is not ideal because exceptions should be for exceptional cases. You don't want your functions throwing errors just because you didn't find something. When you write code like this, it normally results in the colors of your functions having to write some additional code just to make sure that you're not going to throw an error on them. Traditionally, an alternative approach is to return a special value like now. However, this is not ideal either. For example, the item that you actually find that is repeated might be no. In such a scenario, no can mean two things.

01:05

It can mean not found, or it can mean I found two nels. Fortunately, the solution is pretty simple. We come up with this return type, which has a member that can signify the nature of the return object. If the value of the type member in the return object points to the string found, it means that we have found a duplicate item and the item is going to be contained in the item property. Otherwise, the type member of the return object will have the string not found. With that out of the way, we can write a needs scaffold for the problem that we are trying to solve.

01:38

We want to find the repeated item within an array of items of type T, and we will return the repeated item result of type T. Now, in case we don't find anything, we will return this object containing the type member pointing to the string not found. Now to start off for a solution, we are going to use a naive approach because after all, some solution is better than no solution. We go through the items in the array and for each item we start another loop at I plus one and search all the way till the end of the array to see if that item appears again,

02:12

anywhere further on within the array. If at any point the JTH item turns out to be equal to the ITH item, we return an object with the type saying found and the item member containing the ITH item. Now, the runtime for this particular algorithm to find the repeated item is going to be O of N square because we are going to be looping through the input array twice first for I and then for J. Now, the better implementation is going to loop through the input array only once, and we are going to use a data structure that is especially designed for checking object uniqueness.

02:47

And if you guessed it gurus to you, we are going to use the set data structure. We simply look through the input array once, and if we already have seen that item before, because the set Has that item and congratulations, we have found a duplicate and we are going to return type found with the item added. Otherwise, we are going to add this item to the set and continue the loop. And if that item ever appears again within the array set out has will be true and we would have found a duplicate. According interview questions go. This one is pretty easy to solve if you are familiar

03:21

with the set data structure that is built in within JavaScript. This is something that separates a beginning developer from someone who's prepared for algorithm coding interview questions, for example, by watching videos like this.

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

Coding Interview Lessons

Find the Repeated Item

Subscription Required

Problem

Solution

Transcript

Coding Interview