Jarrod Trainque

3Aug

The new breed of programmer recruiting

Posted 3 years, 4 months ago - 13 comments

So there’s a new batch of recruitment ads on the MBTA’s red line. ITA software is looking for programmers, and the ad campaign makes use of puzzles as a form of preliminary candidate qualification.

If this looks familiar to you, it’s because last year google launched a similar campaign. Google challenged potential candidates to find the first 10-digit prime found in consectuive digits of e.

The difference, it seems, is that ITA Software’s puzzles seem considerably less challenging. Anyone with even a rudimentary understanding of programming should easily be able to solve their brainteasers. For example, here’s one that I saw today: What is the sum of all the integers between 1 and 100 billion that are divisible by seven, and when the digits are reversed are still divisible by seven?

Surely this isn’t as difficult as the google challenge. While I won’t actually solve the problem, here are the steps I’d take to solve it (you could use whatever programming language you like).

  1. declare a variable, say n, and give it an initial value of 1
  2. declare another variable, say x, and give it an initial value of 0
  3. declare a third variable, say m, and give it an initial value of 0
  4. divide n by 7
  5. if n divided by 7 returns a remainder, increment n and go to step 3
  6. if n divided by 7 does not return a remainder, reverse the order of the digits in n and save it to m
  7. divide m by 7
  8. If m divided by 7 still doesn’t return a remainder, add n to x, increment n, and go to step 3.
  9. if n = 10^11 (100 billion), stop
  10. return x

Now, everything here, except perhaps step 6, should be really easy for even a newbie. My questions:

  • does this work? If not, what am I overlooking?
  • how would someone reverse the digits (in step 6) using PHP?
  • This uses 3 variables: one for counting/incrementing, one for a cumulative sum, and another for digit reversals. Is there a more efficient way to do this?

A softer approach

Here’s a totally different way to look at this problem. I created a table with the first 14 multiples of 7 along listed alongside their reversal, and checked to see if any of the reversals were divisble by 7. A pattern came up, namely that only the reversals of multiples of 7 created through 7x where the digits of x were either a 1 or a 0 seemed to work. For example, 77, 7007, 70000707, and 7000077777 are all divisible by 7, as are their reversals.

This would seem to suggest there’s a special property of multiples of 7 whereby only numbers containing 7 and 0 are divisible by 7 both forward and reversed. (This is akin to the “mystical” property of multiples of 9 where the sum of the digits always equal another number divisible by 9). It’s probably unlikely that this is the case, but based on a very small initial data set, there’s something to suggest it might be possible. Especially when one considers that this is a puzzle, and puzzles tend to have some sort of trick or special quality to them. Granted, this is a programming exercise, but in solving puzzles, one should always consider the puzzle-maker, and more importantly, the conscious decisions he or she made (e.g. choosing “seven” as the all-important number here).

Yeah, so if you make the leap of faith and assume that 7 has some special property, you can rephrase the problem as the sum of all digits from 1 to 10^11 where each digit is either a 1 or a 7. This saves you the trouble of reversing digits (step 6 above) and makes the calculation really easy, but if your assumption about the properties of multiples of 7 is incorrect you’ll end up dead wrong.

Question:

  • Can you supply an example of a number that is divisible by 7, and is also divisible by seven when the digits are reversed, AND contains a digit other than 0 and 7? (If it is possible, then obviously the second method won’t work).

update: Silvio points out that the number 168 is divisble by 7 forward and reversed. And so making the aforementioned assuption is totally wrong, as is often the case with assumptions

You can follow any responses to this entry through the RSS 2.0 feed. You can leave a comment, or trackback from your own site.

