How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Verify and modify inorder subsequence | Airbnb Coding Question

Quick Overview

This question evaluates algorithm design and data-structure manipulation in the Coding & Algorithms domain, focusing on binary tree inorder traversal, subsequence detection, and computing the minimum edit operations under strict time and space constraints.

Verify and modify inorder subsequence

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Given a binary tree and a sequence of numbers, design an algorithm to check in O(n) time and O( 1) extra space whether the sequence is a subsequence of the tree’s inorder traversal. How would you modify the tree so that its inorder traversal contains the given sequence as a subsequence? What is the minimum number of operations (changing an existing node’s value or inserting a new node counts as 1) required to achieve this modification?

Quick Answer: This question evaluates algorithm design and data-structure manipulation in the Coding & Algorithms domain, focusing on binary tree inorder traversal, subsequence detection, and computing the minimum edit operations under strict time and space constraints.

Part 1: Verify an Inorder Subsequence with Morris Traversal

You are given a binary tree serialized in level-order form, where None represents a missing child, and a list of integers called sequence. Return True if sequence is a subsequence of the tree's inorder traversal, otherwise return False. The intended algorithmic idea is to scan the inorder traversal in O(n) time while using O(1) auxiliary traversal space via Morris traversal.

Constraints

0 <= number of serialized entries in tree <= 100000
0 <= len(sequence) <= 100000
If tree is non-empty, tree[0] is not None
Node values and sequence values are integers in the range [-10^9, 10^9]
Duplicate values are allowed

Examples

Input: ([2, 1, 3], [1, 3])

Expected Output: True

Explanation: The inorder traversal is [1, 2, 3], and [1, 3] appears in order.

Input: ([2, 1, 3], [3, 1])

Expected Output: False

Explanation: The values exist, but not in inorder subsequence order.

Input: ([], [])

Expected Output: True

Explanation: The empty sequence is a subsequence of the empty traversal.

Input: ([], [1])

Expected Output: False

Explanation: A non-empty sequence cannot be a subsequence of an empty traversal.

Input: ([4, 2, 6, 1, 3, 5, 7], [1, 3, 7])

Expected Output: True

Explanation: The inorder traversal is [1, 2, 3, 4, 5, 6, 7], so [1, 3, 7] is a subsequence.

Hints

You only need one pointer into sequence while scanning the inorder traversal.
Morris traversal visits nodes in inorder without a recursion stack by temporarily threading predecessor pointers.

Part 2: Modify the Tree by Appending the Unmatched Inorder Suffix

You are given a binary tree serialized in level-order form and a target sequence. Construct a modified tree using this exact deterministic rule: first, scan the original tree's inorder traversal and greedily match the longest prefix of sequence; second, keep all original node values unchanged; third, if any suffix of sequence remains unmatched, attach new nodes containing that suffix as a right-child chain to the current inorder-last node. If the tree is empty, create a right-child chain from the entire sequence. Return the modified tree in level-order form, trimming trailing None values.

Constraints

0 <= number of serialized entries in tree <= 10000
0 <= len(sequence) <= 10000
If tree is non-empty, tree[0] is not None
Values are integers in the range [-10^9, 10^9]
Duplicate values are allowed

Examples

Input: ([2, 1, 3], [1, 4])

Expected Output: [2, 1, 3, None, None, None, 4]

Explanation: The original inorder is [1, 2, 3], which matches prefix [1]. The remaining value 4 is appended at the end as a new right child of the inorder-last node.

Input: ([2, 1, 3], [1, 2])

Expected Output: [2, 1, 3]

Explanation: The sequence is already a subsequence of the original inorder traversal, so no nodes are added.

Input: ([], [5, 6])

Expected Output: [5, None, 6]

Explanation: An empty tree becomes a right-skewed chain 5 -> 6.

Input: ([7], [])

Expected Output: [7]

Explanation: An empty target sequence needs no modification.

Input: ([], [])

Expected Output: []

Explanation: Both the tree and sequence are empty, so the result is an empty tree.

Hints

Greedily match as much of the sequence as possible during an inorder traversal of the original tree.
Adding a right-child chain to the inorder-last node appends values at the very end of the inorder traversal.

Part 3: Minimum Operations to Force an Inorder Subsequence

You are given a binary tree serialized in level-order form and a target sequence. In one operation, you may either change the value of an existing node or insert a new node anywhere in the tree. Extra values in the inorder traversal are allowed. Compute the minimum number of operations needed so that the modified tree's inorder traversal contains sequence as a subsequence.

Constraints

0 <= number of serialized entries in tree <= 2000
0 <= len(sequence) <= 2000
If tree is non-empty, tree[0] is not None
Values are integers in the range [-10^9, 10^9]
Duplicate values are allowed

Examples

Input: ([2, 1, 3], [1, 3])

Expected Output: 0

Explanation: The inorder traversal is already [1, 2, 3], so the target sequence already appears.

Input: ([2, 1, 3], [1, 4, 3])

Expected Output: 1

Explanation: Keep 1 and 3, then either change the middle node to 4 or insert 4 once.

Input: ([1], [2, 3])

Expected Output: 2

Explanation: There are no exact inorder matches with the target, so two target values must be created using two operations.

Input: ([], [])

Expected Output: 0

Explanation: No changes are required.

Input: ([1, None, 2], [2, 1])

Expected Output: 1

Explanation: The original inorder is [1, 2]. One insertion can make [2, 1] appear as a subsequence.

Hints

A target value costs 0 only if you can keep some existing inorder node with the same value in the correct relative order.
So the problem becomes: maximize how many target values are already matched in order, then pay 1 for every remaining target value.

Quick Overview