Wizards and Dwarves

dwarvesI wrote about interview puzzle questions recently to set the context for this article.

A few years back, a colleague asked me to ponder a Wizards and Dwarves puzzle as a potential interview question.  A typical statement goes something like this:

A village of wizards is nearby a village of dwarves.  Once a year, the wizards visit the dwarves, and line up the dwarves in increasing order of height, so that each dwarf can only see the dwarves smaller than himself.

The wizards have white and black hats.  They place a white or black hat on the head of each dwarf (using a strategy of their choosing, perhaps even randomly).  Then starting at the back of the line (the tallest dwarf), they ask each what color hat he is wearing. 

Each dwarf who answers incorrectly is killed by the wizards.  The other dwarves can hear his answer, but do not know whether he was killed.

What strategy minimizes the number of dwarves killed?

Ok, I thought about it.

Pondering

thinkingAmong many irritations I have for puzzle questions, the fiction is frequently distracting: 

Why villages?  Why wizards and dwarves?  Why in order of height?  What if they are all of the same height?  How can you kill a dwarf and not have his neighbor nearby hear it?

And my brain spins with other tangents:

Dwarves have high magic resistance and constitution – don’t they get a saving throw?  Toss in a few +5 battle axes and there would be a wizard slaughter!

Meh.

Wizards, Dwarves and Barometers

barometerIn the spirit of the barometer question, I formulated the following responses:

  • Non-violent non-cooperation.  It is not stated that there is a penalty for non-cooperation.  In the spirit of Gandhi, the dwarves refuse to be sorted by height, do not line up, and will not wear hats.  Wizards are known weaklings and will be unable to forcefully move the dwarves into place.
  • Scatter.  The dwarves split their village up into smaller villages, until each village consists of a single dwarf.  Each dwarf now has an equal chance of survival (this strategy, while fair, will be popular with the tall dwarves, but less so with the short ones).  The maximum number of dwarves killed will always be one.
  • UN Convention on Genocide.  The dwarves are being unfairly singled out as a group for destruction.  Citing Resolution 260 (III), they appeal to the United Nations and await protracted discussion.
  • Mini-guns.  Despite their diminutive size and desire peace, the dwarves obtain special weapons training, obtain mini-guns and when threatened, and whoop some major wizard ass.
  • Mobile Phone.  First variant – dwarf uses a mobile phone to take a picture of his hat, revealing the color.  Second variant – dwarf snaps a photo of the dwarf in front of him and texts it to him.
  • Low tech (no mobile phone required).  Dwarf turns around and asks the dwarf behind him the color of his hat.
  • Vacation.  The wizards arrive once a year.  The dwarves arrange to be out of town on that day (ideally somewhere warm and sunny).
  • Insubordination.  Each dwarf takes off his hat and reports its color.

And so on.

Conclusion

If you follow the intended script, you can find solutions in which no more than one dwarf is killed (the tallest has no knowledge of his hat color and his odds are essentially subject to chance).

But as shown above, one can simplify and further optimize the solution by exploiting ambiguities in the fiction.

And it’s a lot more entertaining.

Posted in Humor, Interviewing | 3 Comments

Puzzling

puzzleSome time ago, I had an amusing interview experience.

A young fellow interviewing me asked a reasonable set of basic technical questions, had me code a few things on the white board (also reasonable), and so on.  The interview was pretty typical, and going well.

Near the end, he looked at me slightly askance, and said

“Ok, now I’m going to ask you a puzzle question.”

I may not have successfully resisted the temptation to roll my eyes as I responded

“Mmm, Ok.”

I’m not very fond of puzzle questions.

Barometers

barometerHe proceeded to ask

“Suppose you spot a building in the distance and want to estimate its height.  How would you do that?”

I chuckled and replied “That really reminds me of The Barometer Question.”  He blanched a bit and asked “What do you mean?” 

He hadn’t ever heard of it.

