After brief intro, the interviewer went straight in to the coding question. I was given the link to google doc for writing code (remeber, no compiler or IDE).

1. Warm-up question
   Given a binary tree, print a sequence of node values. Condition: you can print any leaf and then remove it from the tree.

			   8
			/     \
		   4       6
		 /   \     /  \
	    3     5   7   9
	  

My solution: Make a hashmap (key=level, value=list(int)), traverse trees DFS style. After traverse, print all values in hashmap, sorted by their key.
We discussed time complexity, and discussed if sorting is really required (no, it's not).
[3,5,7,9,4,6,8]

2. Follow-up
   Condition: you must print the node, in the order of the time it became a leaf.

			   8
			/     \
		   4       6
		 /   \     /  \
	    3     5   7   9
	  

This is a very loose condition with several correct answers.
1 possible order can be [3,5,4,7,9,6,8]. you can remove 3,5 (or 5,3) but as soon as 4 becomes a leaf, you must remove it. You can start from 7,9 (or 9,7) as well.

Solution: Simple DFS would achieve the condition, no need for a hashmap in this case.

3. Follow-up #2
   Given a sequence and root as input, verify if its correct sequence (acc. to Q1).
   [4,3,5,7,9,6,8], [3,5,4,8,7,9,6] is incorrect.
   There are many correct permutations.

I had only 10 mins left, when we started with this segment. We discussed the approaches (I suggested finding a pivot element in the sequence, based on root, and divide and conquer). But the interviewer gave me hint after 4 mins in a different direction(think about hashmap and pre-processing). Also, think about O(N) time.
I'll post the solution in comments.

I was uncertain about my performance, since I didn't come up with optimal approach for real question (follow-up #2), let alone coding it. But I got onsite.

Interview Tips:

1. Ask clarifying questions, I asked question if node values can be duplicates (just when I got warm-up question). It doesn't matter for warm-up and follow-up #1, but it does matter for follow-up #2. Interviewer was impressed by this and said this will be crucial in later follow-ups.
2. Communicate clearly what you're thinking before coding.
3. After coding, test your code against 1-2 inputs. This was a plus point in my favor, I did it for 2 questions.
4. Optimize in iterations. I didn't need sorting in warm-up Q, and removed it when we discussed about it.

Good luck!