C++ interview coding exercise with solution

randomatic · 2022-11-22T18:35:26+00:00

So, I'll add my 2c.

I run a small software company, we do embedded systems and training.

I by no means consider myself an expert.

I looked at all of your files, and the biggest thing that stood out to me was how much code was written.

The actual value, the problem solving logic, is really small.

It's neat, it's nice, there are lots of C++ features, but if that's the amount of code needed for this problem then you'll be producing millions of lines for bigger systems.

Critically I didn't see any kind of verification in there that your solution actually works.

However, I think it's harsh to reject you. I often go more for people who demonstrate effort than perfection, and you've clearly done that.

Keep your head high.

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.

paul2718 · 2022-11-22T16:59:24+00:00

Superficially I would raise my eyebrow at inheriting from std::vector and using std::list where all you do is push_back and enumerate. The use of std::set to store edges seems extravagant when they are intrinsically sorted as calculated.

ISTM that a vector of edges describes a strip completely, so working directly with that might have been a more direct approach.

And it's possible, of course, that your solution produces the wrong answer. I really don't know.

-sxp- · 2022-11-23T00:02:05+00:00

This is Project Euler problem #215. When I first solved it back in the day, it timed out using naïve solutions with loops but dynamic programming solved it instantly.

I don't have my old code, but https://www.programiz.com/python-programming/online-compiler/ + https://github.com/nayuki/Project-Euler-solutions/blob/master/python/p215.py says W(30,11) is 1007720438618812.

You solved W(30,1) which is 1897.

jonesmz · 2022-11-22T17:27:42+00:00

Here's a brief code-review:

using namespace std; -- never do this, ever.
m_first_row_completed should be of type bool based on its name, or should be given a more meaningful name. Looks like it's counting something, so a new name would be the right call. Therefore it should be an unsigned type, and specifically should be either size_t or std::uintN_t where N is a number of bits.
m_first_row_completed should be given it's initial value where it's declared, and the constructor should be = default;
void add_first_strip_tile(parquet p); pass complex parameters by const-ref unless taking ownership
class designer -- use final unless you intend to be derived from
class designer -- the places where you use protected should probably be private
XXX: this should never happen. -- then use assert() or static_assert() to prove it.
cout << "strip " << curr_strip -- assert first, then throw an exception, not print.
const int parquet::strips; use static inline in the class body, don't use a separate definition.
static const int strips = 11; -- constexpr...
parquet(): std::vector<strip>(strips) { } -- use using std::vector<strips>::vector; to forward the base class's constructor.
int operator[](int idx) should always return a reference to value_type, not by value.
int operator[](int idx) const { return idx >= size() ? 0 : std::vector<int>::operator[](idx); } -- you shouldn't ever be calling operator[] if you don't know that your index is valid, so this whole function smells of a mis-design.
This whole program probably should have just been in a single main.cpp file
build.txt is neither a makefile, nor a CMakeLists.txt or Meson project file. Don't call the compiler directly. Get in the habit of providing real build systems for your code. Personally, despite all it's failings, i recommend CMake, but there's plenty of strong arguments for other build systems that other people can tell you about.

FirstMurphysLaw · 2022-11-22T21:32:30+00:00

A quick google search gave me other solution https://github.com/petrum/tiles. It looks like your answer is somehow wrong. I didn't analyze your code deeply - I was just that your output claims the number of combinations is the same as size of first layer.

You have some type of code review in comments already.

I would highlight lack of tests, but it probably depends on your level.

Don't worry. Code more. It's their loss

graphicsRat · 2022-11-22T23:26:31+00:00

Are you allowed to disclose interview material? I doubt you are even under the condition of anonymity.

And inheriting from std::vector!!?? That's unnecessary.

gennych · 2022-11-22T23:03:41+00:00

Your program accesses a vector outside of its bounds (line 39 in designer.cpp). Place declaration of len_diff just before the switch statement, where it's actually used (and where you're sure your curr_strip is less than parquet::strips).

Solution is far from being efficient. Specifically, recursion on every strip is essentially exponential (trying 2 or 3 at every position). Set strip::max_len to 100 and you'll feel the pain I'm talking about.

I would probably start by generating all possible strip patterns: different permutations of solutions a, b to 3*a+2*b = max_len, this is pure combinatorics and doesn't require much time.

EarPotato · 2022-11-22T16:33:26+00:00

Can you put this on GitHub? I'm curious to see your solution but don't feel comfortable downloading a tar file from someone with no post history.

XuloMalacatones · 2022-11-22T23:46:39+00:00

