So I’ve been submitting my resume for techie jobs in the Austin, TX area for a while now, when I came across a listing in Dice that had TWO options to apply… the standard “Apply Now” and a “QA Challenge” that purports to put me on the top of the stack.
Well, if you know me, I’m not one that likes to be lost in the crowd with these things. I like to stand out and shine. So in my mind, the gloves were off, and challenge accepted!
I remember hearing about how Google would advertise jobs on bill boards with fun puzzles, where the solutions was a phone number to call or a website to visit to apply. This “QA Challenge” had the same feel. It made me feel like I was applying for an exclusive job, that few would muster the brain power to attempt – let alone complete.
Now, I’m not going to give away any answers ( to keep things fair for current applicants that come across this post ), but I will describe a bit about the process, the anticipation, and the hidden challenge that was bestowed upon me after the third puzzle.
The Application Notice
My first set of instructions, with a fun and welcoming disclaimer. I just have to solve THREE puzzles, and I’ll have their attention… OK, I can do this.
Puzzle One: Main Floor Challenge
OK, so it reads:
My elevator can go sideways, long ways, slant ways and any other ways you can think of. You just press any button, and, whoosh, you’re off.
So I thought about it for a while, made my selection, and…
I was congratulated with this screen to move on on complete the next two levels…
Puzzle Two: Second Floor Challenge
This one is a pretty easy one for anyone that deals in MD5 checksums on a regular basis. Just a matter of finding the file in question, and running an MD5 checksum, and submitting the result. Not a challenge really, more like a test that you you are paying attention.
Puzzle Three: Third Floor Challenge
I was pretty excited to have this solved, and be moved up the stack, I mean, how many people are going to take the time to solve this, right?
Well after some clever maneuvering, I was able to get all five switches to turn on, with the flick of a switch 😉 Yeah, mission complete, right?
Success! … sort of
Whoa! I completed the task, but I was presented with an oppotunity to give up, or move on… what the? I thought I was done.
I mean, the first screen says I’ll be moved up the stack, but now they’re saying that if I’m REALLY interested in moving to the front of the line, they have a much harder challenge for me.
They’re saying I can stop here and get there attention… really? I don’t think so…
I think they want to see
- Who’s willing to start the challenge, and
- Who’s willing to go all the way.
And if you know me, I’m an all the way kind of guy – so I pressed the button to “Continue to the Fourth Floor Puzzle”…
I mean, how hard could it be, right? The others took a few minutes each… couldn’t take much longer then that, right?
Puzzle Four: Fourth Floor Challenge
Well, the fourth puzzle is different… in fact, it requires me to pull out my pen and paper… no wait, I’m going to need to program this one… oh no, I think I’m going to need to brush up on my algorithm skills…
So how do we go about solving this?
Well, there are a variety of ways, but overall, the process is pretty straightforward. In fact, I presented it to my son, who is a junior in high school, and even without programming skills, he was able to break apart the problem into specific sub-tasks – which is always the name of the game with these types of puzzles.
The text of the fourth puzzle goes like this:
You are in the kitchen with a product manager. He mentions his cousin recently rebuilt a vending machine from the early Roman Republic. Apparently minting coins was labor intensive, so the designers tried to develop a change return mechanism that would return the fewest number of coins necessary to meet the desired change. They did this by always dispensing the largest denomination coin that was equal or less than the remaining change first, and then repeating the process on the remaining change amount.
While this works for U.S. currency, it would sometimes fail for certain amounts of Roman Currency ( i.e. return a greater number of coins than necessary ), because the denominations that the machine would use as change were 1,4,5 and 9 cents.
If you tested, the machine by requesting change in amounts of 0 to 1000 cents ( inclusively ) – in how many cases would the change machine return more coins than necessary?
And in the sidebar are a few examples of what certain coins should be delivered as change, and where the vending machine works, and an example of where it breaks.
It turns out that the vending machine uses an algorithm called a “greedy algorithm“, and is one that approximates very well, and perfectly in some cases like the American coin set, and is typically very fast. But it’s not perfect for all cases.
The way to find a perfect, or optimized solution set, involved using a dynamic programming algorithm that tested more possibilities, and looked for the lower and upper bounds of the solution set, and returning the best answer of all the solutions it’s worked out.
The dynamic programming algorithm is a bit slower, but it’s guaranteed to be the smallest set of coins returned. There is no guarantees on the types of coins returned, and there are often multiple correct answers, including the greedy algorithm solution that the vending machine uses.
So the optimal solution set is the “control set”, of which I then compared to the vending machine solution, and found the number of differences, and that is the solution.
I do believe I’ve found the right answer, but I’m not spilling the beans on the solution, so that anyone working this problem can’t just copy an answer…
So how long did it take me? Well, the better part of three days. Yup, that’s how I spend my weekends 🙂
Why so long? Well, I was brushing up on some skills, researching the problem, doing my diligence on the accuracy of the output, input, and making sure I actually understood the question fully. I actually went through about 4 different dynamic programming algorithms before I was satisfied that I was getting the correct solutions for the optimized problem sets.
So where to from here? Hurry up and wait for a phone call 😉