How do I fix slow and messy implementation even when I know the approach?

Completely normal, and it happens to most people preparing for technical interviews. Understanding a solution someone explains to you and independently constructing a solution are two different skills. The first one develops from watching and reading. The second one only develops from actually attempting problems without guidance. Most people spend too much time on the first and not enough on the second, which is why the gap shows up.

At least 20 to 30 minutes of genuine effort, not 5 minutes of staring and then giving up. The struggle phase is not wasted time, it's the actual learning. Your brain is building problem-solving pathways during that struggle even when it doesn't feel like progress. That said, there's a difference between productive struggle and spinning in circles. If you've genuinely tried multiple approaches and you're completely stuck after 30 to 45 minutes, looking at a hint or the approach is reasonable. Just don't look at the full solution immediately.

Because solving a problem immediately after learning a technique is not a real test. Your brain knows what tool to apply because you just studied it. The actual skill you need in an interview is recognizing the right approach from a cold start, with no context clues about which chapter it's from. This is why mixing problem types in practice and revisiting old problems after a gap of a few days is so important. That time delay removes the hint and forces your brain to work harder.