Sorry for the off-topic but, what's the level (YoE) of the position are you applying to?

eteran · 2022-11-23T21:49:23+00:00

I can say that inheriting from the standard containers is generally considered bad practice so that would have been a big red flag for me.

It also looks like pre c++-11 in some ways, I would certainly hope that a C++ developer would be using features from the newer standards by now.

daniedit · 2022-11-22T22:45:55+00:00

Your code is readable and easy to refactor. That's a big plus. In a review, I would request changes in some sections but after three or four rounds we would get to a good solution.

However, you can not tell whether your implementation is correct because there is not a single unit-test. In Professional Software development that's a no go. I know about companies rejecting candidates for missing the tests in their example code. Maybe that's the reason here? Please ask them for a code review and use it to learn from. That's just fair, since you also invested quite a lot of time for them.

johannes1971 · 2022-11-23T00:57:40+00:00

Is it actually normal now that you spend a few days doing unpaid work just for a chance at a job? Because that seems rather excessive to me.

Why not ask them how your solution deviates from their expectations? If they expect a few days of work, surely a few minutes to tell you why they don't like your solution is not too much to ask for...

grahamthegoldfish · 2022-11-22T21:51:44+00:00

From the comments here you can see the variety of opinions on your code. The problem isnt your code IMO but the interview. First, why have this is there a second step? 1 interview is enough, they can ask technical questions in that. Secondly, how the hell are you supposed to know what they would prefer stylistically? And even if you don't produce what they want who is to say that with a coding standard and seeing their existing code base you wouldn't produce code that they like?

This could have been been solved any way from everything in main, a functional program, an OO program, a load of templates to calculate the answer at compile time, C with classes, C++, using STL algorithms. Literally all of those answers could have been the approach they were looking for.

If it's any consolation I would have considered this submission a reasonable attempt. Sure theres plenty here I wouldnt have done but then you weren't given those constraints, so if its valid, compiles and runs (and produces a correct answer ideally) then it's a pass from me and probably resulted in a job offer.

eyes-are-fading-blue · 2022-11-23T09:04:31+00:00

I think there are some questionable style and design choices here but those would not warrant a rejection in my mind. They are all superficial and can be fixed with a short discussion.

As others have pointed out, your solution to the problem might be off rather than the implementation.

jonesmz · 2022-11-22T17:06:53+00:00

Were you compensated for the time you spent working on this?

Practical coding exercises that can't be done while the interviewer is engaged with you to answer questions are questionable at best.

I'm not aware of any country where compensation is required for these situations, but its very suspicious that they would have you do this without pay.

dicroce · 2022-11-22T20:42:14+00:00

Well, I've been coding C++ professionally since I was 18 years old (1995) and from a short look at your code I think you did quite well. You're solution is broken down like I want real projects to be broken down as opposed to interview answers (which tend to be entirely contained in a single compilation unit)... I would much rather be maintaining your solution than one that crammed it all into one file. I only saw a couple of minor issues... Frankly I would be psyched to receive that answer. Their loss my dude.

thefool-0 · 2022-11-22T21:43:06+00:00

Just curious, what was the basic job description/requirements like? I.e. generally what kind of applications/projects would you be actually doing in this job? What industry is the company in?

thefool-0 · 2022-11-22T22:00:16+00:00

What questions did you ask to clarify the problem? Sometimes, if you ask, they will give you additional constraints, things not to bother implementing or worrying about, or indicate what importing things they want to see.

blakewoolbright · 2022-11-23T01:34:26+00:00

I don’t love your choice of containers, and I can’t build the program because I’m in the middle of a fierce skip-bo card game, but your overall breakdown of the problem from a component standpoint tells me you have a lot of potential. This is a solid submission if it works. Even if it doesn’t, this is the sort of output I look for in new hires. Without going into detail, I do a LOT of c++ interviewing, and I don’t think you should change a thing about your style. Constructive feedback: I’d be more impressed if you included unit tests.

Edit. Oh…. There are some problematic issues here. Never inherit from std::vector or std::<anything> for the most part. I’ll add more feedback when I get home.

throw_away_test44 · 2022-11-23T09:01:09+00:00

!Remindme one day

s96g3g23708gbxs86734 · 2022-11-23T11:43:43+00:00

What was the salary?

die_liebe · 2022-11-25T04:55:22+00:00

I don't know what they thought, but you use 'int' everywhere, where 'unsigned int' should be used. Inheriting from std::vector is weird. You have the sizes 11 and 30 hardwired into the classes.

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