## Google Interview Question for Software Engineers

• 9

Country: United States

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

Algorithm is to sort the array (ascending) and walk indexes toward the middle, comparing the sum of the values at the two indexes with the max weight of the canoes (150). If the summed weight is less than 150, increment boat counter and move both indexes closer to middle of array. If summed weight is higher than 150, only increment boat counter if heaver child is less than max weight, then only move higher index toward center (decrement). The reasoning here is that we'll try to pair the lighter child with the next heaviest child on the list, so we want to leave the low index pointer where it is and then go to the next iteration.

I tried a few test cases and it seems to be working as expected.

Complexity would be O(nlogn) due to the sort at the beginning.

``````private static int GetMaxBoats(List<int> arr)
{
arr.Sort();
/*foreach (int n in arr)
{
Console.WriteLine(n);
}*/

int lowIndex = 0;
int highIndex = arr.Count - 1;
int boatCounter = 0;

while(lowIndex < highIndex)
{
if(arr[lowIndex] + arr[highIndex] <= 150)
{
//2 kids fit
boatCounter++;
lowIndex++;
highIndex--;
}
else
{

if(arr[highIndex] <= 150)
{
// only 1 kid fits, put the larger kid in the boat if he fits
boatCounter++;
}
// Else, larger kid is too heavy to go on boat.

// Either way, we've handled the heavier child
highIndex--;
}

// cover case where both pointers point to same child
if(lowIndex == highIndex)
{
if (arr[highIndex] <= 150)
{
boatCounter++;
}

break;
}
}

return boatCounter;
}``````

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

This will silently ignore the kids that don't fit and leave them behind. It depends on how you interpret the question - definitely something worth clarifying with the interviewer - but I assume that the algorithm should return successfully only if there is a possible arrangement that includes all of the kids. Maybe a better approach would be to return a special value (`UINT_MAX` maybe?) to indicate that it is not possible to take all the kids. Also, the check `if (lowIndex == highIndex)` could be moved out of the loop.

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

Taking into account that we should move kids (probably weights not to much), I think we can use counting sort and reduce the complexity of algorithm O(n)

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

Isn't there a problem? If you mate the heaviest children with the lightest, it doesn't mean you can mate the second lightest with the second heaviest.

I would rather consider "middle index" as the index for which all values on the left are smaller than 75 and on the right larger than 75. The reason for that is that on your canoe, you can only have either two children with weights smaller than 75 or one larger and one smaller.

Then you should try to mate the children with index "middleIndex-1" with the heaviest and so on...You are then assured to have the good result as every children on the left side have a mate and there is nothing to do for those on the right side with no mate

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

There is no problem with the second lightest and second heaviest.
If second lightest + second heaviest > 150, then we assign a boat for only shipping second heaviest, and leave second lightest to next iteration.
There is an example: (l=light, h=heavy)

``````50 75 75 75 80 90 100 110	counter	  carry
l                     h        1         110
l                 h            2         50 + 100
l	        h               3         90
l        h                  4         80
l     h                     5	  75+75
lh                        6	  75``````

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

In case of one kid being heavier than 150 lb you can either cur the kid in a half and use two separate canoes, or ask if is possible to build a special cannoe by combining two or more in one. The latter is easily done, by just dividing kids weight by 150.

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

Here is a NLogN solution, first thing we sort the kids which will take O(nlogN), then we do as
2 sum problem but here we do not search for exact value, we search for any combination from R and L that is less than 150, and we count 1.

``````class Kid{
public:
double weight;
Kid(double w=0) :weight(w){}

bool operator<(const Kid& k)const{
return weight < k.weight;
}
};

int minNumberOfCanoe(const vector<Kid>& kids){

vector<Kid> sortedKids = kids;

sort(sortedKids.begin(), sortedKids.end());

int L = 0;
int R = sortedKids.size() - 1;

int canonCount = 0;

while (L <= R){
int wBig = sortedKids[R].weight;
int wSmall = sortedKids[L].weight;

if (wBig + wSmall <= 150){
canonCount++;
R--;
L++;
}
else if (wBig <= 150){
canonCount++;
R--;
}
}

return canonCount;
}``````

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

