## Flipkart Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
1
of 1 vote

will some1 please tell how by dynamic programming??

Comment hidden because of low score. Click to expand.
0
of 0 vote

You might need to implement your own Big number package for this - represent each number by a list and perform multiplications on them.

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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-
Start from the last digit and add corresponding digits taking care of carry overs.
The pseudo code might look like as follows -
{
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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you missed the point of using dynamic programming here!!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

yup, it should be done using dynamic programming ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0

You cannot store 1000000! in any primitive data structure!

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think u can process it using a string array of digits !

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.