13 Comments

  1. Comment by Marcelo — August 3, 2005 @ 11:19 pm

    Well done Jarrod. You are truly wicked smaht. And I have the PhD? Where is the justice? I love these ads. Maybe kids will read them and start taking math seriously. Damn I wish I had.
    For anyone with questions or interested in applying to ITA, my boyfriend works there.

  2. Comment by Silvio — August 3, 2005 @ 11:34 pm

    Hi Jarrod,

    Marcelo just pointed me to your post.

    The difference, it seems, is that ITA Software’s puzzles seem considerably less challenging.

    Well, I don’t know. This particular one might be easy, but how many days would the brute force program run? 100 billion is big. I haven’t tried this puzzle, but I bet there’s lots of room for optimization.

    As to your question - how about 168 ?
    Or, even

      perl -e 'for($i=7;1;$i+=7){
  $s=sprintf("%d",$i);
  $r=reverse($s) % 7; print "$sn" unless $r }'

    Silvio.

  3. Comment by Jarrod — August 4, 2005 @ 9:50 am

    Yup. I suspected it wouldn’t be long before someone working at ITA would end up reading this.

    Yeah, I was thinking about how long it would take to run this program. PHP, the only real language I’ve mucked around with, definitely has thresholds below 100 billion. Maybe if you ran the brute force script mentioned above 24/7 for a few days? I dunno, but you are totally right. My solution requires some serious number crunching, and probably wouldn’t get you a job.

    Your perl solution is quite nice. I’m not totally familiar with the syntax, but one thing stands out: the reverse() function, which I assume is native to the language(?).

    It makes me wonder if the solution to this problem is less about how you’d do it (I mean, even I could craft up the brute force solution), but rather about what you know in terms of specific programming syntax and functions.

    And yes, my little leap of faith involving some hidden property of multiples of 7’s is (as I suspected) dead wrong. (Kudos to ITA for not employing this kind of trickery in their puzzles.)

    Nonetheless, you’d be surprised at how many times you can arrive at an answer to a puzzle through first recognizing that it’s a puzzle, and the creator made specific decisions. It just doesn’t work in this case.

  4. Comment by Jarrod — August 4, 2005 @ 10:23 am

    Speaking of brute force crunching of large numbers, this reminds me of a PHP script I wrote once:

    First One Million Integers - NOTE: clicking may cause your browser to crash! (Alternately, here’s one million zeros which is easier on the browser, but still big.)

    The first script very simply increments a number and spits out the result. It takes about 1 minutes to run (including HTTP transport to the browser), but if you use it as a rough estimate of how long it takes to count to one million, you can get a ballpark figure of how long it would take to count to one hundred billion. If it takes about 1 minute for a computer to “count” to a million, it takes the same machine about 100,000 times as long to count to 100 billion. That’s 100,000 minutes , or 1667 hours, or 69.4 days, or over 2 full months.

    And since it takes longer to process numbers as they get larger, in reality it would take even more time than this conservative estimate.

    So… given this knowledge, I retract my earlier statement about the ease of this problem.

    Revised considerations now include:

    • figuring out how to deal with massive numbers (brute force won’t work)
    • optimizing the script for maximum efficiency
    • making use of native functions such as reverse() and the modulo (%).
    • the processing power of the machine being used to crunch the numbers
  5. Comment by John — August 8, 2005 @ 12:48 am

    Jarrod,

    Hi. I just stumbled on your site while trying to find the answer to the ITA problems, which I also saw advertised on the Red Line. I think the point of these problems is exactly as you noted: they seem easy, but the brute force method takes ages to run. I wrote a PHP script to solve the Lucky Seven problem by brute force. I thought I was pretty smart. But then after the script had run for 24 hours on my machine (not on a server) it had only tested a tenth of the multiples of seven necessary and I knew I was on the wrong track.

    So while brute force may be a possible solution for ALL the problems, it’s not what they’re looking for. ITA’s whole business is finding the cheapest fares possible out of trillions available. Most of the problems they face in real business could probably also be solved by brute force, IF their users were willing to wait a week for the flight fares page to load on their browser. But in real life you need something faster.

    There must be a trick to all the puzzles, but I haven’t been able to find them. I’m trying to a discover a pattern to what multiples of seven are also such when reversed. Here’s a page I made that shows a grid representing all the numbers from 1 to 10,000 (numbers go horizontal then down): http://www.bostonmathtutor.com/lucky_sevens.php. I’ll leave it up through 8/13/05. On that grid, multiples of seven are yellow, numbers who’s reverses are multiples of seven are blue, and numbers that are multiples of seven both forwards AND backwards are green. A general pattern stands out, but I don’t know how to use it.

    What do you think?

  6. Comment by Jarrod — August 8, 2005 @ 9:32 am

    John. Great post, love the script. There’s something really fascinating with the idea that average people, prompted by a subway ad, have took it upon themselves to start looking for patterns in math.

    As for the grid you posted… I think the key to finding a pattern lies in the width of the grid before wrapping. Starting on a green square and going up 1 row and 9 to the right seems to bring you to another green square. Maybe if you shifted the rows so that the green squares fell on top of one another the pattern would reveal itself a bit.

    I also took a different approach, and graphed out the ratio of integers and their reversals. While this was prompted by the ITA puzzle, it really has little to do with the Lucky Sevens problem.

    Here’s my graph (made in excel): Ratio of Integers and Their Reversals

    What I was curious about was if the ratio of a number to its “reversal” trends towards anything, and to better understand the relationship/properties of reversed numbers… What I found was a self-similar (fractal) graph that doesn’t trend towards any one constant.

    If you can tell me if/how this is relevant to the Lucky Sevens problem, I’d be very interested.

  7. Comment by John — August 8, 2005 @ 11:04 pm

    Jarrod,

    You are definitely on to something about the pattern becoming clearer by changing the grid width. I reduced it from 100 to 91 in the script. The difference is striking.

    See for yourself. It’s still up at the same place here

    Also, thanks very much for responding to my post. I agree that it is very interesting to have a problem and discussion like this prompted just from a subway ad.

  8. Comment by Jarrod — August 9, 2005 @ 9:05 am

    John: Wondering if you’d post a .txt file of your php so I could do some exploring(?)…

    I think it’d be helpful if on mouseover it displayed the number it’s referencing…

  9. Comment by John — August 10, 2005 @ 11:57 pm

    Jarrod,

    Having a mouse over show the cell’s number is a good idea. Here’s a link to a .txt file of the PHP scipt that produces the grid: http://www.bostonmathtutor.com/lucky_sevens.txt

    I really wish I new how this problem would be best solved. I expect when the anser is eventually wide spread it will be one of those things where you go “Oh! Of Course!”

  10. Comment by Jarrod — August 14, 2005 @ 10:26 pm

    update: This post was quoted on boston.com

    Unfortunately, the quoted passage was a completely wrong approach to solving the problem as the comments above note, and taken out of context. Makes me feel a little stupid.

    doh!

  11. Comment by James — August 16, 2005 @ 6:32 pm

    Heh he. I also saw this on the train ride home from work last night. Dug out my C fingers and wrote a version that ran in 2 hours for the 100B numbers. It did need to run on a 64bit machine with a fair bit of oomph, and all the compile flags turned up to ‘11′. Great! Or so I thought…

    As turns out, not so much.

    I talked to a good friend at work, and he came up with the answer and code that takes 0.09 seconds against my 2 hours, and gets the same valid answer without the brute force walk through number space:

    % time maple < lucky7.maple
    bytes used=1986328, alloc=1965720, time=0.09

    I’m not going to share his method (it’s not mine for a start off), or the results as it’s a bit unfair to ita and people who really want to apply for the job. Anyway, there are some pretty clever folk out there that ita are looking for…

    I found out today that I’m not one of them :-)

  12. Comment by Randy — August 21, 2005 @ 5:53 pm

    PHP has a function called “strrev()” which will reverse the string the way you want it.

  13. Comment by Eric Brown-Munoz — September 5, 2005 @ 9:49 pm

    I posted a solution to “Lucky Sevens” which, implemented in Java, runs in .21 seconds on my laptop (this includes time initializing the VM).

    The trick is the word “sum”. You don’t need to find every number that is a “lucky seven” in order to find the sum. You just need to break the search set into “chunks” and find common sums.

    The solution is on my website:

    http://www.brownmunoz.com

    There you will find a not too poorly written explanation and a tar file with working Java source (you can tell I am much more comfortable writing software than English).

    I submitted this to ITA software a couple of weeks ago, and got a terse (standard) rejection letter with no mention of the solution (or the work I put into finding it).

    But c’est la vie in this job market…

RSS feed for comments on this post.

Leave a comment