There is an error if there is a kid that weights more that 150 your code never decrement R index and the code falls in an infinite loop. Eje { 80, 60, 150 }

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

My bad { 80, 60, 155 }

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

Just create an array of size 150 and loop through each person and increment the count in the array by 1. Skip the person if their weight is more than 150. Then, just pair the heaviest person with the lightest person.

O(n)

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

``````int getCanoes(int[] array){
if(array == null){
return -1;
}

int left = 0;
int right = array.length -1;
int count = 0;
while(left < right){
if(array[left] + array[right] > MAX_WEIGHT){
right--;
}else{
left++;
right--;
}
count++;
}
return count;``````

}

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

it should be sorted first

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

Algorithm is to sort the array (ascending) and walk indexes toward the middle, comparing the sum of the values at the two indexes with the max weight of the canoes (150). If the summed weight is less than 150, increment boat counter and move both indexes closer to middle of array. If summed weight is higher than 150, only increment boat counter if heaver child is less than max weight, then only move higher index toward center (decrement). The reasoning here is that we'll try to pair the lighter child with the next heaviest child on the list, so we want to leave the low index pointer where it is and then go to the next iteration.

I tried a few test cases and it seems to be working as expected.

Complexity would be O(nlogn) due to the sort at the beginning.

``````private static int GetMaxBoats(List<int> arr)
{
arr.Sort();
/*foreach (int n in arr)
{
Console.WriteLine(n);
}*/

int lowIndex = 0;
int highIndex = arr.Count - 1;
int boatCounter = 0;

while(lowIndex < highIndex)
{
if(arr[lowIndex] + arr[highIndex] <= 150)
{
//2 kids fit
boatCounter++;
lowIndex++;
highIndex--;
}
else
{

if(arr[highIndex] <= 150)
{
// only 1 kid fits, put the larger kid in the boat if he fits
boatCounter++;
}
// Else, larger kid is too heavy to go on boat.

// Either way, we've handled the heavier child
highIndex--;
}

// cover case where both pointers point to same child
if(lowIndex == highIndex)
{
if (arr[highIndex] <= 150)
{
boatCounter++;
}

break;
}
}

return boatCounter;
}``````

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

Algorithm is to sort the array (ascending) and walk indexes toward the middle, comparing the sum of the values at the two indexes with the max weight of the canoes (150). If the summed weight is less than 150, increment boat counter and move both indexes closer to middle of array. If summed weight is higher than 150, only increment boat counter if heaver child is less than max weight, then only move higher index toward center (decrement). The reasoning here is that we'll try to pair the lighter child with the next heaviest child on the list, so we want to leave the low index pointer where it is and then go to the next iteration.

I tried a few test cases and it seems to be working as expected.

Complexity would be O(nlogn) due to the sort at the beginning.

``````private static int GetMaxBoats(List<int> arr)
{
arr.Sort();
/*foreach (int n in arr)
{
Console.WriteLine(n);
}*/

int lowIndex = 0;
int highIndex = arr.Count - 1;
int boatCounter = 0;

while(lowIndex < highIndex)
{
if(arr[lowIndex] + arr[highIndex] <= 150)
{
//2 kids fit
boatCounter++;
lowIndex++;
highIndex--;
}
else
{

if(arr[highIndex] <= 150)
{
// only 1 kid fits, put the larger kid in the boat if he fits
boatCounter++;
}
// Else, larger kid is too heavy to go on boat.

// Either way, we've handled the heavier child
highIndex--;
}

// cover case where both pointers point to same child
if(lowIndex == highIndex)
{
if (arr[highIndex] <= 150)
{
boatCounter++;
}

break;
}
}

return boatCounter;
}``````

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

