Log in

No account? Create an account

Previous Entry | Next Entry

It has occurred to me that what I've been posting about problem solving may not be so clear to all of my readers, so here is an example of something that is hopefully easy to understand yet illustrates the topic well.

Multiply the numbers 95 and 85 only using one-digit multiplications, shifts, and subtractions. (A shift allows one to do multiplications or divisions in one step. For example, 8 is 1 shifted three places to the left (with zeros) in binary (base 2). 10 (base 2) equals 2 (base 10), 100 (base 2) equals 4 (base 10), and so on. Assume you can do a shift in any base.) Do not do it the long way.

The trick is to notice that 95 * 85 equals (90 + 5) * (90 - 5) which is equal to 90 * 90 - 5 * 5. Thus all you need to do is two simple multiplies, a shift of one product by two zeros to the left, and a subtraction to yield the answer 8075.

So, this doesn't seem too difficult, right? Well, if you see that the product has the property of the difference of two squares, no. But you might not see it, which is sort of what I'm getting at with regards to problem solving, interviews, tests, etc.: depending on one's frame of mind one might not see the trick and get stuck. Also, there are times when the question will not be phrased to give an indication that the asker is looking for an elegant or insightful solution, so one's first reaction to the question might be to do it the long way, especially if one is stressed out.

As to what this might have to do with computer science, there are issues in computer architecture and digital design that involve fast computations (and special-purpose hardware to carry out such computations). Someone who's interviewing someone for such a job might ask this type of question looking for an answer that shows an understanding of how to do fast computations.


( 1 comment — Leave a comment )
Feb. 26th, 2006 12:55 am (UTC)
Alternatively, shift 1 by 2 places in base 90 and base 5, and subtract one from the other :P
( 1 comment — Leave a comment )

Latest Month

December 2017

Page Summary

Powered by LiveJournal.com
Designed by Tiffany Chow