Implement topological sort from string input

Q: Implement topological sort from string input

This question evaluates a candidate's skills in parsing unstructured dependency strings into directed graphs, producing a valid topological order, detecting and reporting minimal cycles, and reasoning about robustness against duplicate, unknown, or malformed inputs as well as time and space complexity.

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

You receive N lines of raw text describing task dependencies, e.g., 'install A after B', 'C->A', 'B before D'. Implement a function that: (

parses the strings into a directed graph; (
returns one valid topological order of tasks; (
detects cycles and reports a minimal cycle; (
handles duplicate/unknown tasks and malformed lines gracefully. Analyze time and space complexity. How would you adapt it for streaming input and very large graphs (e.g., external memory or batched Kahn’s algorithm)?

Implement topological sort from string input

Overview

Comments (0)