Do you need optimal yet non intuitive solution for Meta interview?

I highly recommend going through my DSA course which covers this topic and the FAANG hiring bar in general in-depth: Master The Data Structures And Algorithms Interview

In general, you should always strive for the optimal solution in terms of run-time unless the interviewer tells you not to. In most cases, this is 65%+ of the battle.

However, there are several branching scenarios from just getting the optimal solution in terms of run-time, one of which is super common at Meta:

1. You are pushed for an alternate solution - Meta does this all the time. All 3 people I shadowed for interviewing training at Meta did this. The interviewers on my own panel back when I interviewed to get into Meta also did this. If a question is of lower difficulty (e.g. LeetCode easy on phone screen or LeetCode medium on onsite), there is a good chance the interviewer is expecting an alternate solution with an in-depth explanation in order to pass you. That's what I did.
2. You aren't allowed to get stuff "for free" - In your min heap example, it is trivial to write that solution if you can use a built-in heap. If the interviewer feels like you got the solution too fast with a poor explanation, they might make you explain the heap in-depth or even have you code up the heap. One of the primary goals of the interviewer (especially at Meta and FAANG in general) is to make sure the candidate didn't merely memorize the problems and that they actually understand the underlying concepts. When I saw this as a Meta interviewer, I would make sure to push the candidates much harder. You don't get much signal when the engineer is just recanting memorized knowledge.

In my experience, there's a reasonable solution that you're expected to code within the interview. For some questions, there may be some advanced data structure that allows you to do things more efficiently, but it's unreasonable to expect that most interviewees have seen that pattern before.

As a candidate, one way to get part of the way there is to present and implement the 'good-enough' solution. But spend 5 min at the end talking about your intuition for something better. The awareness of something better gives you points. Something like:

Red-black trees have a self-balancing property which might be useful if applied here, due to X. If I had more time, I'd explore how that might fit in here.

We have a 10 hour crash course on Data Structures & Algorithms by Alvin: Crash Course: Beginner Data Structures And Algorithms Concepts

This course focuses on mastery -- if you have mastery, you're much more likely to arrive at the optimal solution.