## Flipkart Interview Question for Senior Software Development Engineers

Country: India
Interview Type: Phone Interview

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

Seems the sequence mentioned in the question should start from 2 as 1 is not a multiple of 2 or 3 or 5.

An O(n) solution using DP can solve the problem by computing the values from 1st to the Nth number.

0. Maintain a counter, that is initialized to 1 and start from an initial value v, say 2.
1. Keep incrementing the value v and check if it is divisible by 2 or 3 or 5.
2. If divisible, check if the corresponding quotient of v/2 or v/3 or v/5 is present in the solutions to subproblems that are already computed. If yes increment the counter.
3. Return value v when the counter becomes N.

``````import java.util.HashMap;
import java.util.Scanner;

public class Multiplesof2and3and5 {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
findN(N);
}

private static void findN(int N) {
HashMap<Integer, Integer> DPMap = new HashMap<Integer, Integer>();
int temp = 2, i = 1;
DPMap.put(1, 1);
DPMap.put(2, 2);

while (i < N) {
temp++;
if ((temp % 2 == 0 && DPMap.containsKey(temp / 2))
|| (temp % 3 == 0 && DPMap.containsKey(temp / 3))
|| (temp % 5 == 0 && DPMap.containsKey(temp / 5))) {
i++;
DPMap.put(temp, temp);
}
}
System.out.println("The required number = " + temp);
}
}``````

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

But the space is also O(N), can we get rid of the DPMap, but add one more criteria when increasing the count so that: && temp % 7 != 0

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

@PKU.SongChen

Good point. But the problem is, as the value of a number increases, the number of it's prime factors also increases and we may have to keep adding more and more prime numbers to the list of checks that does temp % p != 0(where p is a prime number). Moreover, finding out what all prime numbers are factors of a given number is leading us to the problem of factorization which falls in the complexity class NP.

In order to trade off O(n) space here, the other alternative is to check if the given number has only 2,3 & 5 as factors. This can be done by repeated division of the given number by 2, 3 & 5 until the quotient becomes 1.

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

@Dumbo: i didn't understand this point: why checking whether the quotient exists in the map or not?What is the point when we already know it is divisible, why not simply increment the index?

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

@aka

We are following a DP-like approach where the solutions to subproblems are found before the solution to the given problem. The solutions to subproblems are added to the hashmap as they are computed. So, if the given number is divisible by 2 or 3 or 5, we need to check if the quotient (which is nothing but the product of the remaining factors) is also divisible by 2 or 3 or 5. Hence we are querying the hashmap to see if the quotient(solution to a subproblem) is present. If present, that means the given number is a product of 2(or 3 or 5) and the quotient(which is also a product of multiples of 2, 3 & 5). If the quotient is not present in the hashmap, it means the quotient was not product of multiples of only 2, 3 & 5 and so is not the current number.

As an example, consider the number 14 whose factors are 2 and 7. It is divisible by 2, but the other factor is 7. 7 is not divisible by 2, 3 or 5 and hence will not be present in the hashmap as a solution to a subproblem. Therefore 14 will not be in the sequence.

On the other hand, if you consider 18, it has factors 2 and 9. 9 will be present in the hashmap because it has factors 3 & 3, which again would be present in the hashmap as solutions to subproblems.

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

@Dumbo: Keep up the good work!! Nice explanation, i couldn't have asked for a better explanation than this.

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

@aka

Thanks! Discussions with you are only helping me to become a better learner.

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

He's only asking for Nth number in the sequence. I suppose we can do this by using LCM

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

you can solve this with constant space too by building from 1 -> X
2,3,4,5,
you have to keep 3 pointers(for 2,3,5, multiples) pointing to 3 locations in the list and incrementing every time you use one of them.. the only thing you would need is to do the compare and use the minimum and increment the pointer

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

``````def num(n):
return int(n >= 1) + n / 2 + n / 3 + n / 5 - n / 6 - n / 15 - n / 10 + n / 30

def nth(n):
l = n
r = 2 * n
while num(r) < n:
r = 2 * r
while l < r:
m = (l + r) / 2
c = num(m)
if c == n: return m
if c > n: r = m
else: l = m + 1
return l

print nth(100000000000000)``````

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

@Weizi can u explain the logic?

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

Brilliant.

Here is the explanation:

num(n) returns the "index" of n in the series. For example, 1 => 1, 2 => 2, 3 => 3, 4 => 4, 5 => 5, 6 => 6, 8 => 7, 9 => 8, 10 => 9, 12 => 10 and so on.

