Flipkart Interview Question
Software Engineer / DevelopersYou might need to implement your own Big number package for this - represent each number by a list and perform multiplications on them.
How to perform multiplications on these? Let me tell what i understood from ur solution. Correct me if i got it wrong.
Supppose we have a huge number which cannot fit in any primitive data type we have our own class. In this a list is created using each digit of the number rite? soo number is like 11111111111111111111111111111111111 there will be list of soo many elements with each element having a value of 1.
I hope i got it correctly. If this is the case how do we perform operations on this?
Precisely. For example, if your actual number is 204. It would be represented as 2->0->4
or 4->0->2 (whichever way you like)
Now you need to implement two functions-
1) add(lstNum1, lstNum2)
Start from the last digit and add corresponding digits taking care of carry overs.
The pseudo code might look like as follows -
add(lstNum1, lstNum2)
{
lstResult = []
carry=0
for i in range(0, min(len(lstNum2),len(lstNum1))
{
lstResult[i] = carry + (lstNum1[i]+lstNum2[i])%10
carry = (lstNum1[i]+lstNum2[i])/10
}
//now copy all the other values
if(len(lstNum1) > len(lstNum2))
{
for i in range(len(lstNum2),len(lstNum1))
{
lstResult[i] = lstNum1[i] + carry
carry = 0
}
}
else
{
for i in range(len(lstNum1),len(lstNum2))
{
lstResult[i] = lstNum2[i] + carry
carry = 0
}
}
return lstNum
}
Once you can add two Big numbers, iot is quite trivial to multiply them, just take one number and multiply every other number in mutliplicand and then shift and add.
Hi, To apply dynamic programming we need to first insure that the problem must have
1) Optimal substructure properties -> this means at any point i have to make a choice which optimize my solution, and this choice divide the problem into at least two sub-problems which i need to solve optimally again. if the choice divide the problem into a single sub-problem ->> use greedy algorithm.
2) It must have overlapping sub-problems, -> In first requirement the sub-problems must be overlapping to each other, if not use recursion, else use 3rd property to reduce the complexity from exponential to polynomial.
3) Memorization -> this mean store the solution of sub-problem which you have already calculated.
In greedy algorithms we still have to make a choice but that choice divide the problem into a single sub-problem (such as activities scheduling, fractional knapsack problem etc.) but problems like calculating optimal matrix chain multiplication are solvable only using dynamic programming, you can make many problems of similar kind.
@Hector,
For find the factorial of n (F(n)) we need to know F(n-1).
Lets say, for F(5) we need to find F(4) and we have to multiply the result with 5.
so F(1) = F(0)*1
F(2) = F(1)*2
F(3)=(F2)*3
F(4)=F(3)*4...and so on.
Instead of finding F(1) (or even F(2) or F(3)) several times, we can do tabulation.
So,
F(1) =1
F(2) =2
F(3) =6
F(4) =24.
so F(5) is 24*5 = 120
and F(6) is 120*6 =720 and goes on.
Here comes dynamic programming. We use the result (or intermediate results) of a sub problem to find the result for big problem.
will some1 please tell how by dynamic programming??
- Hector January 30, 2012