As part of the efforts to prepare for coding interviews, I practiced some problems in Python/C++ on leetcode as well as other CP websites like codeforces. I list some of the interesting and/or challenging problems as follows.
- codeforces 1312F attack on red kingdom [Solution]: this problem touches upon the topic of combinatorial games. Refer to the article on codeforces or a Youtube video
-
codeforces 1324F maximum white subtree[Solution]: dp on tree with a special technique called rerooting
-
Leetcode 730. Count Different Palindromic Subsequences[Solution]: dp on the interval of a string
- codeforces 1328E tree queries[Solution]: application of lca. Learn a useful technique for lca, i.e., binary lifting, which is efficient for multiple lca queries.
- Leetcode 1574 Shortest Subarray to be Removed to Make Array Sorted[Solution]: interesting two pointer problem
- Leetcode 1004 Max Consecutive Ones III[Solution]: two pointer problem
-
Leetcode 1585 Check If String Is Transformable With Substring Sort Operations[Solution]: use the bubble sort idea
-
codeforces 1187D Subarray Sorting[Solution]: use BIT to query/update the left boundary of each element
- Leetcode 1606. Find Servers That Handled Most Number of Requests[Solution]: use ordered set to maintain the list of free servers and use priority queue to maintain the list of busy servers
- Leetcode 1611. Minimum One Bit Operations to Make Integers Zero[Solution]: find patterns of recursion. Another solution is to realize that this to find the order of the number in the gray code sequence
- Leetcode 297. Serialize and Deserialize Binary Tree[Solution]: besides bfs, pre-order traversal can also be used to serialize/deserialize binary tree in a recursive fashion. Be sure to know both approaches.
- 382. Linked List Random Node[Solution]: reservior sampling