Coding Test Fundamentals

English edition note: The operation-count estimate is a rough, environment-dependent heuristic. The complexity of nested loops depends on their bounds; it cannot be inferred from nesting depth alone.

#📚 Preparing for coding tests

• Skills needed when solving algorithm problems

  1. 📖 Reading comprehension: understand the problem quickly and accurately
  2. 🔧 Background knowledge: essential data structures and algorithms
  3. 💡 Problem solving: solutions and ideas
  4. 📝 Implementation: the ability to write code
  5. ✅ Verification and debugging: find mistakes and counterexamples when a solution is wrong

• Step by step

  • Review essential data structures and algorithms
  • Develop problem-solving skills
  • Develop implementation skills

#📚 Coding test assessment criteria

• Constraints specified for each problem
  • Time limit: time complexity
  • Memory limit: space complexity

#Time Complexity

• A measure of algorithm performance

• Expressed using Big-O notation

• A rough rule of thumb

  • In C++, exceeding 100 million operations in one second is risky. Remember the rough rule: one second = 100 million operations.
  • Typically, k nested for loops = $O(N^k)$
  • (This is not an exact calculation.)

#Space Complexity

• Describes memory use as a function of N
• A common trade-off: 💾 memory (space) <-> ⏱️ time
• Usually, consider time first

Example

• Problem: time limit 2 seconds; memory limit 64MB
• Input: $0 \leq N \leq 100,000,000$
• What time and space complexities might be feasible for this problem?

#📚 Coding test fundamentals

• Variables, functions, arrays, loops, conditionals and strings are commonly used.
• Inheritance and pointers are rarely used in these notes.
• Input/output functions
• Fast input/output link: [Baekjoon 15552: Fast A+B][FastIO]

Source¹

1 Based on the lecture course “Algorithm Coding Tests: From Introduction to Passing.”
[FastIO]: https://www.acmicpc.net/problem/15552