This -> https://leetcode.com/problems/maximal-rectangle/solution/ is a example of a hazzer interview. Could be mistaken, but I think I found that this is the most common hard Dynamic Programming problem at Google interviews.

The idea that anyone should be able to solve a problem like this in 45 minutes as a demonstration of their skill as a software engineer is just ludicrous. If you can solve this problem it means you have studied this or similar problems. All it means is that you have the luxury of study. This has almost nothing to do with being a software engineer.