Google Interview Question
Country: United States
Binary search. Similar to painter’s partition problem.
def find(ts, n):
assert len(ts) >= n
lo = max(ts)
hi = sum(ts)+1
while lo<hi:
m = (lo+hi)/2
t_left = m
boxes_left = n-1
for t in ts:
assert t <= m
if t_left < t:
if boxes_left == 0:
lo = m+1
break
boxes_left -= 1
t_left = m-t
else:
t_left -= t
else:
hi = m
arrangement,s = [[]],0
for t in ts:
if s + t > lo:
s = 0
arrangement += [[]]
s += t
arrangement[-1] += [t]
return lo, arrangement
Has a bug. Doesn't count the last packet
##########
# Tests
##########
#import functools
def distr_toffee(packets):
lo,arrangement = find(packets,5)
sum_per_box = list(map(sum,arrangement))
print("%s\n%s\n%s\n%s"%(packets,lo,sum_per_box,arrangement))
print("Test %s"%("PASSED\n" if sum(packets)==sum(sum_per_box) else \
"FAILED: %u packets distributed instead of %u\n"%(sum(sum_per_box), sum(packets))))
distr_toffee([1,1,1,1,1])
distr_toffee([1,2,3,4,5])
distr_toffee([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3])
distr_toffee([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3])
distr_toffee([1,21,41,61,81,159,160,169,170,179,180,189,190,199,200])
Result:
[1, 1, 1, 1, 1]
1
[1, 1, 1, 1, 1]
[[1], [1], [1], [1], [1]]
Test PASSED
[1, 2, 3, 4, 5]
5
[3, 3, 4, 5]
[[1, 2], [3], [4], [5]]
Test PASSED
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
9.65625
[7, 8, 6, 6, 6]
[[1, 2, 3, 1], [2, 3, 1, 2], [3, 1, 2], [3, 1, 2], [3, 1, 2]]
Test FAILED: 33 packets distributed instead of 36
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
6.9375
[3, 4, 5, 3, 4]
[[1, 2], [3, 1], [2, 3], [1, 2], [3, 1]]
Test FAILED: 19 packets distributed instead of 30
[1, 21, 41, 61, 81, 159, 160, 169, 170, 179, 180, 189, 190, 199, 200]
499.71142578125
[364, 329, 349, 369, 389]
[[1, 21, 41, 61, 81, 159], [160, 169], [170, 179], [180, 189], [190, 199]]
Test FAILED: 1800 packets distributed instead of 2000
Hi Diana, im flattered that you actually tested it. You're right, only the reported minmax was correct. I updated the code. Thanks.
import java.util.*;
class Solution {
public static boolean check(int[] c, int m, int ans) {
int sum = 0;
for (int i = 0; i < c.length; i++) {
if (m == 0) {
return false;
}
if (sum + c[i] <= ans) {
sum += c[i];
} else {
m--;
sum = 0;
i--;
}
}
return true;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int t = input.nextInt();
while (t-- > 0) {
int n = input.nextInt();
int[] c = new int[n];
int sum = 0;
for (int i = 0; i < n; i++) {
c[i] = input.nextInt();
sum += c[i];
}
int m = input.nextInt();
int low = 1;
int high = sum;
int finalAns = -1;
while (low <= high) {
int ans = low + (high - low)/2;
if (check(c, m, ans)) {
finalAns = ans;
high = ans - 1;
} else {
low = ans + 1;
}
}
System.out.println(finalAns);
}
}
}
def trace(*args):
traceOn = False
if traceOn:
print(*args)
def calc_deviation_for_box(distr, avg, boxId):
return (avg - sum(distr[boxId]))**2
def calc_deviation(distr, avg):
diff_from_optimal = 0
for boxId in range(1,6):
diff_from_optimal += calc_deviation_for_box(distr, avg, boxId)
diff_from_optimal = round(diff_from_optimal**(0.5),4)
trace("diff_from_optimal=", diff_from_optimal, distr)
return diff_from_optimal
def distr_toffee(packets):
distr = {}
noof_toffee = sum(packets)
noof_packets = len(packets)
assert noof_packets >= 5, "packets are not enough for 5 boxes"
avg_per_box = noof_toffee/5
packetIx = 0
print("Start: noof_toffee=", noof_toffee, "noof_packets=", noof_packets, "avg_per_box=",avg_per_box)
print(packets)
# initial distribution: put less than avg except for the last box
for box in range(1,6):
trace("=== Box", box)
distr[box] = []
toffee_in_box = 0
while packetIx != noof_packets:
trace("toffee_in_box + packets[packetIx]=", toffee_in_box + packets[packetIx])
trace("packets_left=", noof_packets - packetIx, "5-box=", 5-box)
if box != 5:
if noof_packets - packetIx <= 5-box:
trace("next box, please: leave packets for remaining boxes")
break
if toffee_in_box > 0 and toffee_in_box + packets[packetIx] > avg_per_box:
trace("next box, please: stop before avg threshold")
break
distr[box].append(packets[packetIx])
trace("put", packetIx, "to", box)
toffee_in_box += packets[packetIx]
packetIx +=1
# optimization
diff_from_optimal = calc_deviation(distr, avg_per_box)
while True:
for box in range(5,1,-1):
trace("=== Optimizing Box", box)
while True:
if len(distr[box]) == 1:
trace("Next box, this one has just one packet")
break
diff_orig = (avg_per_box - sum(distr[box]))**2 + (avg_per_box - sum(distr[box-1]))**2
diff_new = (avg_per_box - (sum(distr[box]) - distr[box][0]))**2 + (avg_per_box - (sum(distr[box-1]) + distr[box][0]))**2
diff_orig = round(diff_orig**(0.5),4)
diff_new = round(diff_new**(0.5),4)
if diff_new > diff_orig:
trace("Next box, this one is good: ", diff_new, " vs.", diff_orig)
break
trace("move packet:", diff_new, " vs.", diff_orig)
distr[box-1].append(distr[box][0])
distr[box].pop(0)
trace(distr[box-1],distr[box])
new_diff = calc_deviation(distr, avg_per_box)
if new_diff >= diff_from_optimal:
break
diff_from_optimal = new_diff
print(distr)
print(list(map(lambda box: sum(distr[box]), range(1,6))))
print("==================================================== DONE", diff_from_optimal)
##########
# Tests
##########
distr_toffee([1,1,1,1,1])
distr_toffee([1,2,3,4,5])
distr_toffee([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3])
distr_toffee([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3])
distr_toffee([1,21,41,61,81,159,160,169,170,179,180,189,190,199,200])
Output:
Start: noof_toffee= 5 noof_packets= 5 avg_per_box= 1.0
[1, 1, 1, 1, 1]
{1: [1], 2: [1], 3: [1], 4: [1], 5: [1]}
[1, 1, 1, 1, 1]
==================================================== DONE 0.0
Start: noof_toffee= 15 noof_packets= 5 avg_per_box= 3.0
[1, 2, 3, 4, 5]
{1: [1], 2: [2], 3: [3], 4: [4], 5: [5]}
[1, 2, 3, 4, 5]
==================================================== DONE 3.1623
Start: noof_toffee= 36 noof_packets= 18 avg_per_box= 7.2
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
{1: [1, 2, 3, 1], 2: [2, 3, 1, 2], 3: [3, 1, 2, 3], 4: [1, 2, 3], 5: [1, 2, 3]}
[7, 8, 9, 6, 6]
==================================================== DONE 2.6077
Start: noof_toffee= 30 noof_packets= 15 avg_per_box= 6.0
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
{1: [1, 2, 3], 2: [1, 2, 3], 3: [1, 2, 3], 4: [1, 2, 3], 5: [1, 2, 3]}
[6, 6, 6, 6, 6]
==================================================== DONE 0.0
Start: noof_toffee= 2000 noof_packets= 15 avg_per_box= 400.0
[1, 21, 41, 61, 81, 159, 160, 169, 170, 179, 180, 189, 190, 199, 200]
{1: [1, 21, 41, 61, 81, 159], 2: [160, 169, 170], 3: [179, 180], 4: [189, 190], 5: [199, 200]}
[364, 499, 359, 379, 399]
==================================================== DONE 114.9783
#include <unordered_map>
#include <vector>
#include <iostream>
using namespace std;
class Result
{
public:
Result(int max, const vector<int>& boxes) : max_(max), boxes_(boxes) {}
Result() : max_(numeric_limits<int>::max()) {}
int max_;
vector<int> boxes_;
bool operator<(const Result& other) const
{
return max_ < other.max_;
}
};
void Distribute(const vector<int>& a, int k, vector<int>& boxes, int max, Result& best_res, int idx = 0)
{
if (idx < 0 || idx > a.size())
{
return;
}
if (max >= best_res.max_)
{
return;
}
if (idx == a.size())
{
if (boxes.size() == k)
{
if (max < best_res.max_)
{
best_res = Result(max, boxes);
}
}
return;
}
boxes.push_back(a[idx]);
Distribute(a, k, boxes, std::max(max, a[idx]), best_res, idx + 1);
boxes.pop_back();
if (!boxes.empty())
{
boxes.back() += a[idx];
Distribute(a, k, boxes, std::max(max, boxes.back()), best_res, idx + 1);
boxes.back() -= a[idx];
}
}
int main()
{
Result res;
vector<int> boxes;
Distribute({1, 21, 41, 61, 81, 159, 160, 169, 170, 179, 180, 189, 190, 199, 200}, 5, boxes, 0, res);
cout << res.max_ << "\n";
for (int n : res.boxes_)
{
cout << n << ",";
}
cout << "\n";
return 0;
}
1. sort all the toffee packets based on the number of toffees.
2. initialize 5 boxes with the last values (top 5 max values)
3. Insert the boxes into the min heap (size 5) based on the no of toffees
4. Iterate from (1 to n-5 packets) --> pop top element, add packet and insert again.
5. pop all top 4 boxes. 5th box or final popped box's toffees from the heap is the answer to the question.
sorting is not allowed since you can only choose consecutive toffee packet to put in a box.
This fails with [1,21,41,61,81,159,160,169,170,179,180,189,190,199,200], returns 440 as maximum minimum and should return 400
1 keep track of the number of toffees in the boxes initially 0.
- PeyarTheriyaa November 02, 20182 add the incoming toffee packet to the first box with the minimum number of toffees
note 1 : under the given circumstances this will produce the minimum max toffees in all the boxes
note 2 : I assume that you are not allowed to rearrange toffee packets in the boxes
if you need the Java program ask so in the reply