Learn Python Coding on Telegram: “# Greedy. Add profit `prices[i]

# Greedy. Add profit `prices[i] - prices[i-1]` whenever it's positive.

• Coin Change 2: Number of combinations that make up an amount.

# Unbounded knapsack DP. `dp[i]` is the number of ways to make amount `i`.

• Minimum Path Sum: Find the min path sum from top-left to bottom-right in a grid.

# 2D DP. `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`.

• House Robber II: Houses are in a circle.

# Run the standard House Robber algorithm twice: once excluding the first house, once excluding the last.

• Palindromic Substrings: Count how many substrings are palindromic.

# Expand from center for every possible center (2n-1 centers).

• Longest Palindromic Subsequence:

# 2D DP. `dp[i][j]` = length of LPS in `s[i:j+1]`.

• Target Sum: Find ways to assign + or - to numbers to reach a target.

# DP or backtracking with memoization.

• Letter Combinations of a Phone Number:

# Classic backtracking problem.

• Knight's Shortest Path on a Chessboard:

# Use Breadth-First Search (BFS).

• Generate All Subsequences of a String:

# Backtracking: at each character, either include it or don't.

• Interleaving String:

# 2D DP. `dp[i][j]` is true if `s1[:i]` and `s2[:j]` can form `s3[:i+j]`.

• Paint House:

# Simple 1D DP. Track the min cost to paint the current house each of the three colors.

VI. Sorting, Searching & Heaps

• K Closest Points to Origin:

# Use a max-heap of size k or `heapq.nsmallest`.

• Find Kth Largest Element in a Stream:

# Maintain a min-heap of size k.

• Median of Two Sorted Arrays:

# Binary search on the smaller array to find the correct partition.

• Find Median from Data Stream:

# Use two heaps: a max-heap for the lower half and a min-heap for the upper half.

• Time Based Key-Value Store:

# Store values in a list sorted by timestamp for each key. Use binary search (`bisect_right`) for lookups.

• Reorganize String: Rearrange so no two adjacent characters are the same.

# Greedy approach with a max-heap or by counting character frequencies.

• Wiggle Sort II: Reorder so nums[0] < nums[1] > nums[2] < ....

# Find the median, then use a three-way partition and clever index mapping.

• Pancake Sorting:

# Find the max, flip it to the front, then flip it to its correct sorted position. Repeat.

• Custom Sort String:

# Use a hash map to count chars in the string, then build the result based on the custom order.

VII. Design Questions

• Design a Logger Rate Limiter:

# Use a hash map to store the last printed timestamp for each message.

• Design Tic-Tac-Toe:

# Store counts for rows, columns, and diagonals to check for a win in O(1).

• Design an In-Memory File System:

# Use a Trie-like structure where each node is a directory/file.

• Design a Hit Counter:

# Use a queue or deque to store timestamps of hits within the last 5 minutes.

• Design TinyURL:

# Map a long URL to a unique hash or incrementing ID, then convert to a base-62 string.

• Design a Web Crawler:

# Use BFS to explore links and a set to keep track of visited URLs.

• Design Twitter's Data Structures:

# Hash maps for users, tweets. A list/deque for a user's own tweets. A more complex structure for the news feed.

• Design Search Autocomplete System:

# Use a Trie (Prefix Tree) where nodes store search frequency.

VIII. Bit Manipulation & Math

• Power of Two: