Solve Topological Sort and Anagram Indices
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
1) Given a directed graph (n vertices, m edges), return a topological ordering if one exists. If the graph contains a cycle, detect it and explain how your approach identifies the cycle. Implement and compare both Kahn’s algorithm (BFS with in-degree) and a DFS-based approach; analyze time and space complexity, and discuss how to handle multiple valid orderings.
2) Given a lowercase string text and a lowercase string pattern, return all starting indices of substrings in text that are permutations of pattern. Achieve O(n) time using a fixed-size sliding window with character counts; handle repeated characters and edge cases (empty pattern, pattern longer than text).
Quick Answer: This question evaluates algorithmic problem-solving and implementation skills across graph algorithms (topological sort and cycle detection) and string algorithms (anagram substring search) in the Coding & Algorithms domain.