## Directi Interview Question for Senior Software Development Engineers

Country: India
Interview Type: Phone Interview

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

Calculate sum[i]=sum of K consecutive numbers ending at index i
dp[i,j] = max sum possible in [1...i] and j number of sub arrays;
dp[i,j]=max(dp[i-1,j],dp[i-k,j-1]+sum[i])
You have two options, either to include the subarray ending at index i or not to include it.
Complexity O(NK)

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

It looks to me like a DP problem. Here is my solution.
1> First create sum array, which at each index contains sum of all elements from 'index' to 'index + K' in the given array.
2> Now a recursive function can be written such that it returns sum of max M sub arrays starting from given index. This function iterates over all the overlapping sub arrays starting from index to 'index + K' and recursively calls this function with new non overlapping index and M-1 in each iteration.
3> Use 2D array to store intermediate results that this function returns.

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

Code looks like this. I have not handled corner conditions

``````maxSum(index, M){
if(dp[index][M] != null)  //Check if we have already calculated it
return dp[index][M];

maxSum = 0;
for(i in index to index+K){
thisMaxSum = sumArray[i] + maxSum(i+K, M-1);
maxSum = thisMaxSum>maxSum ? thisMaxSum : maxSum;
}

dp[index][M] = maxSum; // Store the intermediate result

return maxSum;
}``````

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

Can you clarify this question? Isn't it just a matter of finding the MxK largest numbers in the array?

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

1. it should be subarray , not subsequence of numbers
2. it should be non-overlapping subarray
3. We have to return sum of largest M such subsets..

i didn't get your M * K largest numbers part, what it is ?

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

To find M subarrays with K elements each to maximize sum(M), you can pick the M*K largest numbers of the array and divide them into M subarrays. The total sum will be the largest possible.

For this, sort the array in descending order and pick the first M*K numbers.

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

@Victor: the arrays must be contiguous.

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

