My Interview Brain Teasers Part 4

This is the next part of my series on [[How to Handle Interviews|how I like to conduct interviews]].  

I have 2 other brain teasers I might also use when interviewing a candidate, depending on circumstances.  

The Parts Problem

I use this example as part of a troubleshooting exercise.  

Assume you work for a manufacturing company that has 27 machines that all produce the exact same product, a 1oz gold coin.  However, one of the machines is producing a coin that is only .9 ounces.  You have a stack of coins from each machine.  Using a single scale and a single weighing, how do you determine which machine is producing the faulty coins.  

You'll find variants of this on the internet but I like to again change it a little so it is less obvious to those who have seen the brainteaser and answer but don't understand the reason for the answer, and also to make it relevant.  I'm hoping the candidate again breaks down the problem and realizes that the number of machines really doesn't matter.  Assuming 2 machines, how do you determine the problem machine?  Take 1 coin from MachineA and 2 coins from MachineB.  If the weighing is 2.9 then the problem is MachineA, if it is 2.8 then the issue is MachineB.  I'll help the candidate get this far in the reasoning.  From there I would expect him to extrapolate 3, 4, and 5 machines and their weighings.  By then I would expect the algorithm to be obvious and easily calculable for 27 machines.  

The Salary Problem

This is another fun one for me.  It again tests whether the person can deal with changing requirements quickly.  I once had a candidate that had a college class in cryptography, a subject I find interesting but baffling frankly.  But, I do understand the basics such as Shared Password, Public Key encryption, etc, and I think I understand when to use each.  The candidate rattled off differences in AES from DES from 3DES.  Wow!  But did he understand heuristically how to use these things?  Let's find out, here's the problem (my boss wasn't thrilled when he was present in an interview where I used this):

Our company, similar to most others, has a policy against employees divulging their salaries to other employees.  In fact it is grounds for immediate termination.  But I think we could all agree that knowing each other's salary (or an average salary) would certainly help us to negotiate raises better.  So, how would we all determine our average salary without anyone knowing anyone else's individual salary?

Since these job candidates are technical in nature I usually get an answer like, "I'd build a webpage where everyone anonymously connected, entered their salary, which was stored encrypted in a table using 3DES.  After everyone did this an average would be calculated.  "  That's an ugly answer for so many reasons.  How can I assume the developer didn't backdoor the encryption?  I usually get a dumb look after mentioning that.  OK, then, let's change requirements, this project must be completed in the next 5 minutes.  By now the candidate realizes a coding solution is out of the question.  That's important.  Sometimes coding a solution is NOT the answer to a given problem.  

Then I usually get something like, "Everyone writes down their salary on a slip of paper and puts it in a hat.  We can average that."  OK, it's true that it meets requirements but the fact is that I can likely deduce who makes what individual salary based on seniority and intuition, so, let's assume that not only can no one know anyone else's individual salary, but no one can know *any* individual salary.  

Again, wait for 30 seconds until the dumb looks subside.

For my crypto dude I mentioned that his crypto class gave him his answer, if he thinks about it.  It's very simple one-way encryption.  One employee writes a random number (it probably should be 5 or 6 digits, or if your company is very generous, 7 digits) on a slip of paper and passes it to the next person who adds his salary and passes it to the next person who adds his salary, etc, until the paper is returned to the originator who adds his salary and finds the average of the sum and destroys the paper.  

But, I really like to see candidates that can think about solutions that don't involve technology.  As engineers we tend to like to find answers using our specialized tools.  This is often *wrong*.  Sometimes the answer is much simpler.  For instance, if you like building things (like me) you probably like to measure everything before you cut it ("measure twice cut once").  But that is wrong.  The real goal is to never measure in the first place!  For instance, if I need to replicate a 2x4's length to apply a sister to it I would *not* measure it.  I would put my new board next to it and draw a pencil line directly where the first board ends.  No measuring tool needed at all.  

When you tell the candidate to solve it without technology it is interesting to see what the answers may be.  In reality I've never had a single candidate be able to solve this problem.  I usually give a hint that I don't need an exact average, you can round it to the nearest thousand dollars.  At that point I've heard plenty of answers, my favorite being everyone puts a penny in their coffee cup for each thousand they make.  Everyone comes to the break room and on the count of 3 empties their cup into a trash bag.  Everyone counts the pennies and divides by the number of employees to get the average.