A couple days ago, I took a C++ programming test as part of a company's hiring process. In the interest of not violating the secrecy I agreed to, I'm going to be vague about the exact nature of the test and the company.
The task was fairly simple: Implement an operation on a generic data-structure they use frequently.
There were four constraints the solution had to meet:
- Type specifications - strict adherence to the information given about the types we're working with
- Correctness - All given inputs produce correct outputs
- Canonicity - Don't use more private data than you need to to maintain the data-structure
- Runtime - Don't use more than one O(log N) operation
They're checked in order, so if you fail one of them, you don't get feedback about the rest.
My first attempt succeeded on type spec and correctness, but failed on canonicity. My second attempt failed on the type spec because of fixes I had made to fix my canonicity issue. A third attempt was not available.
I learned a few things from this, and I wanted to write it out both for myself and whoever applies for a programming job next. This was a C++ test, but these lessons should be more broadly applicable.
On my first attempt, I didn't pay enough attention to the canonicity constraint. My solution was simple and produced the correct output with only a few lines of code. I didn't take the time to reason about how multiple operations might violate canonicity, or how even an operation that wouldn't have any effect on the output would pollute the backing data structure.
Take the time. Write another function to introspect on your backing data structure and make sure it's not storing unneeded data. Go even further and write an automated check for it.
Let's go back to the type specifications. We're given two type variables,
K only supports copying, assigning, and less-than comparing.
V only supports copying, assigning, and equality checking.
In testing, the smart thing would be to create basic wrapper types that support only those operations. That way, if you accidentally use an unsupported operation, you get a glaring warning from the compiler before you submit.
This is what tripped me up on my second attempt. I tried checking that a value of type
V was inequal to another with
!= is not a supported operation on type
V. The type I was using for
V while testing was a
char, which does support
!=, so the compiler didn't catch it.
Remember these. Don't make my mistakes. Be thorough. I lost this opportunity, and the soonest they'll take another application from me is a couple of years from now.