Frontend School

Generate Valid Tweet Topic Sequences

DSA
medium

Generate Valid Tweet Topic Sequences

Medium
Recursion
Backtracking
Graph
DFS

Overview

Twitter's content organization often involves grouping related tweets into coherent "threads" or "moments." Imagine a system designed to help users or automated tools understand and generate structured content. This problem focuses on generating all possible valid sequences of topics for a multi-tweet thread, given a set of predefined rules for how topics can transition from one tweet to the next. This helps ensure thematic consistency and discoverability within longer discussions.

What you need to do / Task

Implement a function generateValidTopicSequences that, given a set of allowed topic transitions, a starting topic for the thread, and a desired total length for the topic sequence, returns all possible valid topic sequences.

A topic sequence is considered valid if:

  1. It starts with the startTopic.
  2. Its total length is exactly maxLength.
  3. Every consecutive pair of topics (T_i, T_{i+1}) in the sequence is an allowed transition as specified in the transitions input.

Input & output

generateValidTopicSequences(transitions: string[][], startTopic: string, maxLength: number): string[][]

  • transitions: An array of string[] pairs, where each inner [topicA, topicB] array indicates that a tweet with topicA can be directly followed by a tweet with topicB.
  • startTopic: A string representing the initial topic of the thread. All generated sequences must begin with this topic.
  • maxLength: A number indicating the exact desired length of each valid topic sequence.

Returns: An array of string[], where each inner string[] represents a unique valid topic sequence. The order of sequences in the output array does not matter.

Clarifications

  • There might be no valid sequences for a given input; in that case, return an empty array [].
  • A topic can transition to itself if explicitly defined in transitions (e.g., ["Sports", "Sports"]).
  • The same topic can appear multiple times within a sequence.

Examples

1

Example 1

Input:

transitions = [["Sports", "News"], ["News", "Tech"], ["News", "Politics"], ["Tech", "Sports"]], startTopic = "Sports", maxLength = 3

Output:

[["Sports","News","Tech"],["Sports","News","Politics"]]

Note:

From 'Sports', only 'News' is possible. From 'News', both 'Tech' and 'Politics' are possible, leading to two valid sequences of length 3.

2

Example 2

Input:

transitions = [["A", "B"], ["B", "C"], ["C", "A"]], startTopic = "A", maxLength = 2

Output:

[["A","B"]]

Note:

From 'A', only 'B' is possible. The sequence 'A', 'B' has length 2, which matches maxLength.

3

Example 3

Input:

transitions = [["X", "Y"], ["Y", "Z"]], startTopic = "X", maxLength = 3

Output:

[]

Note:

From 'X', only 'Y' is possible. From 'Y', only 'Z' is possible. The sequence 'X', 'Y', 'Z' has length 3. This is the only path, but the output order doesn't matter for the array of sequences.

Constraints

Constraints & assumptions

  • transitions will contain between 1 and 50 pairs.
  • Each topic string will have a length between 1 and 20 characters, consisting of alphanumeric characters.
  • startTopic will always be one of the topics present in the transitions list.
  • maxLength will be between 1 and 10.
  • The total number of unique topics will not exceed 20.
  • Memory usage should be efficient, avoiding excessive redundant storage.

Out of scope

  • Handling invalid startTopic (it's guaranteed to be valid).
  • Optimizing for extremely large maxLength values where the number of sequences would be astronomically high (the current maxLength constraint keeps this manageable for the given time budget).
  • Error handling for malformed input transitions.

What interviewers evaluate

  • Algorithmic Approach: Ability to identify and apply a suitable recursive (backtracking/DFS) algorithm.
  • Data Structures: Effective choice of data structures to represent topic transitions and manage sequence state.
  • Correctness: The solution correctly generates all valid sequences and no invalid ones, adhering to all constraints.
  • Code Quality: Clean, readable, and well-structured code with appropriate variable naming.

Loading editor...