Construct the Lexicographically Largest Valid Sequence
What is this problem about?
The Construct the Lexicographically Largest Valid Sequence interview question asks you to build a sequence of length 2n - 1 using numbers from 1 to n. The rules are:
- The number 1 appears exactly once.
- Every number i from 2 to n appears exactly twice, and the distance between the two occurrences must be exactly i.
- You must return the lexicographically largest such sequence.
Why is this asked in interviews?
Microsoft and Google use this Construct the Lexicographically Largest Valid Sequence coding problem to test a candidate's ability to implement Backtracking with pruning. Since you need the lexicographically largest result, the order in which you try numbers matters, and you need to efficiently backtrack when a choice leads to a dead end.
Algorithmic pattern used
This follows the Array, Backtracking interview pattern.
- Create an empty array of size 2n-1.
- Start filling from index 0.
- For the current index, try placing numbers from n down to 1 (to ensure lexicographical priority).
- If placing i at index and index + i, ensure both spots are empty and within bounds.
- If a number works, move to the next empty spot and recurse. If it fails, undo the placement and try the next number.
Example explanation
For n = 3, sequence length is 2(3) - 1 = 5. Numbers are 1, 2, 2, 3, 3.
- Try 3 at index 0: [3, _, _, 3, _].
- Try 2 at index 1: [3, 2, _, 3, 2].
- Try 1 at index 2: [3, 2, 1, 3, 2].
Result: [3, 2, 1, 3, 2]. This is the largest sequence.
Common mistakes candidates make
- Incorrect distance logic: Thinking the distance means i numbers between them (which is correct) but failing the index math (index and index + i).
- Wrong loop order: Trying numbers from 1 to n instead of n to 1.
- Redundant search: Not returning immediately when the first (and therefore largest) valid sequence is found.
Interview preparation tip
In backtracking problems where you need the "first" or "largest" solution, always return a boolean from your recursive function. This allows you to "stop" all recursive calls immediately once the goal is reached.
