Flipkart Interview Question for Software Engineer / Developers






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

will some1 please tell how by dynamic programming??

- Hector January 30, 2012 | Flag Reply
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.

- jwalaWaasi March 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- supriya March 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- jwalaWaasi March 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- turbochrgd July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous September 18, 2011 | Flag Reply
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.

- Arne March 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You cannot store 1000000! in any primitive data structure!

- Anonymous April 21, 2012 | Flag
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 !

- Prashant October 14, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More