At one job interview I was deliberately given a problem which had no efficient solution. The idea was to find a heuristic which would get close to the optimal solution and run in a reasonable time.
I got one of those at a FAANG interview. I was a bit less experienced and less confident at the time so I left the interview thinking I was misunderstanding some fundamental CS laws.
