Validate near-palindrome and course prerequisite feasibility

Q: 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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Validate near-palindrome and course prerequisite feasibility

Overview

Coding round (40 minutes): two problems

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

Problem 2: Can all courses be completed?

Comments (0)