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.
answer=dp[n,k]
Complexity O(NK)

- prateekjjw001 June 08, 2015 | Flag Reply
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.

- Murthi February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Murthi February 02, 2015 | Flag
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?

- Victor January 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- saurabh January 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Victor January 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Victor: the arrays must be contiguous.

- Anonymous January 23, 2015 | Flag
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];
		}
		sums.add(sum1);
		for(int i=k; i<num.length; i++){
			int sum2 = sum1-num[i-k]+num[i];
			sums.add(sum2);
			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){
			result.add(l);
			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);
				lNew.add(sums.get(n+i));
				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));
	}
}

- Anonymous January 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please write your logic?

- saurabh January 22, 2015 | Flag
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]);
}

- Shuvam Bosana August 21, 2015 | Flag Reply
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]);
}

- Shuvam Bosana August 21, 2015 | Flag Reply
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

- Anonymous June 07, 2017 | Flag Reply
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

- SSwarnkar13 June 07, 2017 | Flag Reply
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;
             }

  }

- Ishan Khan August 08, 2017 | Flag Reply
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;
             }

  }

- Ishan Khan August 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Read the code comments to understand it.
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;
}

- Kunwar desh deepak March 25, 2018 | Flag Reply
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;
}

- kddeepaksingh March 25, 2018 | Flag Reply
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)

- Anonymous January 22, 2015 | Flag Reply


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