O(N) solution: Get min weight minw. get max weight maxw in the list that is <= 150-m. Count the number of weights between minw and maxw - say this is count1.
Count the number of weights between maxw and 150. say this is count 2.
No sorting is needed.This will take 4 passes on the list/array. O(N)

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

Won't work.

Weights: 35 (small kid), 110, 111, 111, 114, 115, 149, 150
should take 7 canoes

minw = 35
maxw = 115
count1 = 4 ( 110, 111, 111, 114)
count2 = 1 ( 149)
Answer = 4 / 2 + 1 = 3 ... ? Not correct.

Adjusting your between statements to do what I think you may have meant to say:

minw = 35
max2 = 115
count1 = 6 (35, 110, 111, 111, 114, 115)
count2 = 2 (149, 150)
Answer = 6 / 2 + 2 = 5 ... still incorrect

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

Operates in O(n log n) average time with O(n) memory

Assumptions: All individual weights are <= the max weight specified (what do you do with kids larger than the max weight? Leave them at the shore all sad?)

``````public static int countCanoes(int maxWeight, int[] weights){
//sort the weights
Arrays.sort(weights);
//now pair off the weights that are collectively under maxWeight
int loIndex = 0, hiIndex = weights.length - 1;
int canoes = 0;
while(loIndex <= hiIndex){
int loWeight = weights[loIndex];
int hiWeight = weights[hiIndex];
if(loWeight + hiWeight <= maxWeight){
loIndex++;
}
hiIndex--;
canoes++;
}
return canoes;
}``````

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

Operating speed of O(nk) by bucket sorting the kids into their weight and then doing the same traversal. The amount of memory for this approach would be O(k). Could be faster when log n > kids weight.

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

JavaScript

``````var children = [ 100, 145, 33, 80, 9, 60, 30, 20 ];
children.sort(function(a,b){return a-b;});
i=0;
j=children.length-1;
num=0;
while  (i <= j){
big = children[j];
if (j==i)
small = 0;
else
small = children[i];

if ( small + big < 150 )
i++;
num++;
j--;
}

output: 5

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

``````public static int count(int[] weights){
int[] arr = new int[151];
for(int w : weights){
++arr[w];
}
int i = 0;
int j = arr.length-1;
int ret = 0;
for(;;){
for(; i < j && arr[i] == 0; ++i);
for(; j > i && arr[j] == 0; --j);
if (i >= j) break;
if (i+j <= 150){
--arr[i];
--arr[j];
} else {
--arr[j];
}
++ret;
}

if (i == j) {
if (i*2 <= 150){
ret += arr[i]/2;
ret += arr[i]%2;
} else {
ret += arr[i];
}
}

return ret;
}``````

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

Small bugfix:

``````public static int count(int[] weights){
int[] arr = new int[151];
for(int w : weights){
++arr[w];
}
int i = 0;
int j = arr.length-1;
int ret = 0;
for(;;){
for(; i < j && arr[i] == 0; ++i);
for(; j > i && arr[j] == 0; --j);
if (i >= j) break;
if (i+j <= 150){
--arr[i];
--arr[j];
} else {
--arr[j];
}
++ret;
}

if (i == j) {
if (i*2 <= 150){
ret += arr[i]/2;
ret += arr[i]%2;
} else {
ret += arr[i];
}
}

return ret;
}``````

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

It is a greedy problem

``````const int MAXW = 150;

int minCanoes(int A[], int n)
{
sort(A, A + n);

int ans = 0, lo = 0, hi = n - 1;

while (lo < hi)
{
if (A[lo] + A[hi] <= MAXW) { ++lo; --hi; }

else --hi;

++ans;
}

if (lo == hi) ++ans;

return ans;
}``````

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

``````#!/usr/bin/python
kids_by_weight = [40, 120, 122, 124, 156, 100, 140, 20, 50, 80, 30, 60, 80, 100, 40, 70, 30, 20]

