Google Interview Question for Software Developers


Country: United States
Interview Type: In-Person




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

Where does it say time it re takes try to deliver

- sam March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Since there are no requirements to optimize accoring to some criteria,
// greedily assign icecreams to free machines as they come. When there are no
// free machines, wait for the first free one.

//input: order-time, order-number, icecream-type
//output: order-num, depart-time, total-time
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

struct Order {
  int numb;
  int type;
  int start_time;
  int end_time;
  Order():  numb(0), type(0), start_time(0), end_time(0) {}
  Order(int n, int y, int t): numb(n), type(y), start_time(t), end_time(0) {}
};

bool cmp_start_time(const Order &le, const Order &ri) {
  return le.start_time < ri.start_time ||
    (le.start_time == ri.start_time && le.type < ri.type) ||
    (le.start_time == ri.start_time && le.type == ri.type && le.numb < ri.numb);
}

bool cmp_numb(const Order &le, const Order &ri) {
  return le.numb < ri.numb ||
    (le.numb == ri.numb && le.start_time < ri.start_time) ||
    (le.numb == ri.numb && le.start_time == ri.start_time && le.type < ri.type);
}

int machine[3] = {0};

int main() {
  vector<Order> orders {
    Order(0, 0, 15),
    Order(1, 0, 5),
    Order(2, 1, 10),
    Order(3, 1, 20),
    Order(4, 1, 35) };

  /*    00 05 10 15 20 25 30 35 40 45 50 55 60 65 70
   * 0           |=========================|
   * 1     |=========================|
   * 2        |=======|
   * 3              ***|=======|
   * 4                       ***|=======|
   */

  // sort by start_time
  sort(orders.begin(), orders.end(), cmp_start_time);
  // process orders
  for (auto it = orders.begin(); it != orders.end(); ++it) {
    int which = -1;
    int free = INT_MAX;
    for (int i = 0; i < 3; ++i) {
      if (machine[i] < free) {
        free = machine[i];
        which = i;
      }
    }

    int real_start = max(machine[which], it->start_time);
    if (it->type == 0) {
      machine[which] = real_start + 45;
    }
    else {
      machine[which] = real_start + 15;
    }
    it->end_time = machine[which];
  }

  // sort by order-number
  sort(orders.begin(), orders.end(), cmp_numb);
  // display
  for (const auto &o : orders) {
    cout << o.numb << ' ' << o.end_time << ' ' << (o.end_time - o.start_time);
    cout << endl;
  }
}

- plesiv March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not an optimal solution in terms of overall time, or in other words, time of the last order departure. Not sure if that is required in this problem though. But if you have something like:

/*     00 05 10 15 20 25 30 35 40 45 50 55 60 65 70
   * 0           |====================|
   * 1     |===============|
   * 2        |=====|
   * 3              **|=======|
   * 4            **************|===============|
   */

the solution is not optimal as might be expected:

/*     00 05 10 15 20 25 30 35 40 45 50 55 60 65 70
   * 0           |====================|
   * 1     |===============|
   * 2        |=====|
   * 3        ***************|=======|
   * 4              *|===============|
   */

- Alex M. April 28, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class IcecreamStore {
	Time machine1_lastDeparture;
	Time machine2_lastDeparture;
	Time machine3_lastDeparture;

	public OrderOut makeIcecream(Time orderTime, int orderNum, int icecreamType) {
		Time earliestAvailable = min(machine1_lastDeparture, 
			machine2_lastDeparture, machine3_lastDeparture);

		OrderOut orderOut = new OrderOut();
		if(earlistAvailable <= orderTime) {
			orderOut.departureTime = orderTime 
				+ getTimeToMake(icecreamType);
		}
		else {
			orderOut.departureTime = earlistAvailable 
				+ getTimeToMake(icecreamType);
		}

		updateMachine(earliestAvailable);

		orderOut.totalTime = orderOut.departureTime - orderTime;
		orderOut.orderNum = orderNum

		return orderOut;
	}

	private Time getTimeToMake(int ice) {
		if(ice == 0)
			return new Time(15);
		else 
			return new Time(45);
	}

	private updateMachine(Time t) {
		// update the machine variable which has the lowest value with t. 
		// Because that machine will be used to make this order.
	}
}

class OrderOut {
	int orderNum;
	Time departureTime;
	Time totalTime;
}

- blue-j March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Seems intuitive, "lastDeparture" is not updated though once a machine is allocated for an order.

- Muthu May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Seems intuitive, "lastDeparture" is not updated though once a machine is allocated for an order.

- Muthu May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Seems intuitive, "lastDeparture" is not updated though once a machine is allocated for an order.

- Muthu May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <queue>
#include <iostream>
#include <string>
#include <functional>
using namespace std;

class IceCreamShop
{
	priority_queue<int, std::vector<int>, std::greater<int> > machineTimes;
public:
	IceCreamShop()
	{
		for (int i = 0; i < 3; i++)
			machineTimes.push(0);
	};

