Here's one I was recently asked. Apparently, I actually did better than I thought, as I'm going to the next round. The problem is really quite simple, but there's a linear-time solution that just wasn't popping into my head.
Given a tree where each node only contains a pointer to its parent, find the first common ancestor for any two arbitrary nodes.
Part of my hang up was that I was trying to think about lots of complicated trees, when the problem actually boils down to two lists converging. The main issue is dealing with finding the point of convergence without storing extra information or doing an n^2-type loop. If the two given nodes are at different heights in the tree, you can't simply walk up the tree and expect to get a collision. Visualized:
Once you know the obvious solution, it is obvious. You need to measure the height of both nodes by walking all the way up for both of them. Then you "trim up" the longer tail so its height matches the shorter one. Then walking them up side-by-side will produce a guaranteed collision.