kids_by_weight = sorted(kids_by_weight)
i =0
j =kids_by_weight.__len__() - 1
conoi = 0
while i < j:
if(kids_by_weight[i] + kids_by_weight[j] <= 150):
conoi += 1
print "\nConoi[", conoi, "]: ", kids_by_weight[i], " and ", kids_by_weight[j]
i += 1
j -= 1
elif(kids_by_weight[j] < 150):
j -= 1
conoi += 1
print "\nConoi[", conoi, "]: ", kids_by_weight[j]
elif(kids_by_weight[i] > 150):
i += 1
print "\nKid at Index:", i, " cannot be taken on conoi"
elif(kids_by_weight[j] > 150):
j -= 1
print "\nKid at Index:", j, " cannot be taken on conoi"

print "\n Number of Conoi(s):",  conoi``````

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

Simple, sort the array of weights then use low index and high index pointers in order to pick every pair of kids with weights <= 150 then decrement both li and hi by 1, if you could not found this case, then pick up the kid with the larger weight and then decrement high index by 1.

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CanoeCalculator {
public static int calcMinimumCanoe(List<Integer> weights) {
Collections.sort(weights);

int li = 0, hi = weights.size() - 1, number = 0;

while (li < hi) {
if (weights.get(li) + weights.get(hi) <= 150) {
++number;
++li;
--hi;
} else if (weights.get(hi) <= 150) {
++number;
--hi;
} else {
throw new RuntimeException("A kid weight cannot exceed 150!!!");
}
}

if (li == hi) {
++number;
}

return number;
}

public static void main(String[] args) {
List<Integer> w1 = new ArrayList<Integer>();

System.out.println(CanoeCalculator.calcMinimumCanoe(w1));

List<Integer> w2 = new ArrayList<Integer>();

System.out.println(CanoeCalculator.calcMinimumCanoe(w2));
}

}``````

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

Here is an O(nlogn) solution written in Python 3.4

``````def get_min_canoes(a):
a.sort()
if a[-1] > 150:
raise Exception("weight exceeds max")
left_walk = 0
right_walk = len(a) - 1
canoes = 0
while left_walk < right_walk:
if a[right_walk] + a[left_walk] <= 150:
# can get two together
left_walk += 1
right_walk -= 1
canoes += 1
# if only 1 item left
if right_walk == left_walk:
canoes += 1
return canoes
return canoes

a = [1,149]

print(get_min_canoes(a))``````

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

``````def get_min_canoes(a):
a.sort()
if a[-1] > 150:
raise Exception("weight exceeds max")
left_walk = 0
right_walk = len(a) - 1
canoes = 0
while left_walk < right_walk:
if a[right_walk] + a[left_walk] <= 150:
# can get two together
left_walk += 1
right_walk -= 1
canoes += 1
# if only 1 item left
if right_walk == left_walk:
canoes += 1
return canoes
return canoes

a = [1,149]

print(get_min_canoes(a))``````

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

Tom's solutions is the best so far. My solution does not beat it. It's just a different angle to think about this problem by dynamic programming.

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

``````public void fitKidsInCanoe(int maxWeightPerCanoe, ArrayList<Integer> weights) {
Collections.sort(weights);

int canoes = 0;
while (!weights.isEmpty()) {

int left = weights.size() == 1 ? maxWeightPerCanoe : weights.get(0);
int right = weights.get(weights.size() - 1);

if (left + right <= maxWeightPerCanoe) {
System.out.println("Coupled " + left + " : " + right);
weights.remove(0);
weights.remove(weights.size() - 1);
canoes++;
} else if (right <= maxWeightPerCanoe) {
System.out.println("Alone " + right);
weights.remove(weights.size() - 1);
canoes++;
} else {
System.out.println("Left behind " + weights.remove(weights.size() - 1));
}
System.out.println("Total canoes: " + canoes);
}
}``````

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

The answer provided by Tom will work here.
As an extension to the problem assume If I also want to optimize the algorithm to transfer max weight as early as possible or say there are chipper options available if the Weight being transferred is lesser then max capacity of 150

