Google Interview Question


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

if you need the Java program ask so in the reply

- PeyarTheriyaa November 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Adam November 24, 2018 | Flag
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

- adr November 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Diana.Savvatina November 08, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- adr November 08, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now your code is good. Thanks! :)

- Diana.Savvatina November 11, 2018 | Flag
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);
    }
  }

}

- Anonymous November 03, 2018 | Flag Reply
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

- Diana.Savvatina November 05, 2018 | Flag Reply
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;
}

- Alex November 10, 2018 | Flag Reply
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.

- Popeye November 02, 2018 | Flag Reply
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.

- parni November 02, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 02, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- rick November 02, 2018 | Flag


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More