Airbnb Software Engineer Interview Experience — BQ Then a Tree Subsequence Coding Question

For the first round, there's a reference to check, but the post doesn't say what it points to.

The second round started with a quick self-introduction and some small talk with the interviewer, then went straight into behavioral questions. We got asked:

1. Talk about a time you taught yourself something — how did you learn it, and did it end up helping you in your actual work later on?
2. Tell me about a time you didn't meet expectations, and how you used customer feedback to improve.
3. Has anyone given you negative feedback before, and how did you handle it?

Then came the coding part:

In-order traversal of a tree: check whether a given sequence of numbers is a subsequence of the tree's in-order traversal.

My approach: solve it efficiently with two pointers. Initialize two pointers, one on the main sequence and one on the target subsequence, both starting at the beginning. Walk through the main sequence, and whenever the current element matches the current element of the subsequence, advance the subsequence pointer. If the subsequence pointer reaches the end, it's a valid subsequence. This only needs O(n) time and O(1) space, handles duplicate elements while preserving order, and you need to handle the empty-sequence and equal-length edge cases separately.

We worked through this one together pretty fast and got it accepted, then they asked two follow-ups:

1. How would you modify this tree so that it becomes a subsequence of the given sequence?
2. How would you do the modification with the minimum number of steps (overwriting an existing node's value or inserting a new node each count as one step)?