Directi Interview Question
Software DevelopersCountry: India
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[0]);
cout << toffees(A, size, 2);
return 0;
}
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 )
Add c in current column
else
Add c in current column
highestColumn = currentColumn
Print value of array[highestColumn]
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.
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.
#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;
}
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.
- mohit ojha July 06, 2017