``````import java.util.*;
public class solution4DP {
public static int maxSum(int[] num, int m, int k){
int sum=0;
List<Integer> sums = new ArrayList<Integer>();
int sum1=0;
for(int i=0; i<k; i++){
sum1+=num[i];
}
for(int i=k; i<num.length; i++){
int sum2 = sum1-num[i-k]+num[i];
sum1 = sum2;
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> li = new ArrayList<Integer>();
rec(sums, 0, li, result, m, k);
int sum2=0;
for(int i=0; i<result.size(); i++){
List<Integer> l= result.get(i);
for(int j=0; j<l.size(); j++){
sum2+=l.get(j);
}
sum = Math.max(sum2, sum);
sum2=0;
}
return sum;
}
public static void rec(List<Integer> sums, int n, List<Integer> l, List<List<Integer>> result, int m, int k){
if(l.size()==m){
return;
}
if(n>sums.size()) return;
for(int i=0; i<k; i++){
if(n+i<sums.size()){
List<Integer> lNew = new ArrayList<Integer>(l);
rec(sums, n+i+k, lNew, result, m, k);
}else break;
}
rec(sums, n+k, l, result, m, k);
return;
}
public static void main(String[] args){
int[] num = {3,2,100,1};
int m=2; int k=2;
System.out.println(maxSum(num, m, k));
}
}``````

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

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

Here is my solution in c

#include<bits/stdc++.h>
#define ll long long int
#define sd1(a) scanf("%d",&a)
#define sd2(a,b) scanf("%d %d",&a,&b)
#define sd3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define slld1(a) scanf("%lld",&a)
#define slld2(a,b) scanf("%lld %lld",&a,&b)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loope(i,a,b) for(int i=a;i<=b;i++)
#define loopd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int main()
{
int n,m,k,i,j;
sd3(n,m,k);
int a[n];
int dp[n][k];
int sum[n];
for(i=0;i<n;i++)
sd1(a[i]);
int s=0;
for(i=0;i<k-1;i++)
{
sum[i]=0;
s+=a[i];
}
sum[i]=s+a[k-1];
for(i=k;i<n;i++)
{
sum[i]=sum[i-1]-a[i-k]+a[i];
}
/*for(i=0;i<n;i++)
printf("%d ",sum[i]);
cout<<endl;*/
for(i=0;i<n;i++)
{
for(j=0;j<k;j++)
{
if(i==0 || j==0 || i<(j*k-1))
dp[i][j]=0;
else
dp[i][j]=max(dp[i-1][j],dp[i-(k-1)][j-1]+sum[i]);
printf("%d ",dp[i][j]);
}
//cout<<endl;
}
printf("%d\n",dp[n-1][k-1]);
}

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

#include<bits/stdc++.h>
#define ll long long int
#define sd1(a) scanf("%d",&a)
#define sd2(a,b) scanf("%d %d",&a,&b)
#define sd3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define slld1(a) scanf("%lld",&a)
#define slld2(a,b) scanf("%lld %lld",&a,&b)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loope(i,a,b) for(int i=a;i<=b;i++)
#define loopd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int main()
{
int n,m,k,i,j;
sd3(n,m,k);
int a[n];
int dp[n][k];
int sum[n];
for(i=0;i<n;i++)
sd1(a[i]);
int s=0;
for(i=0;i<k-1;i++)
{
sum[i]=0;
s+=a[i];
}
sum[i]=s+a[k-1];
for(i=k;i<n;i++)
{
sum[i]=sum[i-1]-a[i-k]+a[i];
}
/*for(i=0;i<n;i++)
printf("%d ",sum[i]);
cout<<endl;*/
for(i=0;i<n;i++)
{
for(j=0;j<k;j++)
{
if(i==0 || j==0 || i<(j*k-1))
dp[i][j]=0;
else
dp[i][j]=max(dp[i-1][j],dp[i-(k-1)][j-1]+sum[i]);
printf("%d ",dp[i][j]);
}
//cout<<endl;
}
printf("%d\n",dp[n-1][k-1]);
}

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

we can do using max-heap of size "m" and iteration over elements and considering what would be sum upto this index "i" if sub-array of size "k" is considered this can be done in O(n) and adding this sum to max-heap our final answer will be sum of all elements of max-Heap

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

we can do using max-heap of size "m" and iteration over elements and considering what would be sum upto this index "i" if sub-array of size "k" is considered this can be done in O(n) and adding this sum to max-heap our final answer will be sum of all elements of max-Heap

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

This should work fine, If you find something wrong with this please let me know.

``````import java.util.*;
import java.lang.*;

public class solution{
public static void main (String args[]){
Scanner sc=new Scanner(System.in);
int n,m,k;
n=sc.nextInt();
m=sc.nextInt();
k=sc.nextInt();

int arr[]=new int[n];
for (int i=0;i<n ;i++ ) {
arr[i]=sc.nextInt();
}
int subm[]=new int[n/k];
int l;
for(l=0;l<n/k;l++){
subm[l]=0;
}
l=0;
for(int i=0;i<=n-k;i=i+k){

for(int j=i;j<i+k;j++){
subm[l]=subm[l]+arr[j];
}
l++;
}
System.out.println("OUTPUT");
for(l=0;l<n/k;l++){
System.out.println(subm[l]);
}
int ans=0;
for(int i=0;i<m;i++){
ans=ans+max(subm);
subm[Arrays.binarySearch(subm,max(subm))]=0;
}

System.out.println("ANS="+ans);

}
public static int max(int a[]){
int m;
m=a[0];
for (int i=1;i<a.length ;i++ ) {
if(a[i]>m){
m=a[i];
}
}
return m;
}

}``````

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

``````import java.util.*;
import java.lang.*;

public class solution{
public static void main (String args[]){
Scanner sc=new Scanner(System.in);
int n,m,k;
n=sc.nextInt();
m=sc.nextInt();
k=sc.nextInt();

int arr[]=new int[n];
for (int i=0;i<n ;i++ ) {
arr[i]=sc.nextInt();
}
int subm[]=new int[n/k];
int l;
for(l=0;l<n/k;l++){
subm[l]=0;
}
l=0;
for(int i=0;i<=n-k;i=i+k){

for(int j=i;j<i+k;j++){
subm[l]=subm[l]+arr[j];
}
l++;
}
System.out.println("OUTPUT");
for(l=0;l<n/k;l++){
System.out.println(subm[l]);
}
int ans=0;
for(int i=0;i<m;i++){
ans=ans+max(subm);
subm[Arrays.binarySearch(subm,max(subm))]=0;
}

System.out.println("ANS="+ans);

}
public static int max(int a[]){
int m;
m=a[0];
for (int i=1;i<a.length ;i++ ) {
if(a[i]>m){
m=a[i];
}
}
return m;
}

}``````

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

A very basic recursion approach is used here.

``````#include<bits/stdc++.h>

using namespace std;

int solve(int presum[],int m,int sz,int k,int start){

if(m==0)
return 0;

if(start>sz-1)
return 0;

int mx =0;

//if you are including subarray of size k
int	tmpmax = presum[start]+solve(presum,m-1,sz,k,start+k);

//if you are excluding the element  and seaching in all next possible subarrays
int tp = solve(presum,m,sz,k,start+1);

//return the max
return max(tmpmax,tp);
}

int main(){

int n;

cin>>n;
int arr[n];

for(int i=0;i<n;i++){

cin>>arr[i];

}

int m,k;

cin>>m>>k;

int presum[n+1-k]={0};
//store the sum of array from index i to index i+k in presum array at index i of it.
for(int i=0;i<=n-k;i++){

for(int j=i;j<i+k;j++){

presum[i]+=arr[j];
}
}

//the resulting presum array will have a size = n+1-k
int ans = solve(presum,m,n+1-k,k,0);
cout<<ans;
return 0;
}``````

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

``````#include<bits/stdc++.h>

using namespace std;

int solve(int presum[],int m,int sz,int k,int start){

if(m==0)
return 0;

if(start>sz-1)
return 0;

int mx =0;

//if you are including subarray of size k
int	tmpmax = presum[start]+solve(presum,m-1,sz,k,start+k);

//if you are excluding the element  and seaching in all next possible subarrays
int tp = solve(presum,m,sz,k,start+1);

//return the max
return max(tmpmax,tp);
}

int main(){

int n;

cin>>n;
int arr[n];

for(int i=0;i<n;i++){

cin>>arr[i];

}

int m,k;

cin>>m>>k;

int presum[n+1-k]={0};
//store the sum of array from index i to index i+k in presum array at index i of it.
for(int i=0;i<=n-k;i++){

for(int j=i;j<i+k;j++){

presum[i]+=arr[j];
}
}

//the resulting presum array will have a size = n+1-k
int ans = solve(presum,m,n+1-k,k,0);
cout<<ans;
return 0;
}``````

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

sort the array in descending order
then form the M sub arrays of K elements each
then find the sum of M sub arrays.(i.e first M*k elements)

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.