July 30, 2025 - Daily Drill¶
🎯 Daily Goals¶
- Review Anki Deck
- Lumosity training
- Leetcode
- Developing laplace
- Langchain Learning
📝 What I learned:¶
416. Partition Equal Subset Sum¶
Thinking Process¶
This is a classic dynamic programming problem. The brutal force solution requires you to iterate through all possible subsets and cacluate their sum. This takes O(2n) time. Instead we can think from another perspective: what we can form using the elements from the array. If we only look at one element k, the answer would be 0 and k. And we can then introduce another new element m, The subset sum we can form becomes 0, k, m, k + m. We can see that from this process, we can build a possible subset sum array within just O(n2) time. Then we can easily check if the sum_of_all_element // 2 exists in the array. Using bit operation we can further improve the time complexity. The idea is as follows. If a sum s can be formed using all exists elements, we create a variable bit_set and mark sth bit to 1. When a new number n is introduced, we can simply execute the operation bit_set |= bit_set << n. To check if a sum is possible we can do bit_set >> s & 1 == 1.
Complexity Analysis¶
Given that we have n elements in the array.
- Time Complexity: O(n)
- Space Complexity: O(1)
Key Takeaways¶
- Use bit operation to reduce time complexity
🚀 Resources that Requires Further Study¶
This is an interesting research on the AI coding productivity. 16 experienced open-source developer (each with 5 or more years of experience) are selected to complete a series of tasks with/without the helper of AI code editor. The productivity increase with AI coder is predicted to be around 24%. Nonetheless, the result is quite surprising. The group of developer with AI coder actually get their productivity decreased by 19%. This might be caused by the facts that AI is not quite good at handling complex codebase and prompt and context engineering are also time consuming.