NVIDIA Interview Question
Dev LeadsCountry: India
Interview Type: In-Person
#include<stdio.h>
int main()
{
int arr[30],i,j,sum,n,count=0;
printf("enter the no. of input\n");
scanf("%d",&n);
printf("enter the values\n");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
i=0;
j=n-1;
while(i<=j)
{
if(i==j)
{
count++;
break;
}
if(arr[j]==100)
{
count++;
j--;
}
else
{
sum=arr[i]+arr[j];
if(sum>100)
{
count++;
j--;
}
if(sum==100)
{
count++;
i++;
j--;
}
else{
while(sum<100)
{
i++;
sum+=arr[i];
if(sum==100)
{
count++;
i++;
j--;
break;
}
}
count++;
j--;
}
}
}
printf("minimum no. of pipes required are: %d",count);
return 0;
}
#include<stdio.h>
int main()
{
int arr[30],i,j,sum,n,count=0;
printf("enter the no. of input\n");
scanf("%d",&n);
printf("enter the values\n");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
i=0;
j=n-1;
while(i<=j)
{
if(i==j)
{
count++;
break;
}
if(arr[j]==100)
{
count++;
j--;
}
else
{
sum=arr[i]+arr[j];
if(sum>100)
{
count++;
j--;
}
if(sum==100)
{
count++;
i++;
j--;
}
else{
while(sum<100)
{
i++;
sum+=arr[i];
if(sum==100)
{
count++;
i++;
j--;
break;
}
}
count++;
j--;
}
}
}
printf("minimum no. of pipes required are: %d",count);
return 0;
}
#include<stdio.h>
int main()
{
int arr[30],i,j,sum,n,count=0;
printf("enter the no. of input\n");
scanf("%d",&n);
printf("enter the values\n");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
i=0;
j=n-1;
while(i<=j)
{
if(i==j)
{
count++;
break;
}
if(arr[j]==100)
{
count++;
j--;
}
else
{
sum=arr[i]+arr[j];
if(sum>100)
{
count++;
j--;
}
if(sum==100)
{
count++;
i++;
j--;
}
else{
while(sum<100)
{
i++;
sum+=arr[i];
if(sum==100)
{
count++;
i++;
j--;
break;
}
}
count++;
j--;
}
}
}
printf("minimum no. of pipes required are: %d",count);
return 0;
}
int computeCount(int[] jobs){
int minimumNumber=0;
//Sort the array using inbuilt methods because everyone knows the algo
Arrays.sort(jobs);
int i=0,j=jobs.length-1;
int temp = 0;
while(i<j){
boolean isSamePipe = false;
if(!isSamePipe){
temp = jobs[i] + jobs[j];
}else{
temp = temp + jobs[i];
}
if(temp <= 100 ){
isSamePipe = true; // since the combination doesn't exceeded 100 we try adding
i++; // next larger pipe from beginning
}else{
minimumNumber++; //if size of combination increases 100 then adding a pipe
j--; //going to next smaller pipe from end
temp = 0; //resetting the combination size to 0
isSamePipe = false;//For next iteration we have to take a different pipe
}
}
if(j>0) minimumNumber++; // Compensation for the last pipe that is not grater than 100
return minimumNumber;
}
#include<stdio.h>
int main()
{
int n,i,arr[20],temp[20],part=0;
int flag,j,count=0;
printf("\nEnter total no of pipes: ");
scanf("%d",&n);
printf("\nEnter the pine sizes: ");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
//sort arr which holds the pipe size in descending order. I have assumed
sort(arr);
for(i=0;i<n;i++)
{
temp[i]=0;
if(arr[i]<=50 && part)
part=i;
}
printf("\nPartition is %d",part);
for(i=0;i<part;i++)
{
count++;
temp[i]=100-arr[i];
}
printf("\nReached here");
for(i=part;i<n;i++)
{
flag=1;
for(j=0;j<count;j++)
{
if(temp[j]-arr[i]>=0)
{
flag=0;
printf("\nPipe used :%d for pipe of size: %d",temp[j],arr[i]);
temp[j]=temp[j]-arr[i];
break;
}
}
if(flag)
{
temp[count]=100-arr[i];
count++;
}
}
printf("\nCount=%d",count);
return 0;
}
#define MAX_SIZE 100
int minPipes(int a[], int numPipes)
{
int sum = 0;
int i;
int maxPipe;
int rem;
//calculate total lenght of required pipe
for(i=0; i<numPipes; i++)
{
sum += a[i];
}
maxPipe = sum/MAX_SIZE; //Maximum required pipe can be obtained by dividing total lenght with standard pipe length
rem = sum/MAX_SIZE; //see if still some length is not addressed, i.e. total lenght is not a multiple of standard length
//if still there is remaining lenght, we need one more standard pipe
if(rem != 0)
{
maxPipe = maxPipe + 1;
}
return maxPipe;
}
int main()
{
int a[] = {20, 30, 50, 60, 80}; //{10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80}; //{20, 30, 50, 60, 80};
int n = sizeof(a)/sizeof(a[0]);
printf("Minimum required pipes = %d\n", minPipes(a, n));
return 0;
}
int minPipes(int a[], int numPipes)
{
int sum = 0;
int i;
int maxPipe;
int rem;
//calculate total lenght of required pipe
for(i=0; i<numPipes; i++)
{
sum += a[i];
}
maxPipe = sum/MAX_SIZE; //Maximum required pipe can be obtained by dividing total lenght with standard pipe length
rem = sum/MAX_SIZE; //see if still some length is not addressed, i.e. total lenght is not a multiple of standard length
//if still there is remaining lenght, we need one more standard pipe
if(rem != 0)
{
maxPipe = maxPipe + 1;
}
return maxPipe;
}
int main()
{
int a[] = {20, 30, 50, 60, 80}; //{10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80}; //{20, 30, 50, 60, 80};
int n = sizeof(a)/sizeof(a[0]);
printf("Minimum required pipes = %d\n", minPipes(a, n));
return 0;
}
int minPipes(int a[], int numPipes)
{
int sum = 0;
int i;
int maxPipe;
int rem;
//calculate total lenght of required pipe
for(i=0; i<numPipes; i++)
{
sum += a[i];
}
maxPipe = sum/MAX_SIZE; //Maximum required pipe can be obtained by dividing total lenght with standard pipe length
rem = sum/MAX_SIZE; //see if still some length is not addressed, i.e. total lenght is not a multiple of standard length
//if still there is remaining lenght, we need one more standard pipe
if(rem != 0)
{
maxPipe = maxPipe + 1;
}
return maxPipe;
}
int main()
{
int a[] = {20, 30, 50, 60, 80}; //{10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80}; //{20, 30, 50, 60, 80};
int n = sizeof(a)/sizeof(a[0]);
printf("Minimum required pipes = %d\n", minPipes(a, n));
return 0;
}
#define MAX_SIZE 100
int minPipes(int a[], int numPipes)
{
int sum = 0;
int i;
int maxPipe;
int rem;
//calculate total lenght of required pipe
for(i=0; i<numPipes; i++)
{
sum += a[i];
}
maxPipe = sum/MAX_SIZE; //Maximum required pipe can be obtained by dividing total lenght with standard pipe length
rem = sum/MAX_SIZE; //see if still some length is not addressed, i.e. total lenght is not a multiple of standard length
//if still there is remaining lenght, we need one more standard pipe
if(rem != 0)
{
maxPipe = maxPipe + 1;
}
return maxPipe;
}
int main()
{
int a[] = {20, 30, 50, 60, 80};
int n = sizeof(a)/sizeof(a[0]);
printf("Minimum required pipes = %d\n", minPipes(a, n));
return 0;
}
def minimum_pipes(l):
sorted_list = sorted(l)
min_pipes = 0
i = 0
j = len(sorted_list) - 1
while i <= j:
if i == j:
min_pipes += 1
break
if sorted_list[j] == 100:
min_pipes += 1
j -= 1
elif sorted_list[j] < 100:
temp = sorted_list[i] + sorted_list[j]
if temp < 100:
while temp <= 100:
temp += sorted_list[i]
i += 1
min_pipes += 1
j -= 1
elif temp > 100:
min_pipes += 1
j -= 1
elif temp == 100:
min_pipes += 1
j -= 1
i += 1
return min_pipes
>>> import minimum_pipes from minimum_pipes
>>> print minimum_pipes([10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80])
6
>>> print minimum_pipes([10] * 10)
1
>>>
def minimum_pipes(l):
sorted_list = sorted(l)
min_pipes = 0
i = 0
j = len(sorted_list) - 1
while i <= j:
if i == j:
min_pipes += 1
break
if sorted_list[j] == 100:
min_pipes += 1
j -= 1
elif sorted_list[j] < 100:
temp = sorted_list[i] + sorted_list[j]
if temp < 100:
while temp <= 100:
temp += sorted_list[i]
i += 1
min_pipes += 1
j -= 1
elif temp > 100:
min_pipes += 1
j -= 1
elif temp == 100:
min_pipes += 1
j -= 1
i += 1
print min_pipes
minimum_pipes([10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80])
minimum_pipes([60, 90, 50] * 10)
def minimum_pipes(l):
sorted_list = sorted(l)
min_pipes = 0
i = 0
j = len(sorted_list) - 1
while i <= j:
if i == j:
min_pipes += 1
break
if sorted_list[j] == 100:
min_pipes += 1
j -= 1
elif sorted_list[j] < 100:
temp = sorted_list[i] + sorted_list[j]
if temp < 100:
while temp <= 100:
temp += sorted_list[i]
i += 1
min_pipes += 1
j -= 1
elif temp > 100:
min_pipes += 1
j -= 1
elif temp == 100:
min_pipes += 1
j -= 1
i += 1
print min_pipes
minimum_pipes([10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80])
minimum_pipes([60, 90, 50] * 10)
#include <stdio.h>
#include <stdlib.h>
#define SIZE ( 100 )
#define PARENT(i) ( (i-1) / 2 )
#define LEFT_CHILD(i) ( 2*i + 1 )
#define RIGHT_CHILD(i) ( 2*i + 2 )
#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
#define ROD_SIZE (30)
typedef struct heap {
int ary[SIZE];
unsigned int index;
} heap_t;
typedef unsigned char bool;
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
bool insert (heap_t* h, int val )
{
int i;
if(h == NULL)
{
return 0;
}
i = h->index;
if( i == SIZE-1 )
{
return 0; // heap full
}
h->ary[h->index++] = val;
while( ( PARENT(i) >= 0 ) && ( h->ary[i] > h->ary[PARENT(i)] ))
{
swap( &(h->ary[i]), &(h->ary[PARENT(i)]) );
i = PARENT(i);
}
return 1;
}
bool remove_head (heap_t* h, int* val )
{
int i = 0;
if(h == NULL)
{
return 0;
}
if( h->index == 0 )
{
return 0; //empty heap
}
*val = h->ary[0];
h->ary[i] = h->ary[--(h->index)];
while((( LEFT_CHILD(i) < h->index ) && ( h->ary[i] < h->ary[LEFT_CHILD(i)]) ) ||
(( RIGHT_CHILD(i) < h->index ) && ( h->ary[i] < h->ary[RIGHT_CHILD(i)] )))
{
if ( ( RIGHT_CHILD(i) < h->index ) && (h->ary[RIGHT_CHILD(i)] > h->ary[LEFT_CHILD(i)] ))
{
swap( &(h->ary[i]), &(h->ary[RIGHT_CHILD(i)]) );
i = RIGHT_CHILD(i);
}
else
{
swap( &(h->ary[i]), &(h->ary[LEFT_CHILD(i)]) );
i = LEFT_CHILD(i);
}
}
return 1;
}
heap_t* init_heap( void )
{
heap_t* h = (heap_t*) malloc(sizeof(heap_t));
h->index = 0;
return h;
}
int read_max (heap_t* h)
{
if(h->index > 0)
{
return (h->ary[0]);
}
else
{
return 0;
}
}
void print_heap(heap_t* h)
{
int lvl = 1;
for(int i = 0; i < h->index; i++)
{
if ( i > ((1 << lvl) - 2) )
{
lvl++;
printf("\n");
}
printf("%d ", h->ary[i]);
}
}
void sort_ary(int* ary, unsigned int size)
{
int i, val;
heap_t* h = init_heap();
for(i = 0; i < size; i++)
{
insert(h, ary[i]);
}
i = 0;
while(remove_head(h, &val) != 0)
{
ary[i++] = val;
}
free(h);
}
void print_ary(int * a, unsigned int size)
{
for(int i = 0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main( void )
{
int a[15] = {2, 5, 12,15, 22, 10,8, 30,5,12,15,22,10,8,30};
int i, total_rods, cur_rod_size;
heap_t* left_overs = init_heap();
print_ary(a, ARRAY_SIZE(a));
sort_ary(a, ARRAY_SIZE(a));
print_ary(a, ARRAY_SIZE(a));
total_rods = 0;
for(i = 0; i < ARRAY_SIZE(a); i++)
{
if(a[i] <= read_max(left_overs))
{
remove_head(left_overs, &cur_rod_size);
cur_rod_size -= a[i];
if(cur_rod_size > 0)
{
insert(left_overs, cur_rod_size);
}
}
else
{
total_rods++;
cur_rod_size = ROD_SIZE - a[i];
if(cur_rod_size > 0)
{
insert(left_overs, cur_rod_size);
}
}
printf("\nLeft overs at step %d\n", i);
print_heap(left_overs);
}
printf("Total rods required:%d\n", total_rods);
printf("Left overs\n");
print_heap(left_overs);
return 0;
}
assume the input already sorted from small to big. or we can do a sort.
int main()
{
int num;
cin>> num;
int* values = new int[num];
for(int i = 0; i< num; i++) {
cin>>values[i];
cout << values[i];
}
int count = 0;
int target = 100;
for (int j=num-1, k=0; j>=k;j--)
{
int add = values[j];
for(;k<j;)
{
if(add + values[k] > target)
{
;
break;
}else
{
add += values[k];
k++;
}
}
count++;
}
cout << count <<endl;
return 0;
}
int main()
{
int num;
cin>> num;
int* values = new int[num];
for(int i = 0; i< num; i++) {
cin>>values[i];
}
int count = 0;
int target = 100;
for (int j=num-1, k=0; j>=k;j--)
{
int add = values[j];
for(;k<j;)
{
if(add + values[k] > target)
{
break;
}else {
add += values[k];
k++;
}
}
count++;
}
<< count <<endl;
return 0;
}
We can solve it using Greedy Algorithm.
import java.util.*;
public class Solution{
public static void main(String[] args){
Solution sol = new Solution();
int[] arr = {10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80};
int[] arr1 = {10, 15, 20, 25, 65, 5, 4, 23, 17, 85, 69, 32, 14, 15, 56, 58, 57, 96, 100};
int ret = sol.minPip(arr1);
System.out.println(ret);
}
public int minPip(int[] arr){
Arrays.sort(arr);
int ret = 0;
for(int i = arr.length-1; i >= 0; i--){
if(arr[i] < 0){
continue;
}
ret ++;
int tmp = arr[i];
arr[i] = -1;
for(int j = i-1; j >= 0; j--){
if(arr[j] < 0){
continue;
} else {
if(tmp + arr[j] > 100){
continue;
} else{
tmp += arr[j];
arr[j] = -1;
}
}
}
}
return ret;
}
}
// ConsoleApplication2.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream"
#include <vector>
using namespace std;
int minPipe(std::vector<int> input, int max)
{
if (input.size() == 1)
{
return 1;
}
int maxTemp = max;
std::vector<int>::iterator startPos = input.begin();
std::vector<int>::iterator endPos = (input.end())-1;
int num = input.size();
while (*startPos < *endPos)
{
if (*endPos + *(endPos-1) < maxTemp)
{
maxTemp -= *endPos;
--endPos;
--num;
}
else if (*endPos + *startPos < maxTemp)
{
maxTemp -= *startPos;
++startPos;
--num;
}
else
{
maxTemp = max;
--endPos;
}
}
return num;
}
int main()
{
std::vector<int> input = {10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80};
int max = 100;
cout << "Minimum number of pipes needed is" << minPipe(input, max);
getchar();
return 0;
}
// ConsoleApplication2.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream"
#include <vector>
using namespace std;
int minPipe(std::vector<int> input, int max)
{
if (input.size() == 1)
{
return 1;
}
int maxTemp = max;
std::vector<int>::iterator startPos = input.begin();
std::vector<int>::iterator endPos = (input.end())-1;
int num = input.size();
while (*startPos < *endPos)
{
if (*endPos + *(endPos-1) < maxTemp)
{
maxTemp -= *endPos;
--endPos;
--num;
}
else if (*endPos + *startPos < maxTemp)
{
maxTemp -= *startPos;
++startPos;
--num;
}
else
{
maxTemp = max;
--endPos;
}
}
return num;
}
int main()
{
std::vector<int> input = {10, 10, 10, 15, 20, 35, 55, 60, 70, 75, 75, 80};
int max = 100;
cout << "Minimum number of pipes needed is" << minPipe(input, max);
getchar();
return 0;
}
O(nlogn) implementation using map.
It is based on Bin Packing First Fit heuristic, just using the map to speed up the finding of an available bin (with enough space to fit the new item)
int firstFitOpt(vector<int>& items, int capacity)
{
int n = items.size();
map<int, int> binCapacity;
int res = 0;
for (int i = 0; i < n; ++i)
{
auto it = binCapacity.lower_bound(items[i]);
int residual = capacity;
if (it != binCapacity.end())
{
residual = it->first;
it->second--;
if (it->second == 0)
binCapacity.erase(it);
}
else
{
++res;
}
residual -= items[i];
if (residual > 0)
binCapacity[residual]++;
}
return res;
}
int main() {
vector<int> items;
int c = 10;
for (int i = 0; i < 50000; ++i)
items.push_back(rand() % 10 + 1);
std::cout << "Opt: " << firstFitOpt(items, c) << std::endl;
}
private static int getMaxPipeRequired(int[] sizes){
int totalPipes = 0;
double totalLength = 0;
for(int size : sizes){
totalLength += size;
}
totalPipes = (int) Math.ceil(totalLength/100);
return totalPipes;
}
#include<stdio.h>
int main()
{
int arr[30],i,j,sum,n,count=0;
printf("enter the no. of input\n");
scanf("%d",&n);
printf("enter the values\n");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
i=0;
j=n-1;
while(i<=j)
{
if(i==j)
{
count++;
break;
}
if(arr[j]==100)
{
count++;
j--;
}
else
{
sum=arr[i]+arr[j];
if(sum>100)
{
count++;
j--;
}
if(sum==100)
{
count++;
i++;
j--;
}
else{
while(sum<100)
{
i++;
sum+=arr[i];
if(sum==100)
{
count++;
i++;
j--;
break;
}
}
count++;
j--;
}
}
}
printf("minimum no. of pipes required are: %d",count);
return 0;
}
Hello. Did you look at Bin Packing Problem? I think the best answer is to use branch and bound method or implement some kind of heuristic or probabilistic algorithm.
- Serge Aktanorovich October 27, 2015