	string makeIceCream(int type)
	{
		int t = machineTimes.top();
		machineTimes.pop();
		t += timeForType(type);
		machineTimes.push(t);
		return to_string(t) + " " + to_string(timeForType(type));
	};

	int timeForType(int type)
	{
		if (type == 0)
			return 45;
		else
			return 15;
	}
};

int main()
{
	IceCreamShop shop;
	int n, type;
	while (cin >> n >> type)
		cout << n << " " << shop.makeIceCream(type) << endl;
	return 0;
}

- Ekaterina March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It will suffice to keep track of the time when the next job can be scheduled on each machine.

So 3 variables, one for each machine that will maintain the state.
Can use a min-heap if the number of machines are large.

A, B, C. Initialize to DateTime.Minimum.

GetOrderCompletionTime(Order)
NextAvailableMachine = Min(A, B, C).
if (NextAvailableMachine < Order.OrderTime)
NextAvailableMachine = Order.OrderTime + time taken to complete that order.
else
NextAvailableMachine += time taken to complete that order.

return NextAvailableMachine

- Anonymous March 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

enum IceCreamType{
	combo(45), 
	vanila(15);
	
	int time; 
	
	IceCreamType(int time){
		this.time = time; 
	}
	
	int getTime(){
		return this.time;
	}
}

class Order{
	int orderNum; 
	Date orderTime;
	IceCreamType type;
	Date departTime;
	int totalTime;
	
	public Order(int orderNum2, Time orderTime2, IceCreamType type2) {
		this.orderNum = orderNum2;
		this.orderTime = orderTime2;
		this.type = type2;
	}
	
	void setDepartInfo(int time){
		this.totalTime = time;
		this.departTime = this.orderTime;
		Calendar cl = Calendar. getInstance();
		cl.setTime(this.departTime);
		cl.add(Calendar.SECOND, this.totalTime);
	}
}


class Machine{
	ArrayList<Order> orders = new ArrayList<Order>();
	int totalTime;
	
	Machine(){
		totalTime = 0;
	}
	
	void addOrder(Order order){
		totalTime += order.type.getTime();
		order.setDepartInfo(totalTime);
		orders.add(order);
	}
	
	void removeOrder(int index){
		Order removeOrder = orders.remove(index);
		totalTime -= removeOrder.type.getTime();
	}
}

class IceCreamStore{
	final int MACHINE_COUNT = 3;
	Machine[] machines;
	
	IceCreamStore(){
		machines = new Machine[MACHINE_COUNT];
	}
	
	Order addOrder(int orderNum, Time orderTime, IceCreamType type){
		Machine targetMachine = selectTargetMachine();
		Order order = new Order(orderNum, orderTime, type);
		targetMachine.addOrder(order);
		return order;
	}	
	
	Machine selectTargetMachine(){
		Machine minMachine = machines[0]; 
		for(Machine machine : machines){
			if(minMachine.totalTime > machine.totalTime){
				minMachine = machine;
			}
		}
		return minMachine;
	}

}

- vic March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

enum IceCreamType{
	combo(45), 
	vanila(15);
	
	int time; 
	
	IceCreamType(int time){
		this.time = time; 
	}
	
	int getTime(){
		return this.time;
	}
}

class Order{
	int orderNum; 
	Date orderTime;
	IceCreamType type;
	Date departTime;
	int totalTime;
	
	public Order(int orderNum2, Time orderTime2, IceCreamType type2) {
		this.orderNum = orderNum2;
		this.orderTime = orderTime2;
		this.type = type2;
	}
	
	void setDepartInfo(int time){
		this.totalTime = time;
		this.departTime = this.orderTime;
		Calendar cl = Calendar. getInstance();
		cl.setTime(this.departTime);
		cl.add(Calendar.SECOND, this.totalTime);
	}
}


class Machine{
	ArrayList<Order> orders = new ArrayList<Order>();
	int totalTime;
	
	Machine(){
		totalTime = 0;
	}
	
	void addOrder(Order order){
		totalTime += order.type.getTime();
		order.setDepartInfo(totalTime);
		orders.add(order);
	}
	
	void removeOrder(int index){
		Order removeOrder = orders.remove(index);
		totalTime -= removeOrder.type.getTime();
	}
}

class IceCreamStore{
	final int MACHINE_COUNT = 3;
	Machine[] machines;
	
	IceCreamStore(){
		machines = new Machine[MACHINE_COUNT];
	}
	
	Order addOrder(int orderNum, Time orderTime, IceCreamType type){
		Machine targetMachine = selectTargetMachine();
		Order order = new Order(orderNum, orderTime, type);
		targetMachine.addOrder(order);
		return order;
	}	
	
	Machine selectTargetMachine(){
		Machine minMachine = machines[0]; 
		for(Machine machine : machines){
			if(minMachine.totalTime > machine.totalTime){
				minMachine = machine;
			}
		}
		return minMachine;
	}

}

- vic March 22, 2015 | Flag Reply


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