Learn essential coding patterns to answer problems and prepare for tech companies' interviews.

Ace the JavaScript Coding Interview

This module teaches us the underlying patterns behind common coding interview questions. By learning these essential patterns, we'll be able to unpack and answer any problem the right way—just by assessing the problem statement. This approach was created by FAANG hiring managers to help us prepare for the typical rounds of interviews at major tech companies like Apple, Google, Meta, Microsoft, and Amazon.

By the end of this module, we'll have the skills we need to unlock even the most challenging questions, grok the coding interview, and level up our career with confidence.

Coding Interview Patterns

# Statement
We are given an unsorted array, `nums`, with $n$ elements and each element is in the range $[1, n]$ inclusive. The array originally contained all the elements from $1$ to $n$ but due to a data error, one of the numbers is duplicated, which causes another number missing. Find and return the corrupt pair (missing, duplicated).

**Constraints:**
- $2 \leq n \leq 10^3$
- $1 \leq$ `nums[i]` $\leq n$



# Solution

The given input array is unsorted, and the numbers in the input array lie in the range $1$ to $n$. Therefore, the cyclic sort is optimal to place the elements at their correct index. Once all the elements are in their correct position, we can easily find the pair of missing and duplicate numbers.

The essence of this approach is to identify missing and duplicated elements within a single pass. This approach involves iteratively swapping elements until each number is placed at its correct index. After this, it scans the array to find the element that does not match its index, indicating the presence of a duplicate. Simultaneously, this also points to the absence of the number that should have been at this index, identifying the missing number.

The steps of the above-mentioned approach are given below:

1) The first step is to place each number in its correct position during the cyclic sort. Initialize `i` to 0 and iterate over the array. While traversing, we will perform the following steps:

   * The variable `correct` is calculated as `nums[i] - 1`, representing the index where the current number should be placed if the array were sorted.
   * If the current number, `nums[i]`, is not equal to the number at the correct position, `nums[correct]`, a swap is performed using the `swap` function to move the current number to its correct position.
   * If the numbers are already in their correct positions, `i` is incremented to move to the next element.


2) The second step is to traverse the array and detect the number that is not at its correct index. This will be the duplicated number. When we add $1$ to that index, the resulting value will be our missing number.

3) Return the pair containing missing and duplicated numbers.

Let’s look at the following illustration to get a better understanding of the solution:

Let's solve the Find the Corrupt Pair problem using the Cyclic Sort pattern.

Solution: Find the Corrupt Pair

Statement