I proceeded to relate the story of the professor who asks a student how to measure the height of a building “with the aid of a barometer”.  The professor’s expectation is that student will provide an answer involving differential pressure from the base to the top. 

Instead, the student provides a list of unexpected, yet technically correct answers:

  • Tie a string to the barometer and lower it from the top of the building until it touches the ground.  The length of string will be the same as the height of the building.
  • Toss the barometer off the top of the building, time how long it takes to hit the ground, and solve for height.
  • Offer the shiny new barometer to the building superintendent in trade for a peek at the blueprints.  The building height will be on the blueprints.

and so on.

“Wow, sounds like you’ve already heard of that one …”

said my dismayed interviewer.  (Indeed, though we eventually discussed the question and I provided him with a novel answer that satisfied him.)

Wizards and Monkeys

wizardAs puzzle questions go, this barometer variety isn’t too bad – at least it is amenable to multiple alternative, creative and valid solutions.

Puzzle questions which primarily involve a “gotcha” moment of perfect truth are in my mind essentially worthless for evaluating candidates.  In this category I have in mind classics such as Wizards and Dwarves, or the one on Monkeys and Switches.

These questions tend to result in a quick response if the candidate has heard them before, or a lot of fruitless struggling if they have not.  They generally don’t lend themselves well to systematic analysis nor extended discussion.

The puzzles are entertaining, for sure, but do you want to hire someone who can solve brain teasers, or do you want someone who can actually get work done?  Unless perhaps you run a company that authors brain teaser books …

In Joel Spolsky’s widely referenced article on Guerilla Interviewing, he too frowns on what he refers to as “Aha!” questions (the “gotcha” questions I refer to above), for similar reasons.

Out of the Box

boxJoel hedges somewhat more on what he calls “impossible” questions, like “How many piano tuners are there in Seattle?”  I’m a little more sympathetic here – I call those “out of the box” questions since you’re essentially looking for a candidate to approach a non-standard situation in a systematic way.

While I find those questions slightly more useful, they are less relevant for programmers than fundamental questions on algorithms, data structures, coding, design and architecture.  And in a 45-60 minute interview, I find I’m already pressed for time to cover those well.

As a result, if I’m ever interviewing you and ask you a puzzle question, it’s only because you’ve done very well.  It means I’d like to hire you, the interview is ahead of schedule, and I’m simply curious to see how you respond.

I’m secretly hoping you’ll roll your eyes, of course …

And if you ever ask me a puzzle question in an interview, I’m making a mental note to follow up (if hired) and speak to you about your interviewing techniques.

Posted in Interviewing | 3 Comments

Thrashing The Delivery Truck

Random Truck Walk

I’ve previously compared software estimation to variations in the time required to drive to work.

Dispatching delivery trucks is my mental model for comparison to changes in project direction.  This can help others to understand the impact when changes happen too frequently.

A Random Walk

Using an example from the Bay Area, suppose I have a delivery truck stationed in San Francisco.

drivingI call up the driver and ask him to make a delivery in Sacramento.  For reference, Google tells me it takes an hour and a half or so to drive from San Francisco to Sacramento.

Suppose that, 30 minutes into the trip, I call my driver and tell him to make the delivery to San Jose instead.  He’d likely be near San Pablo, only a third of the way to Sacramento. 

The driver dutifully turns around, and starts the one hour trip to San Jose.

After another half an hour, I call him up and instruct him to drive to Tracy.  From somewhere near San Leandro (and short of reaching San Jose) he would start the one hour drive to Tracy.

And so on.

What Did You Accomplish Today?

After a day of this, I recall my driver back to the home office and inquire

“How did it go?  How many deliveries did you make today?”

Exasperated, my driver informs me that, in spite of driving hundreds of miles, he failed to complete a single delivery.

(As a manager, I then express shock and outrage, and we proceed to have a conversation in which perhaps I learn the error of my ways.)

Thrashing

