One interviewer posed a question quite vaguely. He asked about algorithms and their time complexity for an array list that is partially sorted.

I asked for clarification, "Do you mean there are several subarrays which are sorted, but the overall array is not?" He confirmed.

So, I offered an answer of O(log k), where k is the number of subarrays, as a typical case of merge sort.

However, what he actually meant was that he was expecting bubble sort, and his question was about individual elements not being in the correct order, rather than partially sorted subarrays. I finally understood this when we moved to his larger coding question instead of a screening task.

I was a little disappointed that he did not have the patience to discuss and clarify better. He seemed very hurried during the interview, spoke rapidly, and couldn't wait to leave the room. I recall he even forgot to shake hands before departing, which confused me.

What is the total number of different valid parentheses? I mean, not to code it out, but to calculate the number.