How do you react if you encounter a hard problem in an interview that you've already solved before?
And assuming you already know the optimal solution. Consider the problem maximal rectangle on leetcode, apparently frequently asked (like in Google): https://leetcode.com/problems/maximal-rectangle/description/ The best I could do on my own would be O(n^2xm^2), and that is a hard solution to come up with by itself. But there is an O(nxm) solution which uses the solution from another hard problem on leetcode (area of rectangle under histogram). If I was the interviewer and someone came up with the optimal solution for this one I would know what's up. So what would you do?
Leetcode
That happened to me recently with trapping rainwater at Microsoft. I told them I’ve seen it before but didn’t know the optimal solution. They made me solve it anyway. I also got the merge intervals problem at Facebook, told them, and they switched it to an extension of the problem instead. Overall I think it’s worth telling them. Doesn’t really hurt in anyway but not telling them might hurt.
The only way it can hurt is if you tell them. If you tell, the expectations are likely higher since you should already know how to do and explain the problem. If you don’t tell, then you can work through the problem and get the optimal solution and look good. Obviously don’t be a dunce and just write out the optimal solution without any explanation of brute-force solutions or how to go from brute-force to the optimal solution. This is how they’ll know you’ve seen the problem before and are just barfing out the answer. Ideally, since you’re probably working Leetcode, you’ve seen most or all of the common problems already.
Oh yea that’s a great point actually. I’m imagining telling them I’ve seen the problem before and then missing some edge cases or something. I could see that coming across kinda badly.
Depends. How good are your acting skills?
I guess they're ok. But I'm not sure how to pace myself. Going from observation to observation and optimizing slowly all the way from brute Force to optimal in reality might take many hours or even days. How am I supposed to make it believable in 1 hour? (Unless I get these in all the other interviews too and they actually believe I'm the next Gauss)
1. Act shocked 2. Say it seems like a challenge 3. Take a second to appear to think about solving it, but think about something else, 4. Crush it and 5. Walk out and say I’ll call then later.
Forget what I said, this is the way to go
I usually say something along the lines of "i think I've seen something similar"
What if you haven't seen a hard problem before, but can come up with the optimal solution? Are you supposed to pretend to take longer so that the interviewer doesn't think you've heard it before? That just seems ridiculous.
It wasn't a hard problem in that case, period. I'm not talking about some leetcode problems marked hard but aren't hard, but the ones that really are hard. And nearly no one would be able to come up with the optimal solution in so little time.
What if some people can though? Seems pretty silly to filter them out.
Practice like you're explaining to someone. Say here's the easy brute force way, but by doing this you can optimize it as such. If you understand the problem and not just memorize it, should be easy. No acting required. Also doesn't take forever to reach to optimal solution.
I do "know" the progression from brute Force to optimal, with the key observations to make, but the fact remains that if u can do all of that for a hard problem you probably already know the solution. And in that case you should've disclosed that in the beginning?
You're answering a question I haven't asked. I specifically talked about hard leetcode algorithmic problems not implementing a standard textbook datastructure/beginner algorithm or a behavioral question.
Interviewer reuses question, I reuse answer.
I used to say that I saw that before but recently I realized that with the ridiculous culture of leetcode questions being everywhere saying this is meaningless. You are participating in this weird mating dance so just go with it.
I’ve always told that I’ve seen it before and have always been asked to solve the question anyway
I guess if you say you've seen it you better solve it fully with the optimal solution or you're screwed (and maybe get honesty points). But if you don't disclose I think coming up with a complicated enough slightly suboptimal solution might tell them more about the thought process (perhaps better than disclose + optimal?)