Just don't ask brain teasers when you conduct an interview; I believe they give no valid signal at all, and I also believe Microsoft does not ask them anymore. The coding questions that require an "aha!" moment are very similar to brain teasers, and should also be avoided. When I conducted interviews for FAANG, I asked somewhat simpler coding questions, something around DFS and/or topological sorting (without calling…
I remember an MS interview I failed in 2015 or thereabouts:
As part of the interview, they asked "how would you find the kth element from the end of a singly-linked list in the shortest time", and they strongly implied that size() followed by counting forward was not what they were looking for, and that they were expecting constant space.
I didn't know the answer, and failed. I don't know if I failed because of it, but anyway.
So I went home and looked up the intended solution, which is the dual iterator, advance one k times then repeatedly advance both one step. After a bit of thought I realized that the time complexity is the exact same as the naive size() + count.
With size(), you do n traversals to get the number of elements, then you do n-k to get your iterator to the desired position. With dual iterators, you advance one n times and the other n-k times. Same deal, total number of steps is 2n-k no matter what, and linked lists usually aren't sequential in memory, so there are no cache benefits favoring one over the other.
There are other advantages to dual iterator-like algorithms (e.g. if it's a stream, you cache the k last seen values and pass only once at the cost of O(k) space; or if it's paging from very slow storage, it pages less due to locality). But they didn't say anything to indicate they were doing a stream. They were, essentially, just reading a puzzle from a book and expecting a particular solution.