Add high-level approach and in-detail solutions to all existing problems (#12)
Hi friends,
For the last week, I have been thinking about ways that I could:
- present the solution for a problem better so that it is easier to understand and internalize key concepts behind each one
- explain the solution better so that it is more straightforward to implement the idea in code
- make the solution more recallable so that it sticks in our brain longer, especially when one is having interview soon
To satisfy (1) and (3), with every problem, I have added a new section called “Approach” that summarizes the solution’s approach in 1–2 sentences. These hints should be clear and concise so that it is easy for one to understand and remember the solutions when one first read them and when one review them in the future. For (2), I have added more details to the existing explanations as well as presented them in ways that they are more aligned with the actual implementations. One could look into these and be able to translate them into code without much effort.
Here is an example of a newly updated problem:
Problem:
Given a string, check if its permutation is a palindrome.
Example:
Input: “ivicc”
Output: true
Input: “civic”
Output: true
Approach:
- To determine if a permutation is a palindrome, need to check if each character in the string appears an even number of times, allowing for only one character to appear an odd time, that is the middle one.
- Could use a hashmap store the characters and their number of occurrences.
Solution:
- As we iterate through the string, use a hashmap to add a character if we haven’t seen it and remove it if it’s already there.
- After the iteration, if we’re left with less or equal than a character in the map, we have a palindrome.
Cost:
- O(n) time, O(1) space.
- The space complexity is O(n) due to the hashmap, but since there are only a constant number of characters in Unicode, we could treat it as O(1).
That said, all updated problems are listed in the GitHub link here →
Hope you find them useful. If you have any feedback on things that you like or do not like, things that can be improved, simply reply to this email and let me know.
Best,
Hoanh
