Flipkart Interview Question SDE-2s
Team: Retail
Country: India
Interview Type: In-Person
Testing Code:
public class Test {
public static void main(String[] args) {
int n = 15;
ArrayList al = new ArrayList();
al.add(new Integer(1));
int i1, i2, i3;
i1 = i2 = i3 = 0;
int min = -1;
int index = 0;
for (int i = 1; i < n + 1; ++i) {
min = Math.min(
Math.min((2 * (int) al.get(i1)), (3 * (int) al.get(i2))),
(5 * (int) al.get(i3)));
al.add(min);
index++;
if (min == 2 * (int) al.get(i1))
i1++;
if (min == 3 * (int) al.get(i2))
i2++;
if (min == 5 * (int) al.get(i3))
i3++;
// System.out.println("Index:"+index+"="+min);
}
System.out.println("Index:" + index + "=" + min);
}
}
i dont think it ll work properly. when i1 is increased after getting 4, can we ever get 5.
after the log:
mlg2 + nlg3 + plg5
then we know:
2lg2 < lg5
lg2+lg3 > lg5
so the incresing pattern is
1 0 0
0 1 0
2 0 0
0 0 1
1 1 0
3 0 0
2 1 0
4 0 0
2 0 1
3 1 0
so we will get the answer soon
Good idea about log but am not sure how it helps. Also if the number of factors increase by just 1 then the number up combinations will go up exponentially. Here is a different approach to the problem.
The idea is to find the next combination of [m,n,p] using dynamic programming.
Create an array out[N][N][N] to store the various values of product for different combination of [m,n,p] where N is the N'th number we have to find.
//track which factors have been used (Y = Yes, N = No). we will see its use towards the end
used_flag = [N,N,N]
//base values of m,n,p. This will be clear in the end
base_val = [0,0,0]
//pervious combination of [m,n,p]
prev_comb = [0,0.0]
for p = 0 to N
//the next number will have one of the values of [m,n,p] increased. So lets assume the value of all increased by 1
new_comb = prev_comb + [1,1,1]
//try all possible combinations till base_val to find the next smallest number
//finding out value of number with the new combination of m,n,p
min = value(new_comb)
last_val = value(prev_comb)
for i from new_comb[0] to base_comb[0]:
for j from new_comb[1] to base_comb[1]:
for k from new_comb[2] to base_comb[2]:
if out[i][j][k] == 0:
out[i][j][k] = (2^i)*(3^j)*(5^k)
//do not process any value which is smaller than the previous value
if out[i][j][k] <= prev_value:
continue
if min>out[i][j][k]:
temp_comb = [i,j,k]
min = out[i][j][k]
prev_comb = temp_comb
find out which of the value of m,n,p increased at the end of the iteration and marked used flag as Y for that. Once all flags are marked as Y change the value of base combination to that of temp_comb and used_flag = [N,N,N]
With the help of used_flag and base_comb we are able to reduce the number of times the inner loop of i,j,k runs. e.g. in the given example once the value 30 (which contains all factors used atleast once) we only want to check all combinations of m,n,p which will be greater than its combinaion.
Hope the explanation was sufficient.
We don't need to create the list even to get the nth number, following code works without the having to create the list:
public static void main(String[] args) {
int multipleOfTwo = 2, factorTwo = 1;
int multipleOfThree = 3, factorThree = 1;
int multipleOfFive = 5, factorFive = 1;
int n = 10;
int finalNumber = 1;
while (n > 1) {
finalNumber = Math.min(multipleOfTwo * factorTwo,
Math.min(multipleOfThree * factorThree, multipleOfFive * factorFive));
if (finalNumber == multipleOfTwo * factorTwo) {
factorTwo++;
}
if (finalNumber == multipleOfThree * factorThree) {
factorThree++;
}
if (finalNumber == multipleOfFive * factorFive) {
factorFive++;
}
n--;
}
System.out.println(finalNumber);
}
- jiangok2006 March 27, 2014// 1 f(0) // 2 min(2*f(0), 3*f(0), 5*f(0)) // 3 min(2*f(1), 3*f(0), 5*f(0)) // 4 min(2*f(1), 3*f(1), 5*f(0)) // 5 min(2*f(2), 3*f(1), 5*f(0)) // 6 min(2*f(2), 3*f(1), 5*f(1)) // 8 min(2*f(2), 3*f(2), 5*f(1)) public static void mainFunc(int n) { List<int> f = new List<int>(); f.Add(1); int i1, i2, i3; i1 = i2 = i3 = 0; for (int i = 1; i < n + 1; ++i) { int min = Math.Min(Math.Min(2 * f[i1], 3 * f[i2]), 5 * f[i3]); f.Add(min); if(min == 2*f[i1]) i1++; if (min == 3 * f[i2]) i2++; if (min == 5 * f[i3]) i3++; } Console.WriteLine(f[n]); }