DEV Community: mixao

Change Your Mindset About Algorithms with These Simple Coding Problems

mixao — Tue, 17 Sep 2024 18:42:42 +0000

A common misconception is that practicing algorithms means memorizing many algorithms. This leads to ineffective practice, frustration, rejection of algorithms, etc. To rekindle your love for algorithms, here are a few simple coding problems that do not require much algorithmic knowledge, but reflect an important aspect often overlooked in algorithms.

Each problem comes with a link for you to submit your code and view the results. You should try solving them on your own before reading the solutions; if you don't get hands-on experience, you won't learn anything. Or, you might think they are too easy but end up making mistakes. 🤭

The solutions are written in Python. If you’re not familiar with Python, that’s fine; the main goal is to understand the ideas so you can implement them yourself. Alternatively, you can ask ChatGPT to convert the code into a language you're familiar with.

Leetcode 1688: Count of Matches in Tournament

Problem

Link: https://leetcode.com/problems/count-of-matches-in-tournament/description/

You are given an integer n, the number of teams in a tournament that has strange rules:

If the current number of teams is even, each team gets paired with another team. A total of n / 2 matches are played, and n / 2 teams advance to the next round.
If the current number of teams is odd, one team randomly advances in the tournament, and the rest gets paired. A total of (n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams advance to the next round.

Return the number of matches played in the tournament until a winner is decided.

Example 1:

Input: n = 7
Output: 6
Explanation: Details of the tournament:
- 1st Round: Teams = 7, Matches = 3, and 4 teams advance.
- 2nd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 3rd Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 3 + 2 + 1 = 6.

Example 2:

Input: n = 14
Output: 13
Explanation: Details of the tournament:
- 1st Round: Teams = 14, Matches = 7, and 7 teams advance.
- 2nd Round: Teams = 7, Matches = 3, and 4 teams advance.
- 3rd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 4th Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 7 + 3 + 2 + 1 = 13.

Constraints:

1 <= n <= 200

Solution

If you already know basic programming, this problem is quite simple, right? Each match involves 2 teams, so the number of matches each round is n / 2. If the number of teams is odd, add 1 team to the next round. After each round, the number of teams is reduced approximately by half. Continue until only 1 team remains.

class Solution:
    def numberOfMatches(self, n: int) -> int:
        matches = 0
        while n > 1:
            if n % 2 == 0:
                matches += n // 2
                n = n // 2
            else:
                matches += (n - 1) // 2
                n = ((n - 1) // 2) + 1

        return matches

However, if this problem was asked before you learned programming, you might have had a different answer.

There are n teams in total, and they compete until only 1 team remains.

So there are n - 1 teams eliminated.

Each match eliminates 1 team.

So, there are n - 1 matches. Duh! 🤷‍♀️

The result is simply:

class Solution:
    def numberOfMatches(self, n: int) -> int:
        return n - 1

Leetcode 1332: Remove Palindromic Subsequences

Problem

Link: https://leetcode.com/problems/remove-palindromic-subsequences/description/

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous. In other words, a subsequence of a string is a sequence of elements taken from the string while preserving their order. For example, consider the string "abcd":

"acd" is a subsequence.
"bd" is a subsequence.
"ba" is not a subsequence.

A string is called palindrome if is one that reads the same backward as well as forward. For example, abbcbba is palindromic, while abcabc is not.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". Remove palindromic subsequence "baab" then "b".

Constraints:

1 <= s.length <= 1000
s[i] is either 'a' or 'b'.

Solution

If s is palindromic, then it can be removed in one step.

If not, in each step, you can choose a subsequence consisting of all the same characters, which should be palindromic because it consists of identical characters.

For example, s = "aabbbabab":

Remove the palindromic subsequence "bbbbb".
Remove the palindromic subsequence "aaaa".

At most, it will take 2 steps.

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        return 1 if s == s[::-1] else 2

Leetcode 1460: Make Two Arrays Equal by Reversing Subarrays

Problem

Link: https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays/description/.

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.

Return true if you can make arr equal to target or false otherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1. Reverse subarray [2,4], arr becomes [4,2,1,3]
2. Reverse subarray [1,3], arr becomes [4,2,3,1]
3. Reverse subarray [2,3], arr becomes [4,3,2,1]
4. Reverse subarray [4,3,2,1], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr does not have value 9 and it can never be converted to target.

Constraints:

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

Solution

Notice that with the subarray reversal operation, we can move an element to any position we want. For example, to move arr[5] to arr[2], we reverse the subarray from 2 to 5. The other elements in the subarray will also change positions, but the elements outside the subarray are unaffected.

Taking advantage of this, we will transform each element of arr, from left to right, to match the corresponding element in target.

For each position i, we find the element equal to target[i] in arr from i to n - 1. If no such element is found, then it is impossible to transform arr into target because we cannot add new elements. If found, let the position of that element be j, we reverse the subarray from i to j. Now arr[i] is equal to target[i]. Continue this process until the end of arr.

Example: target = [1,2,3,4], arr = [2,4,1,3]

Thus, as long as we can find j for each position i, arr will gradually be transformed into target, from left to right. Therefore, the order of the elements does not matter, as long as arr and target contain the same elements, with the same quantities, arr can always be transformed into target.

In fact, you can come up with other algorithms to rearrange the elements. The important thing here is that you can always transform arr to arrange it in any desired order.

So to determine if arr can be transformed into target, just compare if arr and target have the same elements. Same here means that the quantity of each value must also be the same, for example, if target has 4 elements with value 3 and arr has 5 elements with value 3, then obviously it cannot be transformed because we cannot add or remove elements.

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return Counter(arr) == Counter(target)

If you are not familiar with Counter/Dict/Map, you can sort target and arr and then compare:

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return sorted(arr) == sorted(target)

Leetcode 1700: Number of Students Unable to Eat Lunch

Problem

Link: https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/description/.

The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:

If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
Otherwise, they will leave it and go to the queue's end.

This continues until none of the queue students want to take the top sandwich and are thus unable to eat.

You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the i-th sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j-th student in the initial queue (j = 0 is the front of the queue).

Return the number of students that are unable to eat.

Example 1:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0
Explanation:
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.

Example 2:

Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3

Constraints:

1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i] is 0 or 1.
students[i] is 0 or 1.

Solution

A naive algorithm is to simulate the process step by step:

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        while len(students) > 0 and sandwiches[0] in students:
            front = students.pop(0)
            if front == sandwiches[0]:
                sandwiches.pop(0)
            else:
                students.append(front)
        return len(students)

However, continuously removing elements from the front of an array is very inefficient. Each time an element is removed from the front, the positions of all remaining elements must be updated. Thus, you have to traverse the students list many, many times. If you know a bit about data structures, you might realize that you can replace the array with a queue to make the removal operation less costly.

But you can do even better.

Notice that for each sandwich on top, you will keep pushing the student at the front of the queue to the end of the queue until a student who wants that sandwich is at the front of the queue.

You only care whether there are any students left in the queue who want that sandwich. If not, the process ends. If there are, one student who wants that sandwich will eat it. Specifically which student... doesn't matter.

Thus, we don't even need to keep track of the list of students in the queue. We only need to know how many students want sandwich 0 and how many want sandwich 1.

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        # count_students[i] is the number of students who want sandwich type i
        count_students = [0, 0] 
        for i in students:
            count_students[i] += 1

        not_eat = len(students)
        for i in sandwiches:
            if count_students[i] > 0:
                count_students[i] -= 1
                not_eat -= 1
            else:
                break
        return not_eat

So you only need to traverse the students list once and the sandwiches list once. Much more efficient than the previous solution.

Leetcode 2073: Time Needed to Buy Tickets

Problem

Link: https://leetcode.com/problems/time-needed-to-buy-tickets/description/.

There are n people in a line queuing to buy tickets, where the 0-th person is at the front of the line and the n - 1-th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the i-th person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person at position k (0-indexed) to finish buying tickets.

Example 1:

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

Example 2:

Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
- In the next 4 passes, only the person in position 0 is buying tickets.
The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

Constraints:

n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n

Solution

A naive algorithm is to simulate the entire ticket-buying process step by step until person k finishes buying their tickets. You can use a queue/deque data structure for the ticket-buying line to make adding and removing elements more efficient.

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        t = 0
        q = deque()
        for i in range(len(tickets)):
            q.append(i)
        while tickets[k] > 0:
            front = q.popleft()
            tickets[front] -= 1
            t += 1
            if tickets[front] > 0:
                q.append(front)
        return t

However, with this algorithm, you have to simulate the entire ticket-buying process step by step until it is complete. Let's try to find a more efficient way.

Each ticket purchase takes 1 second, so the elapsed time is equivalent to the total number of tickets everyone has bought. Let's try to calculate how many tickets everyone has bought.

Suppose we have a queue of 5 people: ["Alice", "Bob", "Carol", "Dave", "Eve"]. They need to buy the corresponding number of tickets: [3, 10, 9, 13, 5].

Think carefully, when Carol buys her 9th ticket, how many tickets has each other person bought? Think about it and then read on.

The answer is:

Alice bought 3 and left.
Bob bought 9.
Dave bought 8.
Eve bought 5 and left.

In the initial order, the person in front can buy tickets faster than the person behind by 1 ticket, but never more than 1 ticket, because after buying, they have to go to the end of the line and wait for others to buy another ticket.

When a person buys their x-th ticket, all the people before them in the initial order have also bought x tickets, or have finished buying if they needed fewer than x tickets.

The people behind them in the initial order have also bought x - 1 tickets, or have finished buying if they needed fewer.

When person k has just finished buying all their tickets, we can also deduce how many tickets each other person has bought, thus knowing the total number of tickets bought and the elapsed time.

Code:

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        t = 0
        for i in range(len(tickets)):
            if i <= k:
                t += min(tickets[i], tickets[k])
            else:
                t += min(tickets[i], tickets[k] - 1)
        return t

With this approach, you only traverse the number of tickets each person buys exactly once. Even if there are millions of people, each needing to buy millions of tickets, the program's runtime will still be less than 1 second.

Leetcode 1894: Find the Student that Will Replace the Chalk

Problem

Link: https://leetcode.com/problems/find-the-student-that-will-replace-the-chalk/description/

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the student number 0 again.

You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When the student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then the student number i will be asked to replace the chalk.

Return the index of the student that will replace the chalk pieces.

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.

Constraints:

chalk.length == n
1 <= n <= 10^5
1 <= chalk[i] <= 10^5
1 <= k <= 10^9

Solution

A naive algorithm: Simulate the process of each student solving problems.

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        i = 0
        while True:
            if k < chalk[i]:
                return i

            k -= chalk[i]

            if i + 1 < len(chalk):
                i = i + 1
            else:
                i = 0

No good, right? Time Limit Exceeded.

The problem with the naive algorithm is that when k is large, the process can take a very long time over many rounds (1 round is when it goes back to the first student's turn). The program has to traverse the chalk array many times. For example, when k = 1000_000_000, chalk = [1, 1, 1, 1, 1, 1...] (100_000 ones), the algorithm will traverse chalk 10_000 times, and chalk has 100_000 elements.

But pay attention to k after each round.

After 1 round, there are 1000_000_000 - 100_000 pieces left.
After 2 rounds, there are 1000_000_000 - 100_000 - 100_000 pieces left.
After 3 rounds, there are 1000_000_000 - 100_000 - 100_000 - 100_000 pieces left.
And so on...

After each round, the number of chalk pieces decreases by a fixed amount, which is the total amount of chalk the students use in one round.

Do you have to iterate through each round and subtract the chalk pieces bit by bit? You can calculate the number of rounds directly, right?

cycles = int(k / sum(chalk))

And you can also calculate the remaining chalk pieces after cycles rounds:

k = k - cycles * sum(chalk)

Or just use the modulo operation:

k = k % sum(chalk)

Now the remaining pieces are not enough for one round, so you only need to go through the list one more time to run out of chalk.

Code:

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        k = k % sum(chalk)
        for i in range(len(chalk)):
            if k < chalk[i]:
                return i

            k -= chalk[i]

This algorithm only needs to traverse the chalk array twice, once to calculate the total chalk for each round and once more to subtract the chalk until it runs out.

Leetcode 1509: Minimum Difference Between Largest and Smallest Value in Three Moves

Problem

Link: https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/description/

You are given an integer array nums.

In one move, you can choose one element of nums and change it to any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

(In other words, you can perform at most 3 moves to change the difference between the largest and smallest values in nums, return the smallest difference that can be achieved).

Example 1:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
- In the first move, change 2 to 3. nums becomes [5,3,3,4].
- In the second move, change 4 to 3. nums becomes [5,3,3,3].
- In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

Example 2:

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: We can make at most 3 moves.
- In the first move, change 5 to 0. nums becomes [1,0,0,10,14].
- In the second move, change 10 to 0. nums becomes [1,0,0,0,14].
- In the third move, change 14 to 1. nums becomes [1,0,0,0,1].
After performing 3 moves, the difference between the minimum and maximum is 1 - 0 = 1.

It can be shown that there is no way to make the difference 0 in 3 moves.

Example 3:

Input: nums = [3,100,20]
Output: 0
Explanation: We can make at most 3 moves.
- In the first move, change 100 to 7. nums becomes [3,7,20].
- In the second move, change 20 to 7. nums becomes [3,7,7].
- In the third move, change 3 to 7. nums becomes [7,7,7].
After performing 3 moves, the difference between the minimum and maximum is 7 - 7 = 0.

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Solution

Of course, you should not change an element in a way that decreases the minimum or increases the maximum of the array because it will increase the difference.

Changing an element that is neither the minimum nor the maximum also does not help. For example, nums = [1, 5, 0, 10, 14], changing 10 to 11 still results in a difference of 13.

You should change the elements that are the maximum or minimum, and change them to a value within the new minimum and maximum range. Specifically, the exact value does not matter because we only care about the difference between the minimum and maximum.

In general, you only need to change the smallest, second smallest, third smallest, largest, second largest, and third largest elements. Now we have just a few cases that need to be checked:

Change the 3 smallest elements.
Change the 2 smallest elements and 1 largest element.
Change 1 smallest element and 2 largest elements.
Change the 3 largest elements.

Additionally, for arrays with 4 or fewer elements, you can change all elements to be equal to achieve a difference of 0.

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0

        nums = sorted(nums)

        return min(
            nums[-1] - nums[3], # Change the 3 smallest elements so nums[3] becomes the smallest
            nums[-2] - nums[2], # Change 1 largest element so nums[-2] becomes the largest
            nums[-3] - nums[1],
            nums[-4] - nums[0]
        )

The array is sorted to easily access the smallest, second smallest, largest, second largest, etc.

In fact, you only need to focus on a few smallest and largest elements, so you do not need to sort the entire array. The algorithm can be further optimized. You can use a heap/priority queue to quickly find the largest and smallest elements (if you are a beginner, you can skip this part, the above method is sufficient for this problem).

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0

        smallest = heapq.nsmallest(4, nums)
        largest = heapq.nlargest(4, nums)

        return min(
            largest[0] - smallest[3],
            largest[1] - smallest[2],
            largest[2] - smallest[1],
            largest[3] - smallest[0]
        )

Conclusion

Have the questions above changed your mindset about algorithms?

As you’ve seen, the problems discussed don’t require advanced knowledge of algorithms or data structures. Even someone well-versed in algorithms might struggle with these problems. There are countless problems, and it’s impossible to know every algorithm for every situation. The important thing is to develop skills in observation, thinking, reasoning, etc., to come up with algorithms to solve new problems.

However, I'm not saying you don't need to learn more algorithms. Common algorithms can help solve parts of problems. Sorting algorithms, for instance, are frequently used and often come pre-written, but other algorithms might not be as readily available. Sometimes, you’ll need to combine algorithms to tackle a problem or tweak an algorithm to fit a specific situation. It’s also important to understand the principles and ideas behind algorithms rather than just memorizing them. Personally, I don’t memorize algorithms, but I understand them so I can rewrite them. This way, you can tweak, learn the thinking, techniques, and tricks to apply in other cases. And who knows, understanding algorithms might even lead you to improve or invent better algorithms.

I hope this article helps you better understand algorithms, improve your programming skills, and inspires you to practice and develop your algorithmic abilities.

Implement JavaScript Promise from scratch

mixao — Fri, 22 Mar 2024 18:41:31 +0000

Today, I tried implementing Promises/A+ from scratch to test my coding skill. In the process, I’ve crafted this guide to share my insights and experiences with those who share a similar interest. Without further ado, let’s dive in.

We'll name our Promise implementation NotNow. Other catchy names like will, future, later, etc. have already been claimed by other packages.

Let's start simple.

const PENDING = "pending";
const FULFILLED = "fulfilled";

class NotNow {
  #state = PENDING;
  #onFulfilleds = [];
  #value;

  constructor(fn) {
    fn(this.#fulfill.bind(this));
  }

  #fulfill(value) {
    this.#state = FULFILLED;
    this.#value = value;
    this.#onFulfilleds.forEach((fn) => fn(value));
  }

  then(onFulfilled) {
    this.#addOnFulfilled(onFulfilled);
  }

  #addOnFulfilled(onFulfilled) {
    if (this.#state === PENDING) {
      this.#onFulfilleds.push(onFulfilled);
    } else if (this.#state === FULFILLED) {
      onFulfilled(this.#value);
    }
  }
}

The constructor executes the function you pass, using the #fulfill method as an argument. This allows you to fulfill the promise with a value when you're ready.

The #fulfill method sets the value and triggers all the callbacks with the fulfilled value.

The then method adds a callback to be executed when the promise is fulfilled. It internally calls #addOnFulfilled.

The #addOnFulfilled method, if the promise is pending, queues the callback for later execution. If the promise is already fulfilled, it executes the callback immediately.

Let's put it to the test.

const notNow = new NotNow((fulfill) => {
  setTimeout(() => fulfill(2), 2000);
});
notNow.then((value) => console.log(`callback 1, fulfilled with ${value}`));
notNow.then((value) => console.log(`callback 2, fulfilled with ${value}`));

After 2 seconds, the console will log:

callback 1, fulfilled with 2
callback 2, fulfilled with 2

That's a good start.

In reality, the callbacks aren't executed synchronously right after the promise is fulfilled, but asynchronously. This ensures consistency; even if the promise is fulfilled synchronously, the callbacks will still be executed asynchronously. You can use setTimeout or queueMicrotask to schedule this. I'll use queueMicrotask to allow them to execute sooner.

Update the #fulfill method:

// this.#onFulfilleds.forEach((fn) => fn(value));
queueMicrotask(() => this.#onFulfilleds.forEach((fn) => fn(value)));

Update the #addOnFulfilled method:

// onFulfilled(this.#result);
queueMicrotask(() => onFulfilled(this.#value));

When we add a callback, we're actually creating a new promise. This new promise is the result of executing our callback. We can then pass this promise around to add more callbacks to process the result of our current callback.

So, in then, we create a new promise. When the promise is fulfilled, we execute the callback, then fulfill the new promise with the result of the callback.

class NotNow {
  // ...
  then(onFulfilled) {
    return new Promise((nextFulfill) => {
      this.#addOnFulfilled((value) => {
        const nextValue = onFulfilled(value);
        nextFulfill(nextValue);
      });
    });
  }
  // ...
}

Let's test this out.

const a = new NotNow((fulfill) => {
  setTimeout(() => fulfill(2), 2000);
});
const b = a.then((value) => value * 2);
b.then((value) => console.log(value));

a will be fulfilled with 2, and then b will be fulfilled with 4. So, 4 should be printed.

We can chain the then calls:

new NotNow((fulfill) => {
  setTimeout(() => fulfill(2), 2000);
})
  .then((value) => value * 2)
  .then((value) => console.log(value));

We can even chain more:

new NotNow((fulfill) => {
  setTimeout(() => fulfill(2), 2000);
})
  .then((value) => value * 2)
  .then((value) => value * 2)
  .then((value) => value * 2);
  .then((value) => console.log(value));

Ah, method chaining always looks so satisfying.

One characteristic of a promise is that when the fulfilled value is also a promise (i.e., it has a then method), the current promise will attempt to adopt its state. For instance:

const a = new Promise((fulfill) => fulfill(2));
const b = new Promise((fulfill) => fulfill(a));
b.then((value) => console.log(value));

The output will be:

Even though we fulfilled b with a, it tried to take a's fulfilled value, because a is a promise.

This behavior remains the same even if you nest more promises:

const a = new Promise((fulfill) => fulfill(2));
const b = new Promise((fulfill) => fulfill(a));
const c = new Promise((fulfill) => fulfill(b));
const d = new Promise((fulfill) => fulfill(c));
d.then((value) => console.log(value));

Output:

To achieve this, when fulfilling, if the fulfilled value is a promise, we don't fulfill immediately, but wait until that promise is fulfilled, by adding #fulfill as a callback.

class NotNow {
  //...
  #fulfill(value) {
    if (typeof value?.then === "function") {
      return value.then(this.#fulfill);
    }
    this.#state = FULFILLED;
    this.#value = value;
    queueMicrotask(() => this.#onFulfilleds.forEach((fn) => fn(value)));
  }
  //...
}

The next time #fulfill is called, it performs the same operation, so it works recursively, untill the fulfilled value is not a promise.

Let's test this:

const a = new NotNow((fulfill) => fulfill(2));
const b = new NotNow((fulfill) => fulfill(a));
const c = new NotNow((fulfill) => fulfill(b));
const d = new NotNow((fulfill) => fulfill(c));
d.then((value) => console.log(value));

Output:

Correct!

Can we use async/await with NotNow? Absolutely! The value to be awaited just needs to behave like a promise, its actual class doesn't matter.

const a = await new NotNow((fulfill) => {
  setTimeout(() => fulfill(5), 2000);
});
console.log(a);

That's the essence of it. In this tutorial, I've skipped error handling for simplicity, to make it easier to focus on the core concepts. Refer to the source code for the complete version. There are also additional methods like all, allSettled, any, race.

I hope this helps. Feel free to share your thoughts, or even your own implementation, in the comments below.