July 16, 2025 - Job requirements

🎯 Daily Goals

• Review Anki Deck
• Lumosity training
• Mailmind developing

📝 What I learned:

Leetcode Problem:

3612. Process String with Special Operations I

Topics: Simulation, String Manipulation

📝 Thinking Process

This questions is pretty straightforward. You can just iterate through the input string and construct the return result on the go. The main problem is to optimize the string manipulation operation such as reverse, pop, append and replication.

👨‍💻 Big O analysis

Assume all operations are replication. Then there would be n operations. Then we denote the largest length of the string as 1 + 2 + 4 + ... + 2ⁿ = O(2ⁿ). For each operation. The worst case time complexity is linear time. Thus we have O(n*2ⁿ) Time Complexity: O(n * 2ⁿ) Space Complexity: O(n)

🛫 Implementation takeaways:

My initial implemention used deque and implemented reverse operation as a boolean flag. Based on the flag status, we can decide which side to add, drop and replicate. However, the replication is not working as expected. Since I was using deque.extendleft(reversed(deque)) It reports the error: deque mutated during iteration. The problem is that reversed() would generate an iterator of the list which the extendleft works on. During iteration the underlying deque is also mutated. In comparison deque.extend(deque) can work. In hindsight, this can totally be avoided since the result of deque.extendleft(reversed(deque)) is the same as deque.extend(deque). Still it is a quite interesting behavior. Also, I have learned that since slicing is optimized. It is actually quicker to just reverse the whole thing using slicing than using the boolean flag to mark the reverse state.

3610. Minimum Number of Primes to Sum to Target

Topics: DP, Math，Sieve of Erathosthenes

📝 Thinking Process

The prompt asks for the minimum number of primes that sums towards a target sum. Besides the primes part this is similar to a very classic dp problem: Coin change. Basically, after you have created the array of all primes that smaller the target amount. The question turned into coin change. The main idea of coin change is to think in terms of optimal solution when we are looking at a subset of coins. We create a dp array where dp[i] represents the optimal solution given the current set of coins. When there is a new coin added into the coins set. For i that is strictly smaller than the coin denomination k, dp[0] to dp[k-1] is already an optimal solution considering the new subset of coins. For i belongs to k to n-1 we only think of whether dp[i] would be updated given the new coin set. i.e. if dp[i - coin] + 1 would be smaller than the original dp[i]. As suggested earlier, dp[i - coin] would always represent the minimum coin needed for sum i - coin for the new coin set. So after we incorporating all of the coin types into consideration, dp[target] would represent the answer.

However, this question tested another concept: Sieve of Erathosthenes which is an algorithm that generates primes in linear time. The main idea is as following: Each composite number would be a multiple of some prime numbers that is strictly smaller than it. If we know all of the prime number that is smaller than a particular number and it is not a multiple of any of them. Then this number is definitely a prime number. Here is the key: we don't check all prime numbers that is smaller than the current candidate. Instead, we rule out the multiples of a prime number once we find one. Thus, each number would only gets checked once -- linear time complexity.

👨‍💻 Big O analysis

Assume the target sum is n and we have m primes.

• Time Complexity: O(n * m)
• Space Complexity: O(n)

Since we use a dp array of size n and iterate the whole array for each prime.

🛫 Implementation takeaways:

• Understand Sieve of Erathothenes
• Know how to solve coin change problem both bottom up and top down

🚀 Resources that Requires Further Study:

• Kilo Code