## NVIDIA Interview Question for Dev Leads

Country: India
Interview Type: In-Person

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

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.

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

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

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

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

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

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

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

# of pipes * 100 gives us the upper bound on the total length.
We start a binary divide-and-conquer method where we check if # of pipes / 2 *10 if feasible. Checking feasibility should be easy.

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

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

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

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

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

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

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

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

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

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

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

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

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

``````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
>>>``````

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

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)

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

``````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)``````

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

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

{
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;
{
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++)
{
{
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;
}``````

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

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--)
{
for(;k<j;)
{
{
;
break;
}else
{
k++;
}
}
count++;
}
cout << count <<endl;

return 0;
}

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

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--)
{
for(;k<j;)
{
{
break;
}else {
k++;
}
}
count++;
}
<< count <<endl;

return 0;
}

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

simple python code:

def Pipes(array,n):
sum1=sum(array)
count=sum1/100
count2=sum1%100
if count2>0:
count+=1

return count

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

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

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

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

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

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

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

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

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

private static int getMaxPipeRequired(int[] sizes){
int totalPipes = 0;

double totalLength = 0;
for(int size : sizes){
totalLength += size;
}

totalPipes = (int) Math.ceil(totalLength/100);

}

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

private static int getMaxPipeRequired(int[] sizes){
int totalPipes = 0;

double totalLength = 0;
for(int size : sizes){
totalLength += size;
}

totalPipes = (int) Math.ceil(totalLength/100);

}

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

what if input is 60,90,50

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

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

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.

### 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.

### 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.