In computer science thrashing refers to situations in which the resources of a computer are largely (or wholly) consumed by forms of overhead, with the result of severely reduced productive output.

The concept can apply to other activities, including projects.  Changes in direction (whether literal or figurative), can happen too frequently with the result that productivity is impacted (and in the worst case, entirely eliminated).

Make sure the driver has a chance to drop off the package.

Posted in Management, Software | Leave a comment

Hidden Chronicles

Hidden ChroniclesToday Zynga launched a new game called Hidden Chronicles

Hidden Chronicles is a “hidden object” game in which you search for all the objects hidden within an illustration presented on the game screen (like the one to the right).  It also has mini-games and puzzles.

You can read more details in this VentureBeat article.

You can try Hidden Chronicles here

http://apps.facebook.com/hidden-chronicles/

Enjoy!

Posted in Zynga | 2 Comments

Ball Cookies

finished productThese round cookies are a family holiday tradition.  They are fairly easy to make, and not overly sweet.  Like potato chips, it’s hard to eat just one.

This recipe yields about 50 cookies.

Ingredients

  • ready for chilling1 cup butter, softened at room temperature
  • 1/2 cup powdered sugar (plus more later to roll the cookies in, see directions below)
  • 2 1/4 cup flour
  • 1 teaspoon vanilla
  • 3/4 cup chopped nuts (for example, small walnut pieces)

Directions

  • ready for the ovenMix butter & powdered sugar well
  • Mix in vanilla, flour and nuts
  • Chill in refrigerator for several hours
  • Shape into balls about 1 inch across (see picture to right)
  • Bake at 400 degrees for about 11 minutes
  • Roll in powdered sugar while warm.  For this I use a small baking pan filled with sugar (see picture to right)
  • rolling in sugarOnce cool, roll again in powdered sugar

Once fully cool, they are ready to eat.

Enjoy!

Posted in Cooking | Leave a comment

Technical Pecha Kucha

stop watchPecha Kucha is a fun presentation format, bound in both content and time (20 slides of 20 seconds each – about 7 minutes long). 

At NetApp we employed a similar format for “outrageous opinion” talks in engineering which I really enjoyed.  So I happily accepted a recent opportunity to perform a Pecha Kucha presentation at Zynga.

We used a slightly modified format (20 slides of 15 seconds each – 5 minutes total), but the principle is the same.  I chose to transform a longer presentation on scoping for 90% into the shortened format. 

For a technical presentation, that turned out to be a fun challenge. Here’s some things I learned from that experience.

Cadence

metronomeThe timed format means that your presentation will be chugging along regularly, even if you are not.  If you haven’t mastered the cadence of your slides, the timing of your presentation will sound awkward to your audience.

To address this, you’ll need to know your slides end to end. 

That is, you have to have the sequence of your presentation in your head, so that for each slide you know which is coming next, to ensure a smooth transition.

You should be talking about the next slide in sequence before it shows up, otherwise your audience will wait through an uncomfortable silence.

Overall this is tricky to master.  I recommend several trial runs through your slide deck, with the last run ideally performed shortly prior to your presentation.

In other words, practice.  Watching some examples will help as well.

Visual Simplicity

zenShoot for visual simplicity.  Uncomplicated pictures, graphs, smallish text snippets and callouts trump paragraphs of text.  Avoid big gobs of text and long lists of bullet items.

Swap graphs and clip art in place of text, whenever you can meaningfully replace the content.

With any presentation, strong reinforcing visuals are important.  In Pecha Kucha, they are golden.  The format is more friendly to purely visual presentations (design, art, architecture, …), and this fact needs to be leveraged for technical content as well.

5 Seconds

clockYour slides should take around 5 seconds for the average viewer to read and understand.  Any longer, and they won’t be able to listen to you, or might still be reading as you transition to the next slide.

If your presentation includes a slide with 20 bullet items and lots of text, you’ve got a problem.

Cheat: Repeat

abcIf you’ve got a key point that requires more than the allotted time to present or reinforce, simply copy / paste the slide for a second repeated time slice.

