Group testing puzzle
Try to think in terms of binary search:
Start by checking half the cake. Then, if you didn't smell vanilla, you can be sure the first half does not contain vanilla, hence we don't need to check them anymore - hence we save time. This was only intuiton to why it might be possible to do better than $O(n)$, not the actual solution for it.
But something important to note is that any algorithm better than $O(n)$ must depend on $k$. Its not hard to show a lower bound of $\Omega(k)$