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
Given a non-empty array of positive integers, determine if the array can be divided into two subsets so that the sum of both subsets is equal.

**Constraints:** 
* $1 \leq$ `nums.length` $\leq 200$
* $1 \leq$ `nums[i]` $\leq 100$

# Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

## Naive approach
We can solve this problem with the following two steps:

1) First, we calculate the sum of the array. If the sum of the array is odd, there can’t be two subsets with an equal sum, so we return FALSE.
2) If the sum is even, we calculate $sum/2$ and find a subset of the array with a sum equal to $sum/2$.

The naive approach is to solve the second step using recursion. In this approach, we calculate the result repeatedly every time. For example, consider an array, `[1, 6, 20, 7, 8]`, which can be partitioned into `[1, 20]` and `[6, 7, 8]` with the sum `21`. While computing the sum, we encounter `21` twice: once in the first subset (`6 + 7 = 13, 13 + 8 = 21`)  and once in the second subset (`1 + 20 = 21`). However, since we're not storing these sums, it is computed twice.

The time complexity of this approach is $O(2^n)$. In the worst case, for each element in an array, this solution tests two possibilities, i.e., whether to include or exclude it. We can avoid the repeated work done in the naive approach by storing the result calculated at each step. We store all the values in a lookup table.


## Optimized approach using dynamic programming

We use the bottom-up approach of dynamic programming, also known as the **tabulation technique**. In this approach, the smallest problem is solved, the result is saved, and larger subproblems are computed based on the evaluated results. The problem is divided into subproblems, which are dependent on each other. We start by initializing a lookup table and setting up the values of the base cases. For every subsequent, larger subproblem, we fetch the results of the required preceding smaller subproblems and use them to get the solution to the current subproblem.


Here is how we implement this algorithm:

1) First, we calculate the sum of the array, `nums`. If the sum of the array is odd, there can’t be two subsets with an equal sum, so we return FALSE.

2) Create a lookup table, `dp`, of size $(((s/2)+1) \times (n+1))$, where $s$ is the sum, and $n$ is the size of the array. The `dp[0][0]` represents that the sum is $0$, and none of the elements is included in the sum. Therefore, $(s/2+1)$ rows and $(n+1)$ columns are needed. Initialize all cells of `dp` with FALSE.

3) Since each element in the array is a positive number, therefore the sum of elements can't be $0$. Hence, each element of the first row in `dp` is set to TRUE to represent the solution of the smallest sub-problem.

4) The FALSE in the first column except $[0][0]$ location indicates that an empty array has no subset whose sum is greater than $0$.

5) Fill the table in a bottom-up approach where `[i][j]` represents the current row and column entry.

    - If the `j`$^{th}$ element of the array is greater than `i`, it will make the sum greater than `i`, which means we cannot include this element in our subset. Therefore, we copy the previous column's value, which is `dp[i][j-1]`, into `dp[i][j]`.

    - If the `j`$^{th}$ element of the array is less than or equal to `i`, we have two choices: either include it in our subset or exclude it. Here, we want to find out if it is possible to form a subset with a sum of `i` using the first `j` elements of the array.

      - In the first choice, we need to find a subset that adds up to `i - nums[j-1]` using the first `j-1` elements of the `nums` array. That means we are looking at the value of `dp[i - nums[j - 1]][j - 1]`.

      - In the second choice, we exclude the `j`$^{th}$ element from our subset and find a subset that adds up to `i` using the first `j-1` elements of the nums array. This means we are looking at the value of `dp[i][j - 1]`.

      - Finally, we set `dp[i][j]` to the logical OR of these two choices: `dp[i][j] = dp[i - nums[j - 1]][j - 1] OR dp[i][j - 1]`.

6) Return the value present at the last row and last column of the `dp`, which denotes whether the array can be partitioned or not.
   - If we get TRUE, then the array can be partitioned.
   - If we get FALSE, then the array can not be partitioned.

Here’s the demonstration of the steps above:

Let's solve the Partition Equal Subset Sum problem using the Dynamic Programming pattern.

Solution: Partition Equal Subset Sum

Statement