Google Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
// 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;
}
}
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 *|===============|
*/
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;
}
Seems intuitive, "lastDeparture" is not updated though once a machine is allocated for an order.
Seems intuitive, "lastDeparture" is not updated though once a machine is allocated for an order.
#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;
}
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
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;
}
}
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;
}
}
Where does it say time it re takes try to deliver
- sam March 13, 2015