cswork / libraryOpen practice workspace

Coding questions · Meta

Validate near-palindrome and course prerequisite feasibility

These problems evaluate string-processing and graph-theoretic competencies, testing algorithmic reasoning about near-palindrome validation with edge-case handling and course-prerequisite feasibility via cycle and ordering concepts, and are commonly asked to assess correctness, efficiency, and robustness under input constraints.

Coding round (40 minutes): two problems

You do not need to run code, but you should:

  • Explain your approach clearly.
  • Walk through the logic on examples.
  • Propose test cases and edge cases.

Problem 1: Near-palindrome after deleting at most one character

Given a string s containing lowercase English letters, determine whether s can become a palindrome after deleting at most one character.

  • Input: s
  • Output: true if s is already a palindrome or can be made into one by deleting at most one character; otherwise false.
  • Constraints (typical): 1 <= len(s) <= 1e5

Problem 2: Can all courses be completed?

You are given:

  • An integer n representing courses labeled 0..n-1
  • A list prerequisites, where each pair [a, b] means you must complete course b before course a.

Determine whether it is possible to finish all courses.

  • Input: n, prerequisites
  • Output: true if there exists an ordering of all courses that satisfies prerequisites; otherwise false.
  • Constraints (typical): 1 <= n <= 1e5, 0 <= len(prerequisites) <= 2e5

Near Palindrome With One Deletion

Return whether s is a palindrome after deleting at most one character.

Examples

Example 1

Input: ('aba',)
Output: True

Explanation: Already palindrome.

Example 2

Input: ('abca',)
Output: True

Explanation: Delete b or c.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.

Course Prerequisite Feasibility

Return whether all courses can be completed under prerequisite constraints.

Examples

Example 1

Input: (2, [[1,0]])
Output: True

Explanation: Acyclic prerequisites.

Example 2

Input: (2, [[1,0],[0,1]])
Output: False

Explanation: Cycle prevents completion.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.