## Directi Interview Question for Software Developers

Country: India

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

sort the array ..take a minimum priority queue ..insert first m packets and later on add the coming (n-m) packets to the first element of priority queue.

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

We can use Binary Search (Divide & Conquer) for the solution:

``````#include <bits/stdc++.h>
using namespace std;

bool is_possible(int A[], int size, int B, int curr_min) {
int students = 1, sum = 0;

for (int i = 0; i < size; i++) {
if (A[i] > curr_min)
return false;
if (sum + A[i] > curr_min) {
students++;
sum = A[i];
if (students > B)
return false;
}
else
sum = sum + A[i];
}
return true;
}

int toffees(int A[], int size, int B) {
long long sum = 0;

if(size < B)
return -1;

for(int i = 0; i < size; i++)
sum = sum + A[i];

long long start = 0, mid = 0, end = sum;
int result = INT_MAX;

while(start <= end) {
mid = (start + end) / 2;
if (is_possible(A, size, B, mid)) {
result = min(result, (int)mid);
end = mid - 1;
}
else
start = mid + 1;
}
return result;
}

int main() {
int A[] = {12, 34, 67, 90};
int size = sizeof(A) / sizeof(A);
cout << toffees(A, size, 2);
return 0;
}``````

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

a. Sort c1, c2, c3 ... cn, descending order

b. Create array of size [M]

c. Loop over numbers
Store first M numbers in the array. ( first col will have the highest number )

d. int highestColumn = 0 ( since col 0 has the highest value )

e. Loop over columns in the array, from last to first i.e. in ascending order.
This is to ensure the lowest digit is added the next highest number, thus creating the lowest combo.
&&
Loop until c series numbers finish

if ( array[highestColumn] >= array[currentColumn] + c )
else
highestColumn = currentColumn

Print value of array[highestColumn]

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

@deep.kulshreshtha, Can you share bit more insight about your solution, and one more thing, question says that we can only choose consecutive toffee packets then sorting will disturb the order. Isn't it?

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

Number of boxes, M range from [1,N].
When M = 1, only one ordering is possible, i.e all toffee packets in one box => ans will be sum of all toffees -> call this is the upper bound
Similarly, when M = N, again only one ordering is possible, i.e each toffee packet in each of the M boxes => ans will max of the toffees -> call this is the lower bound

So, we can binary search in the range(lower bound to upper bound).
Find mid = (upper-lower)/2
Now, check if mid is possible by putting toffee packets in <= m boxes.
If it is possible, check for a lower half.
Else, check for the higher half.

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

sort the n packets in descending order according to ci.
take a min priority queue and push the first m packets in the queue
now for remaining n-m packet pop out the first element from min priority queue add ci corresponding to current packet,push the result in priority queue.
at last the largest element can be found easily from the queue.

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

``````#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
int T;
cin>>T;
while(T--)
{
int N,M;
cin>>N>>M;
int A[N];
priority_queue<int,vector<int>,greater<int> > Q;
for(int i=0;i<N;i++)
{
cin>>A[i];
}
sort(A,A+N);
int i;
for(i=0;i<M;i++)
Q.push(A[i]);
int temp=N-M;
int index=N-1;
while(temp--)
{
//cout<<Q.top()<<endl;
int data=Q.top()+A[index--];
Q.pop();
Q.push(data);
}
int res;
while(!Q.empty())
{
res=Q.top();
// cout<<Q.top()<<endl;
Q.pop();
}
cout<<res<<endl;
}
return 0;
}``````

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.