Algorithms Cheat Sheet

General Principles

• Default values often act like an if statement in certain cases, eg: dict.get.
• When accessing out-of-bound indices, use min and max functions to clamp values within a reasonable range.
• Directly use if instead of None check, e.g., if x: instead of if x is not None:.

Problem Solving Steps

1. Communication: The goal is to solve real-world problems collaboratively with the interviewer.
2. Clarify the Objective: Confirming what is asked is very important. For example, if the problem requires returning values instead of indices, then storing index information is meaningless.
   • Identify boundary cases.
   • Ask valuable questions.
   • Don’t rush to code; first confirm you are solving the correct problem.
3. Formulate the Problem: To solve algorithm questions, you need to build a formula that describes how to get the result. Then look at all known conditions (such as whether the data is sorted, or any useful data characteristics). This helps decide how the formula converges and whether to use loops or recursion.
4. Explain Your Approach: Before coding, explain your thought process to the interviewer and get confirmation.
5. Test Your Code: After coding, run several test cases including edge cases.
6. Optimize: Improve time and space complexity if possible.

Strings

If the string consists purely of letters, you can convert characters to ASCII codes to build a hashmap.

• For example, a-z, A-Z, 0-9 can be mapped to 0-61.
• When frequency matters, sorting can sometimes help.

Two Pointers

Sliding Window

The essence of the sliding window technique is to reuse information for judgment. The right and left pointers move one step at a time and incrementally update the condition, rather than recalculating every time.

For example, first expand the window by moving the right pointer until the condition is met, then shrink the window by moving the left pointer until the condition is no longer met, which can help find the optimal solution.

Matrices

• In-place problems
  • You can extend the value range to solve them (introducing new information without overwriting old data).
  • Use temporary variables.
  • Swap coordinates: $(x, y) = (y, x)$.
• Matrix rotation is equivalent to:
  • First transpose, then flip.
  • Or first flip, then transpose.

Hashmaps

• Use defaultdict(int) for counting frequencies.
• Check length and boundary conditions upfront, not mixed in the main logic.
• Double hashmaps can be used to create unique mappings.