In my talk, I used a slide in order to present a more complicated topic (for 15 seconds) and then repeated the slide with animated annotations to explain key points (for another 15 seconds).

Animate, Carefully

flimAnimations can effective but require careful planning due to the compressed time format.

Powerpoint does a nice job by default of spacing the animations out over the time interval, if your presentation is on an auto timer. 

If your presentation cadence is really on the mark, the animations can appear just in time to support the points you’re discussing with the audience.

Wash, Rinse, Spin

washerTo maximize impact, I arranged my talk in iambic pentameter.

Just kidding. I divided my talk into three sections

  • Introduction, introduce the problem (5 slides)
  • Concept and reinforcing content (14 slides)
  • Conclusion (1 slide)

I limited the reinforcing content to two primary examples and one shorter example.  That was a little too complicated – if I did the talk again, I would limit to 1-2 examples. 

Limit the number of key concepts so the audience can absorb them in the short time allotted.

And good luck.

Posted in Communication, Pecha Kucha, Zynga | 3 Comments

What I Found in Panama

I feel a guilty need to read my share of books which are outside my area of expertise (I have friends who are substantially more prolific readers than I – they make me feel guilty).

Once in a while, I read a book with unexpected overlap with my professional experience (which, of course, is part of the point). 

I’d like to share one I read recently. 

Path Between The Seas

panama

The Path Between The Seas by David McCullough describes a good portion of the history of the construction of the Panama Canal.

It covers the early motivation to build the canal, efforts to build consensus, and stories of success and failure. 

There are additional fascinating details related to political, social and medical issues surrounding the endeavor.

When it comes to large engineering projects, there are few that top the Panama Canal.  But I’d like to distill a few details which seem to recur in projects regardless of scale.

Evangelizing

220px-Ferdinand_de_LessepsFerdinand de Lesseps, having developed the Suez Canal, was instrumental in evangelizing support for the Panama Canal.

However, there’s some evidence that Lesseps’ evangelism was less affected by actual project status than it could have been.

There are some stories of him reporting progress substantially more favorably than he had observed firsthand, and also collecting estimates from expert subordinates and “adjusting” the estimates downward.

Hmm.

Lesson: charisma is an amplifier; projects need evangelists, but to be effective they need to be pointed in the right direction

Getting It Going

150px-John_Frank_StevensJohn Stevens was an early chief engineer during the second major phase of canal construction.  He was very hands-on and beloved by his workers for that among other reasons. 

Stevens really seemed to Get The Thing Going, and had the foresight to improve the industrial and medical infrastructure to the point that canal construction was actually feasible.  He pragmatically stated

… the problem is one of magnitude and not miracles.

Lesson: every project needs someone to turn the dream into reality

Building It

220px-George_Washington_GoethalsGeorge Goethals followed John Stevens on the project.  He was not particularly well liked at first, but ultimately earned deep respect from his workers. 

Joseph Bishop, a New York reporter, recalled of Goethal’s relations with workers that

They were treated like human beings, not brutes, and they responded by giving the best service within their power

He brought organization, efficiency, and discipline to the project, and ultimately was the one who Built The Damn Thing.

Lesson: every project needs someone who can Build The Damn Thing

Simplicity

The construction of the Panama Canal featured advancements in engineering and medical science.  It was an early example of electrical control systems (and a major project for General Electric).

I’d like to highlight one feature that caught my attention from a work flow perspective.  It involves the central control panel for the canal.

From the book, pp 602-603

The genius of the system, however, was in the elaborate racks of interlocking bars concealed from view beneath the board.  For not only was the operator able to see the entire lockage process in miniature and in operation before him, but the switches were interlocking-mechanically.  Each had to be turned in proper sequence, otherwise it would not turn.

In brief, the control board implemented a mechanical state machine which rendered operator errors impossible. 

That is, designed to be inherently simple, bug-free and foolproof – I like it.

