I really like this comment a lot because it mirrors my experience with brute force type solutions to problems. It's pretty much what I always start with because on my first pass I need to prove that the problem can be solved in the first place. Then that gives me a baseline where I feel comfortable making changes and trying to optimize. Like you said, very often because of business constraints the optimization only needs to go so far and so an "optimal solution" may not necessarily be the one that is fastest in benchmarks. It may be the one I can get out today that solves the business problem now.
+1 for test case generator, some of our libraries even have a dividing path between optimized vs brute force modes just so we can be certain of correctness in unit test and what not. Correctness first with all the testing infrastructure and TODOs to at a later time go in and lay better algorithms down/execute general refactoring.
- Brute force is often simple to understand. That directly translates into maintainable code.
- The business constraints on the input size may make the brute force an acceptable solution.
- If you need a better optimized algorithm, brute force is a great place to start. It's basically your test case generator for verifying that your more complex algorithm is right.
After they get brute force code written, the coding part is over and the rest of the interview is about discussing why it's brute force and what we could do about it. But no more coding is expected. It's a chance to be creative. If they want to talk about improving the algorithm that's fine, let's draw some diagrams. They want to throw more hardware at it? Sure, let's talk about how to scale that. Maybe they've actually seen a business problem before that was similar? Great, let's discuss how you solved it.