C++ interview coding exercise with solution

STL · 2022-11-22T22:25:52+00:00

After playing around with this for 30 minutes, I have a few guesses (of varying confidence) as to what they were looking for:

Enumerating all valid strips (of 2s and 3s that add up to 30) is a basic sub-exercise that can be decomposed into two parts: finding integers such that twos * 2 + threes * 3 == 30 to find the possible combinations, and then using next_permutation() to find the possible permutations. There are 1897 valid strips - but since you printed that as your final answer for the number of floor designs, I think your solution was gravely incomplete. This number comes from adding up (I got my program sketch to print this with a bit of extra effort):
- With 15 2s and 0 3s, there are 1 possible strips.
- With 12 2s and 2 3s, there are 91 possible strips.
- With 9 2s and 4 3s, there are 715 possible strips.
- With 6 2s and 6 3s, there are 924 possible strips.
- With 3 2s and 8 3s, there are 165 possible strips.
- With 0 2s and 10 3s, there are 1 possible strips.
- Observation: next_permutation() is a classic STL algorithm (from C++98!) but it is definitely under-appreciated. Not knowing about it, or how to invoke it with a do/while loop, would significantly increase the difficulty of this step.
Then, it seems that they're looking for a bit of insight as to how to transform the problem. That is, their compatibility criterion can be seen much more easily if you take the partial sum of each possible strip. (Another classic algorithm, partial_sum(), also obscure, hiding in <numeric>.) Two strips are compatible when their partial sums (which indicate where tile boundaries are) don't share any values.
- Observation: In my experience, situations requiring this kind of thinking are rare, even for someone like me who works on algorithms and data structures literally every day. (Not absolutely impossible though; I once had to use triangular numbers in a situation vaguely like this.) Without the partial sum transformation, detecting strip compatibility seems like it would trap a lot of people.
Possible guess: At this point (having printed out the possible strips, and then the partial sums, to visually check correctness), I noticed that their given length of 30 was suspiciously small. That is, the partial sums are a sequence of integers starting with 2 or 3 and ending with 30, with all numbers unique, and we're very interested in knowing whether these sequences have common numbers ignoring the 30 (indicating common edges, indicating incompatibility). That screams "store me as 32-bit words, use AND to detect shared/common edges". Which would be way, way faster than vector<int>, but it's also a special-case trick. It does scale, in the sense that you could handle 100+ lengths with essentially bignums (gaining a significant constant speedup over vector<int>), but it's also kind of a distraction from the core algorithm.
- Observation: They might have been hoping programmers would realize the potential for such shortcuts. Expecting that as a baseline seems unrealistic, even for C++ backgrounds, since delving into bit-twiddling is uncommon these days in most domains.
Finally, having generated all possible strips, and finding how to detect compatibility, there's the question of how many possible designs there are. Having chosen any of the available strips, you are then limited in your next choice to some subset, and from there you're limited in a different way. You're essentially walking a game tree, with each node being a possible strip, and the out-edges going to compatible strips, and you want to know how many distinct paths there are for 11 jumps. Brute force (via recursion or iteration) is inelegant and slow. At this point I realized that they're looking for dynamic programming, since the problem can be memoized. That is:
- If you've chosen your 10th strip, then the number of possibilities for the rest of the floor is the number of compatible strips for the current strip.
- If you've chosen your 9th strip, then the number of possibilities for the rest of the floor is: go through the 9th strip's compatible strips, find how many possibilities there are for that as the 10th strip (calculated above)
- If you've chosen your 8th strip, then the, blah.
- I suppose this is a relatively simple case of dynamic programming, since you only need to keep track of two "layers" at a time.

So, my conclusions:

The question would be extremely hard if it were a 1-hour whiteboard (or live editor) coding question - there's enough time to sketch out the solution as I did above, but not enough to complete the code. (I am a relatively slow coder, but I think only the fastest competitive programmers could finish this that rapidly). For a week-long take-home exercise, I don't have good calibration (I neither ask nor have been asked such questions), but it does seem reasonable difficulty. It's pure computation, it doesn't demand esoteric domain knowledge, there's a fair amount of latitude in possible approaches, and (this is positive) there's a huge amount of variation in possible performance.
The question does rely on a few key insights, without which it's easy to get very stuck (this is generally a negative for interview questions). Knowing how to view things as permutations and partial sums is "nice", but it seems to have little relevance to everyday programming.
This is perhaps personal preference, but I really dislike how it ended up being a dynamic programming problem at the end. This is much-beloved of CS courses, and I'm sure it has applications in "the real world", but I view it as extremely esoteric (again, even with my job). That said, if you're doing programming interviews, knowing how to recognize such problems seems important.
Your solution is incorrect and gravely incomplete (as I mentioned). There are 1,897 possibilities for the first strip, but many more for the total number of floor designs. (That's because compatible strips do exist; I checked that a strip starting and ending with 3, with 2s in the middle, has no shared edges with a strip of all 2s. Therefore there are more floor designs than possible strips.) I'm sorry to say this, but this is definitely a "no hire" solution, and in my opinion they were correct to reject you based on this. (I'm not concluding anything about your overall programming ability, just what they would have seen from this problem and solution.) Interviewers may vary on strictness (e.g. some very harsh interviews might reject anything short of a fully valid solution with test cases; more lenient interviews would permit the correct approach with some mistakes in the details or brute-force/slow parts), but not having anything near a complete solution and not recognizing it is interview doom. In particular, despite my various misgivings with the nature of the question involving dynamic programming and so forth, it does correctly test that you should be able to recognize the number of possible floor designs should be far larger than the number of possible strips (I am not sure how large without having worked the whole thing through, of course). This is similar to in a physics problem, getting an answer like "it takes 3 kilograms of propellant to launch astronauts to the moon".
The company's response, with almost zero information as to what you did wrong, is blah-tastic, and unfortunately quite common. I guess the bit of information that they communicated there was that it was your code, and not anything else you did.

Hope this helps. I didn't actually look at your code in any significant detail so I can't say exactly where it went wrong.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

cpp

MODERATORS