Lesson: it takes hard work to make things simple, yet is often worth the effort

 

This blog post is a reprise of an article originally written in September 2009.

Posted in Books, Leadership, Simplicity | Leave a comment

Scoping for 90%

90 percentI’ve been working at Zynga since early 2010. 

One of the challenges of running an online game (like Café World, on which I’ve spent most of my time) involves releasing new features on a regular, predictable cadence.

As a result, our team has devoted resources to collecting metrics on feature development and release timing.  We use that data as a feedback mechanism to adjust our scoping and scheduling guidelines.

The approach outlined below describes a process for constructing schedules with relatively high confidence.  It also gives a statistical foundation for justifying “padding” which might otherwise raise the eyebrows of skeptical managers. 

Driving to Work

driving-to-workTo the left is a histogram of the time required to drive 18 miles to work, over many dozens of trips.  The data is not perfect, but roughly models a route that I drove frequently – a mix of highway and local roads.

Most days, the trip took about the same amount of time, around 30 minutes. 

An occasional traffic accident would hold things up, maybe requiring 45 minutes.  Sometimes bad weather would slow things down; an accident and bad weather together would be even worse – requiring perhaps an hour.

Rarely, with unusually clear traffic and cooperative traffic lights, I could race home in only 20 minutes.  But never faster.

Schedules Are Subjective

If you asked me “Steve, how long does it take you to drive to work?” I could sensibly answer

“About 25-35 minutes”

reflecting the average, and most common trip times.  And about half the time, I’d be right.

TrafficHowever if I had a 9am meeting with the CEO, you could be certain that I would leave at 8am or earlier, in order to have a nearly 100% chance of being there on time. 

If you wanted to pin me down to something certain, my answer would be something closer to

“An hour or less”

When the stakes are high, a schedule with 50% confidence just doesn’t cut it.

Variability In Driving

Relative to software development, driving to work is a technically non-complicated task (apologies to all you professional drivers out there).

Driving to work is easily understood, and easily repeatable.  In my example, the route is executed each time by the same person, in the same way.  Only the environmental conditions vary, yet they substantially impact the actual execution.

In spite of the many constants, we observe a remarkable 3:1 variation in performance (20 to 60 minutes). 

That is fairly surprising for this non-complicated task.

Tossing Coins

coin-tossesImagine you are constructing a schedule comprised of 10 tasks which must be executed in sequence.  Each has an independent 50% chance of requiring 1 day to execute, and a 50% chance to require 2 days to execute.

Clearly the project will require 10 to 20 days to complete, but what would be a safe estimate?  Would the midpoint of 15 days be a reasonable schedule commitment?

coins-annotatedThis admittedly simplistic example can be modeled as a series of coin tosses, with a probability distribution as shown in the figures above and to the right.

Because the distribution is symmetric, there is only a 50-50 chance that the tasks will be completed in 15 or fewer days. 

Scheduling for 15 days is not a winning strategy for a high-confidence commitment.

In the figure to the above right, the same distribution is shown with the rightmost bins annotated with the likelihood that the completion time will be fewer than the indicated number of days.

coin-tosses-90We can use this information to construct a schedule with relatively high confidence.

The figure to the right shows a bounding box around 90% of the schedule possibilities. 

A schedule estimate between 17 and 18 days will be too short only 1 in 10 times.

Statistical Variation is the Norm

Even if our estimates are perfect (and they are not), environmental factors intrude.  The network or VPN can be down, source code control can be broken, or the build might not work.  A colleague may have gifted you with an unusually complicated branch merge.

These things happen all the time, yet we often pretend they do not.  Software estimation, even when done well, is a highly stochastic process.

Scoping for 90%

I encourage our teams to scope and schedule for a 90% on time rate, since the consequences of schedule misses are fairly severe.

When iterating over a large number of feature iterations of similar size and complexity, it is possible to accumulate statistical evidence to help drive this process in a compelling manner.

