The hardest interview situation I’ve ever faced was when an employer revealed a chalkboard full of database relationships from behind his desk and forced me to start writing specific queries on the spot. It’s a little intimidating when you’re completely unprepared and I’ll admit I was a smidge rusty. As a follow up to what my brother wrote about interviewing programmers, check out some of the questions ITA Software asks their potential employees :
> Word Rectangle
Write a program to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom).
> Lucky Sevens
Write a program to compute the sum of all the integers between 1 and 1011 that are both divisible by seven and, when the decimal digits are reversed, are still divisible by seven.
> Palindromic Pangram
A palindromic pangram is a multi-word palindrome that includes all 26 letters of the alphabet. Write a program to find a palindromic pangram.
Maxnoy says that, “the good news is that interview question repertoire is generally very limited. The Programming Interviews Exposed book covered or helped on probably 60-70% of questions I got.” For more programming interview questions to see what you’re made of, check out Maxnoy’s List of Questions and One Particular Harbor.
What’s the craziest programming question you’ve ever faced?
I once interviewed for Microsoft in Mexico. They asked the standard cannibal/monk variation problem (this particular incarnation included the U2 members with a flashlight), which I — stupidly — couldn’t solve until about an hour after the interview, when I had stopped thinking about it.
They also asked me to make a fast program for computing prime numbers.
Back in the dot com days I was asked to write a fibonacci program by a 20 year old interviewer (he was the CTO).
I did the Lucky Sevens with seven lines of code and got: 102,049,428,685,193,293,045.
Watch out though, this number needs 67 bits unsigned (you can’t fit it into 64 bits).
Oh good — I got that same number for the sevens problem (indeed, found this page because it’s the only hit for Googling on it); nice to get confirmation of the answer.
Mine took 15 lines, but in my defense, it ran in 0.09 seconds. I’m kind of disappointed that they made the upper bound just low enough that it’s feasible to do it by brute-force calculation; it should be 100 trillion instead of 100 billion. (Then the sum would be, um, 102041179796115463104759635, an 87-bit integer [0.13 sec].)
FairDice, I didn’t spend too long thinking about the math, so I went for brute force. Mine took 7 hours!
Mine took about 18 minutes on a reasonably fast machine. It wasn’t brute force, but I guess it wasn’t that clever either. I’d be interested to know the algorithm that could give you the answer in less than a second.
Oh, I remember this puzzle. My solution, for anyone who is still interested, was placed at http://www.michael-maniscalco.com/lucky sevens/luckySevens.htm
The source code also included a hand C++ 128 bit class. It isn’t super fast, but it fit the need regarding this puzzle.
I think the time required was less than 0.0001 seconds or so on my 3GHz machine if I remember correctly.
I got asked the standard “how do you move a mountain” chestnut.
“So, I have a budget in the billions?” Yes. “The mountain is in the US?” Yes. “The test for a moved mountain is …?” The highest point on the mountain must correspond to the new location and the peak cannot be moved separately from the rest of the mountain.
“How far do I have to move it?” 10 meters east.
Easy peasy.
Hire minions to covertly track down everyone with direct administrative control over the USGS topographic database.
Using the unlimited budget, bribe the senior members of that group to set the recorded GPS coordinates for all USGS survey points within 25 kilometers of the mountain peak 10 meters east. (Accompanied by whiteboard graphics in three colors.)
For each USGS survey marker within the range 25 to 75 kilometers from the mountain peak, modify the recorded GPS coordinates to smoothly deform the orihginal coordinate grid to disguise the modifications made in Step 2. (More whiteboard magic in a fourth color.)
Repeat Steps 1-3 for the land resource organizations in the states and/or provinces containing any part of the grids described Steps 2-3.
…………………………
Preliminary project estimates: 60 days, $5-20 million direct costs (minions), $1.5 to $4.5 billion ‘consultation’ fees depending on location of target mountain.
That ended the interview cycle. I think I won the job on deviousness-plus-style points.