I will take this approach in that case:
1. Sort the Boys by Weight in O(nLogn)
2. Iterate over array for each W from highest weight
3. Search for ( W-150) or just smaller to it
4. Transfer the couple of Boy and mark boys transferred. Hire the boat based on sum of weight of both boys
Repeat steps 3-4 till all boys are moved.

This have additional complexity but it is still O(nLog(n))

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

public int canons(int[] weights){
int number_of_canons = 0;
int pointer1 = 0;
int pointer2 = weights.length - 1;

//when there is just one kid
if(weights.length ==1)
return 1;

//sorting the weights
Arrays.sort(weights);

while(pointer1 <= pointer2){

//if any single kid weighs more than 150 it is not possible to accommodate him in any boat
//hence no number of boats can accommodate ALL kids. In that case, the function returns -1
if(weights[pointer2] > 150){
return -1;
}
int total_weight = weights[pointer1] + weights[pointer2];
if(total_weight <= 150)
pointer1++;

number_of_canons++;
pointer2--;
}

return number_of_canons;
}

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

``````public int canons(int[] weights){
int number_of_canons = 0;
int pointer1 = 0;
int pointer2 = weights.length - 1;

//when there is just one kid
if(weights.length ==1)
return 1;

//sorting the weights
Arrays.sort(weights);

while(pointer1 <= pointer2){

//if any single kid weighs more than 150 it is not possible to accommodate him in any boat
//hence no number of boats can accommodate ALL kids. In that case, the function returns -1
if(weights[pointer2] > 150){
return -1;
}
int total_weight = weights[pointer1] + weights[pointer2];
if(total_weight <= 150)
pointer1++;

number_of_canons++;
pointer2--;
}

return number_of_canons;
}``````

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

``````public class CanoesNeeded {

static final int canoeMAX = 150;

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] kids = {35,110, 111, 111, 114, 115, 149, 150};
System.out.println("Canoes Needed: "+getMinCanoes(kids));
}

public static int getMinCanoes(int [] kids){
int canoes = 0;
Arrays.sort(kids);
for(int i=0,j=kids.length-1;i<=j;canoes++){
if(i==j){
System.out.println("Kid "+kids[i]+" gets his own canoe");
canoes+=1;
break ;
}
if(kids[i]+kids[j]>canoeMAX){
System.out.println("Kid "+kids[j]+" gets a canoe");
j--;
}
else{
System.out.println("Kids "+kids[i]+" & "+kids[j]+" share a canoe");
j--;
i++;
}
}
return canoes;
}
}``````

This is a O(n log n) solution because of the array sorting. Otherwise one pass over the weights is enough to solve the problem.

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

``````Sort the kids based upon their weights
Start with two pointers, one at the highest weight kid and another is at lowest weight kid
Check if both can be in a single canoe or not, if not, reserve one for higher weight kid, decrement its counter,
if yes, then reserve one for both of them, and increase and decrease the counters of respective kids.``````

Complexity : O(nlog(n))
Space : O(1)

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

There is a case where all the kids have a weight bigger that 150

``````public int GetNumCanoes(int[] weights, int maxWeight)
{
Array.Sort(weights);

int start = 0;
int end = weights.Length - 1;
int numCanoes = 0;

while (start <= end)
{
if (weights[start] > maxWeight)
start++;
else if (weights[end] > maxWeight)
end--;
else if (start <= end)
{
numCanoes++;
// If the sum is bigger that maxWeight they can't go an the same canoe, lets try in the next iteration
if (weights[start] + weights[end] <= maxWeight)
start++;
end--;
}
}

return numCanoes;
}``````

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

1. sort the kids by weight
2. take 2 pointers high and low pointing to first and last kid in the sorted array
3. while ( low < high) {

if(A[high] > 150 || A[low]+ a[high] > 150)
high --; count++;
else if (A[low] + A[high] < = 150)
high--; low++; count++;
}
return count;

complexity = O(nlogn)

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.