## Flipkart Interview Question for SDE-2s

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] = 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
of 0 votes

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
of 0 votes

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
of 0 votes

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):
# pieces do not start with 0
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[1];
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
of 0 votes

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;
}
}
}

memo.Add(hash, min);

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;``````

}

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