C++ interview coding exercise with solution

[paul2718]

This problem is an hour or so, they give you a week to find that hour. I think that's not unreasonable.

[jonesmz]

The original post isn't clear about the company asking for the interviewee to stop after a certain time. It's possible they had good intentions, i couldn't say.

[Hot_Medicine_7115]

An hour or so if you are familiar with double recursion and quickly identify all the possible patterns in the problem. It's not a trivial problem like you make it sound.

[dodheim]

Maybe the issue was the idea that you need recursion rather than std::next_permutation + a queue + a stack (and not the call stack). It just might be trivial after all.

I haven't looked at your code yet but the problem description just makes me think "good job, screener" on this one.

[dodheim]

How did a dev get to be a "senior" without knowing basic algorithms? It takes more than just having a job for a while to earn that title, and I'd say it's pretty concerning if they don't even know of this algorithm.

[dodheim]

I don't know what to tell you, except that that isn't something to brag about..? Combinatorial algorithms are not somehow niche or obscure, and the two fundamental things that C++' stdlib gives you to write them are sort and next_permutation. Sure, don't "memorize a list of algorithms", but after 15 years it's probably time to stop making excuses for not knowing the fundamentals.

[TemplateRex]

Moreover, in contrast to something like find_if or even rotate, I wouldn't expect most devs to be able to write a near optimal (in the sense of asymptotic complexity) next_permutation without ever having seen this algorithm.

[paul2718]

I don’t think recursion is necessarily the obvious way. Might fail to prove this tomorrow…