Interview Questions And Answers 
-
You need to multiply say, 5123 x 3333 (yes, it’s an obvious example) without using calculator etc. How would you go about doing it?
7,852 Views |
(17 votes, avg: 3.71)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Well, you work out that 5123 x 3 = 15369. Write it down and then appropriately add zero’s and add.
These types of problems typically are known as caching problems. Save your results so you don’t have to do it again!
It’s not always so dramatic, but how many times do you want to recalculate things? The classic example of the Fibonacci sequence is an example:
f( n ) = f( n - 1 ) + f( n - 2 )
It’s trivial to translate this recursively. So we do. Unforunately, if you want to know, say, the 100-th Fibonacci number, and your computer does, say, a trillion calculations a second, it will still take, about 11 years to get your answer. So save and reuse your results! If you did do that, even if you only do 100 operation a second, it’ll take less than a minute!
Yes, someone’s going to point out you only need the last two numbers, so you can use a for loop. You’re perfectly correct, and that’s “Dynamic Programming” (DP). Sometimes memoization is faster, sometimes dp is faster. Experience will tell you which one is which.
I’m handwaving right now, but this isn’t simply “saving down results”, of course. DP/Memo is when you know that certain results will be re-used in the future, exploiting the fact that well, you don’t need to redoing the same thing over and over again..
Assuming I am using C.
5122 = 4098 + 1024 + 1
= 2^12 + 2^10 + 2^0
In this case:
1. Shift 3333 to the left 10 bits => A
2. Shift A to the left 2 bits => B
3. answer = A + B + 3333
Answer 3 is not correct
4098+1024+1 = 5123
Answer #3 is almost near to solution.
It should have been
5122=4096+1024+2
=2^12+2^10+2^1
1. Shift 3333 to the left 1 bits = A
2. Shift A to the left 9 bits = B
3. Shift B to the left 2 bits = c
4. Answer = A+B+C
answer 5 is not correct
3333*2^12 = 13651968
3333*2^10 = 3412992
3333*2^1 = 6666
total 17071626
BUt actual result of multiplication is 17074959
There is 3333 difference between the answer and above result.
It should have been
5123=4096+1024+2+1
=2^12+2^10+2^1+2^0
1. A = shift 3333 left 12 bit
2. B = shilf A Right 3 bit
3 C = shift A Right 7 bits
4 D = shift A Right 1 bit
4. Answer = A+B+C+D
5123 x 3333 =
((5123 x ((3 x 3333) + 1)) – 5123) / 3 =
((5123 x10000) – 5123) / 3 =
(51230000 – 5123) / 3 =
51224877 / 3 =
17074959
void doMultiply(int a, int b, int *result)
{
*result = 0;
while (b–) {
*result += a;
retrun;
}
Leave an Answer/Comment