I recently did an onsite with Google for an L3/L4 position.
https://leetcode.com/problems/paint-fence/
The questions I got from Google was very similar to this question. Thought I should give back to the community.