For tasks which are highly novel, unusually complicated, or having strong external dependencies, variances are naturally much higher and statistical categorization can remain elusive.

But it’s always worth tracking the original estimates, the actual execution, and their historical variations.

Posted in Management, Software, Zynga | 2 Comments

Quadratic Songs and Books

quad-ballsMy son is 2 1/2 years old, and loves stories.  His favorite book at the moment is A Fly Went By.

In the book, a boy sits lazily by the lake and observes a fly passing.  The fly in turn is pursued by a frog, who is in turn chased by a cat, and so on.

Each animal introduced is pursued by yet another, and a pattern emerges in the story.  For each new animal

  • The animal is introduced
  • All the prior animals are again enumerated

In this manner, following the introduction of the dog, the story goes:

The fly ran away in fear of the frog
who ran from the cat, who ran from the dog …

Cumulative Stories

This style in song form is called cumulative, and other examples include the familiar Twelve Days of Christmas, for which on day three we have

On the third day of Christmas, my true love gave to me…
3 French Hens
2 Turtle Doves
And a Partridge in a Pear Tree.

Yet another similar example is the song There Was And Old Lady Who Swallowed a Fly.  After swallowing a bird, spider and fly, the song goes

There was an old lady who swallowed a bird.
How absurd to swallow a bird.
She swallowed the bird to catch the spider,
that wiggled and wiggled and tickled inside her.
She swallowed the spider to catch the fly.
I don’t know why she swallowed the fly.
I guess she’ll die.

Each has a similar pattern.

Quadratic Behavior

With some amusement one evening while reading A Fly Went By, I realized that this style exhibits quadratic behavior.  That is, the length of the song/story increases with the square of the number of actors/stanzas. 

This is evident due to the number of actors/stanzas enumerated in each of the N segments in sequence:

1
2
3

N

Arranged with an equivalent number of objects (dots, for example) on each line, the sequence forms a half-triangle pattern, as pictured at the top of this article.

If you accumulate all the sizes of all the segments, we have the numerical series

1 + 2 + 3 + … + N  =  N (N+1) / 2

which, for large N, is dominated by the term N2.  In computer science, an accumulation like this is frequently an indication of non-ideal algorithm design.

What’s The Bottom Line?

In summary, if you double the number of actors / stanzas, the resulting book / song will be not twice, but four times as long.  “24 days of Christmas” would be an excruciating 4 times as tedious to listen to, relative to the (already tedious) 12 days.

It isn’t very surprising, then, that these songs and books generally tend to call it quits after 8-12 segments.

In the future, my interview questions may include children’s books.

Posted in Software | Leave a comment

Klink’s Hierarchy of Train Wrecks

train-wreckYou’ve heard of Maslow’s hierarchy of needs?  I’ve got Klink’s hierarchy of train wrecks.

I was talking to a colleague recently about basic expectations for staff responses in adverse situations, based on their level of experience. 

The further up the ladder you are, the higher the expectations for proactive observation and corrective action.

Hiearchy of Train Wrecks

I have in mind something like this

  • passive

That was nasty. What happened?

  • observation

I was in a train wreck!

  • communication

I inform others that a train wreck occurred, and describe the details.

  • analysis

I can describe the root cause of the train wreck, and find ways to avoid the same in the future.  My analysis is objective and dispassionate, of course.

  • proactivity

I can see conditions shaping up for a future train wreck.  I communicate that to others and actively work to avoid the accident.

  • prevention

I accept that trains wrecks, while regrettable, are inevitable.  I actively work to reduce their frequency and impact.  This may involve a combination of training, process and technological improvements, political maneuvering, and so on.

  • extinction

I implement a process or technology shift (riding bicycles for example) which eliminates train wrecks as a class of problems.

The goal is to spot organizational train wrecks early, communicate that they are forthcoming, mount resources to correct them and (ideally) factor out their possibility of occurrence.

Posted in Leadership, Management | Leave a comment