Now, to find the "nth" number in the series, we find the smallest r whose index is >= to n. The number we want is clearly going to be <= r. It is also going to be >= n, since the nth number in the series is always >= n.

Once r is found, the algorithm performs a binary search of all numbers between n and r to find the number whose index is equal to n.

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

It is basically dp problem.I thought of following recursion but I cant optimize it further
a[i]=min{a[i-5]*2,3,5;a[i-4]*2,3,5;a[i-3]*2,3,5;a[i-2]*2,3,5;a[i-1]*2,3,5} and that num>a[i]

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

-take array of three elements values{2,3,5}
-take array of three in indices indices{0,0,0}
-create array result[N] to store result;
- take min(values), add to result, check with values and if it is equal to first value in values
then increment first index of indices array and multiply with 2 the result[indices[0]] and store in values[0], same way for 3 and 5, do till Nth number

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

This is the standard problem of Ugly numbers. A good DP solution is given at geeksforgeeks.org/ugly-numbers/

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

@recursive based logic

``````/*
* Following sequence is given:
1,2,3,4,5,6,8,9,10,12,15,16,18,20,24
In this sequence, each number is multiple of 2,3 or 5 only.
This sequence does not contain 7 & 14 as these number has sequence 7 as multiple.
So, if you are given N find the Nth number of this sequence.
* */

public class FindNthNumber {
/**
* @param MultiplList
*            --all has to prime nmbers
* @param Nth
*            number
*/
int curr_size = 0;

public int FindNthNumberfromSequence(int[] MultiplList, int n) {
curr_size = 0;
int[] list = new int[n];
for (int j = 0; j < n; j++)
list[j] = Integer.MAX_VALUE;
getListforPower(MultiplList, n, 1, list, n);
//for (int i = 0; i < n; i++)
//System.out.println(list[i]);
return list[n - 1];
}

private void getListforPower(int[] multiplList, int k, int value,
int[] list, int n) {
if (curr_size >= n && value >= list[n - 1])
return;
int size = (n > curr_size) ? ++curr_size : n;
int v = value;
// System.out.println(v+"<-->"+list[n-1]+ " ,"+size);
for (int j = 0; j < size; j++) {
if (value == list[j])
break;
if (value < list[j]) {
int temp = list[j];
list[j] = v;
v = temp;
}
}
if (k == 0)
return;
for (int j = 0; j < multiplList.length; j++)
getListforPower(multiplList, k - 1, value * multiplList[j], list, n);
}

/**
* @param args
*/
public static void main(String[] args) {
FindNthNumber test = new FindNthNumber();
int listofmultipliers[] = { 2, 3, 8 };
int output = test.FindNthNumberfromSequence(listofmultipliers, 11);
System.out.print(output);

}

}``````

output: 24

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

``````import java.util.*;
public class Nthterm{
public static void main(String args[]){
int ar[]=new int[50];
ar[0]=1;
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
for(int i=1;i<50;i++){
int j=0;
while(j<=ar[i-1] || j%7==0 )	j = queue.poll();
ar[i]=Integer.valueOf(j);
}
System.out.println(Arrays.toString(ar));
}

}``````

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

``````public static void main(String args[]) {
int N =10; // Input N value
int noCnt = 1;
System.out.print(1 + ",");
for(int i=2,twoC = 2, threeC = 2, fiveC = 2,sevenC=2;noCnt<N;i++,twoC++,threeC++,fiveC++,sevenC++)
{

if(twoC  == 2){
twoC = 0;
}
if(threeC  == 3){
threeC = 0;
}
if(fiveC  == 5){
fiveC = 0;
}
if(sevenC == 7){
sevenC = 0;
continue;
}
if(twoC == 0 || threeC == 0 || fiveC == 0){
System.out.print(i + ",");
noCnt++;
}
}
}``````

}

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

``````…
int result=1;
int a=20; //20 is the index number to find
for(int i=1;i<a;i++)
{
if( ((result+1)%2==0) || ((result+1)%3==0) || ((result+1)%5==0) )
result=result+1;
else
result=result+2;

}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

..
..
for(i=2;;i++)
{
if((i%2==0 || i%3==0 || i%5==0))
{
count++;
if(count == n)
return i;
}
}

...

assume here i start from 2 ..
n is the nth term ..
and count is variable set to 0 and incremented as we'll find a number we need.. if count and n are same then return i ...

Comment hidden because of low score. Click to expand.

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.