## Flipkart Interview Question for SDE-2s

• 0

Country: India
Interview Type: In-Person

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

dynamic programming
f[i] = min (f[j -1] + 1, f[i])

``````public int numsOfWays (String s ){
long [] f = new long [s.length() + 1] ;
f = 0;
for (int i = 1 ; i <= s.length() ;++i) {
f[i] = Integer.MAX_VALUE;
for (int j = 1 ; j <= i ;++j) {
if (s.charAt(j - 1) == '0'){
continue ;
}
int num = Integer.parseInt(s.substring(j - 1, i), 2) ;
if (isPower(num)) {
f[i] = Math.min(f[i], f[j - 1] + 1) ;
}
}
}
return f[s.length()] == Integer.MAX_VALUE ? -1 : (int)f[s.length()] ;
}

private boolean isPower (long val){
if (val == 0) {
return false ;
}
int n = (int)(Math.log(val) / Math.log(5));
return Math.pow(5, n) == val;
}``````

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

Nice solution.
To improve the performance we can traverse the inner loop in reverse order i.e.

``for(int j=i;j>=1;--j)``

and get the value of the current segment incrementally.

But integer overflows may still happen.

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

Nice solution.
To improve the performance we can traverse the inner loop in reverse order i.e.

``for(int j=i;j>=1;--j)``

and get the value of the current segment incrementally.

But integer overflows may still happen.

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

Nice solution but in the return statement we can skip doing the typecast to int. f[s.length()] would always lie in the range of int.

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

@Scott
I agree with the thought. You may need to check f[j-1] before taking it into account, what if f[j-1] is Integer.MAX_VALUE.
Code in python:

``````import math

def sliceIntoMultiplesOf5(s):
def isPowerOf5(s):
x = int(s, 2)
n = int(math.log2(x) / math.log2(5))
return 5 ** n == x

# initialize
n = len(s)
f = [-1] * n
# dp
for i in range(n):
if isPowerOf5(s[:i+1]):
f[i] = 1
continue
for j in range(i):
if f[j] == -1 or s[j+1] == '0' or not isPowerOf5(s[j+1:i+1]):
continue
if f[i] == -1:
f[i] = f[j] + 1
else:
f[i] = min(f[i], f[j] + 1)
# result
return f[n-1]

# test case
strList = [
"101101101",
"1111101",
"110011011",
"1000101011",
"111011100110101100101110111"
]

for s in strList:
print(sliceIntoMultiplesOf5(s))``````

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

``````'''
The following code takes a binary number as input and prints the number
of chunks in the number which are divisible by 5.
'''
import sys
import math

def validateInput(inputStream):
isValid = True;
for x in inputStream:
if x != '0' and x != '1':
isValid = False;
break;
return isValid;

'''
For divisibility by 5, the number must end in 1010 or 101.
'''
def processInput(inputStream):
chunk = '';
chunksDivisibleBy5 = 0;
for x in inputStream:
chunk += x;
decimal = convertBinaryToDecimal(chunk);
if decimal is not None and decimal%5 == 0:
chunksDivisibleBy5 += 1;
chunk = '';
return chunksDivisibleBy5;

'''
Converts a binary number to its decimal counterpart.
'''
def convertBinaryToDecimal(inputStream):
length = len(inputStream);
decimal = 0;
for x in inputStream:
decimal += length * math.pow(int(x), length - 1);
return decimal;

def main():
input = sys.argv;
inputStream = list(input);
if (validateInput(inputStream)):
print 'Valid input';
chunksDivisibleBy5 = processInput(inputStream);
print chunksDivisibleBy5 if chunksDivisibleBy5 != 0 else -1;
else:
print 'Invalid input. The input should contain only 0s and 1s.';

if __name__ == '__main__':
main()``````

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

It is not that it should be divisible it should be a power of 5.

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

1) Consider int start = 0, curr = 0;
2) Traverse from left to right one letter at a time and and increment curr++ accordingly.
3) Validate whether the number formed from start to curr index is in power of 5 or not. If it is then increment k and also update start variable to curr+1 (start=curr+1)

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

Wow this seems to be an intimidating problem at first but if you think about it you just need to split once a power of five is found then look for another sets after that chunk and used memoization to recall when you already processed a previous chunk.

I used a hash set to know if a number is a power of 5.

I think there are better solutions but this is what I would came up with at the moment.

``````public int FindSplitsOfPowerOfFive(string S)
{

return CoreFindSplits(S, 0, S.Length, new Dictionary<string, int>());
}

private int CoreFindSplits(string S, int start, int end, Dictionary<string, int> memo)
{
string hash = start + "," + end;

if(memo.ContainsKey(hash))
{
return memo[hash];
}

var sorted = SortedDictionary<int, int>()

// Find all Powers of Five while parsing
long current = 0;
int min = -2;

for(int i = start, i < S.Length; i++)
{
current <<= 1;
current += S[i] =='1'?1:0;

if(IsPowerOfFive(current))
{
int sub = CoreFindSplits(S, i+1, end, memo);

if(sub != -1 && sub < min)
{
min = sub + 1;
}
}
}

return min;
}

private bool IsPowerOfFive(long number)
{
// Precalculated all powers of five for efficient lookup
const HashSet<long> powersOfFive = new HashSet<long>
{
5,
25,
125,
625,
3125,
15625,
78125,
390625,
1953125,
9765625,
48828125,
244140625,
1220703125,
6103515625,
30517578125,
152587890625,
762939453125,
3814697265625,
19073486328125,
95367431640625,
476837158203125,
2384185791015625,
11920928955078125,
59604644775390625,
298023223876953125,
1490116119384765625,
7450580596923828125
};

return powersOfFive.Contains(number);
}``````

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

is there a cpp solution for this problem

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

``````#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long int
#define llu unsigned long long int
#define I int
#define S string
#define D double
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define in(n) scanf("%lld",&n)
#define in2(a,b) scanf("%lld %lld",&a,&b)
#define in3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define out(a) printf("%lld\n",a)
#define inu(a) scanf("%lld",&a)
#define outu(a) printf("%llu",a)
#define outf(a) printf("%.9f\n", a);
#define mod 1000000007
#define inf 100000000000000
#define MM(a,x)  memset(a,x,sizeof(a));
#define ALL(x)   (x).begin(), (x).end()
#define UN(v)    sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())
#define fill(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define PB push_back
#define f first
#define s second
#define sz(v) v.size()
#define nl cout<<"\n"
#define MX1 100005
#define MX2 1000005
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
typedef pair<ll,ll>  pll;
typedef vector<ll>     vll;
typedef vector<llu>    vllu;
typedef vector<string>  vs;
typedef vector<pll>     vpll;

bool check(int i , string s , int k){
ll ans = 0;
for(int j = k ; j >= i ; j--)
ans = ans + ((s[j] - '0') * pow(2,k - j));

while(ans > 0){
if(ans % 5 == 0)
ans/=5;
else if(ans != 1)
return(false);
if(ans == 1)
return(true);
}
}

int main(){
fast;
// freopen("A-large-practice.in","r",stdin);
// freopen("output_file_name.out","w",stdout);
S s;
cin >> s;
ll k = sz(s)-1;
int i;
int count = 0;
while(k >= 0){
for(i = 0 ; i <= k ; i++){
bool  p = check(i,s,k);
if(p){
count++;
k = --i;
break;
}
}
if(k < 0)
break;
}
cout << count << endl;``````

}

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.