Country: United States

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

1 keep track of the number of toffees in the boxes initially 0.
2 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

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

Could you post the Java program? From your answer I would guess that you would be using a min PQ for the box sums.

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

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

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

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

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

Hi Diana, im flattered that you actually tested it. You're right, only the reported minmax was correct. I updated the code. Thanks.

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

Now your code is good. Thanks! :)

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

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

}

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

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

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

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

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

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.

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

sorting is not allowed since you can only choose consecutive toffee packet to put in a box.

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

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

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

This fails with [1,21,41,61,81,159,160,169,170,179,180,189,190,199,200], returns 440 as the maximum minimum and it should be 400.

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.