Directi Interview Question
Software EngineersCountry: India
Preamble:
- Definitions:
Box(ID, Weight, Scheduled?),
Machine(ID, Capacity),
Schedule(Machine, Boxes)
- Create sorted array of machines sorted by Machine.CarryingCapacity - say, machines
- Create array of boxes sorted by Box.Weight - say, boxes
- Assume there is a binary search utility method over sorted arrays with a twist as:
-- For Machines: Try exact match, otherwise return the next highest capacity machine
Algorithm:
- For every pending box,
-- Find best machine
-- Reduce the machine capacity
-- Add box to schedule
-- Remove box from pending list
- Repeat the above loop
-- Until all the boxes are scheduled or no new schedule has been created
-- Reason for repeating of loop can be
--- More boxes than machines can carry
--- Machine that can fit box has been selected for other boxes with not enough capacity
Psuedo-Code:
total_schedules = new Array()
time_units = 0
while (true) {
# Initialize the loop state
unscheduled_boxes = boxes.filter_by { |box| NOT box.Scheduled? }
unscheduled_machines = machines.dup_as_sorted()
scheduled_machines = new SortedArray()
current_schedules = new Array()
for (Box box in unscheduled_boxes) {
# Find best possible machine for this box weight
# in both scheduled and unscheduled machines
old_machine = scheduled_machines.binary_search(box.Weight)
new_machine = unscheduled_machines.binary_search(box.Weight)
# If both Old and New Machines are NULL, then continue
# Why not break? May be one of the old machines has higher capacity
# but due to it's existing scheduled capacity can't have this in the schedule
if (old_machine == NULL && new_machine == NULL) {
continue;
}
# If old machine remaining capacity is apt
if (old_machine!= NULL &&
(
(old_machine.CarryingCapacity == box.Weight) ||
(old_machine.CarryingCapacity <= new_machine.CarryingCapacity)
) {
# Update Schedule
schedule = current_schedules.find(old_machine)
schedule.Boxes.add(box)
# Update Box
box.Scheduled? = true
# Update Machine Lists
## Removing and adding would make the machine sorted on reduced capacity
old_machine.CarryingCapacity -= box.weight
scheduled_machines.remove(old_machine)
## Only add if there is some capacity left over
if (old_machine.CarryingCapacity > 0) {
scheduled_machines.add(old_machine)
}
}
# If new machine capacity is apt
else
if (new_machine!= NULL &&
(
(new_machine.CarryingCapacity == box.Weight) ||
(new_machine.CarryingCapacity < old_machine.CarryingCapacity)
) {
# Update Schedule
schedule = new Schedule(new_machine, [box])
current_schedules.add(schedule)
# Update Box
box.Scheduled? = true
# Update Machine Lists
new_machine.CarryingCapacity -= box.weight
unscheduled_machines.remove(new_machine)
## Only add if there is some capacity left over
if (new_machine.CarryingCapacity > 0) {
scheduled_machines.add(new_machine)
}
}
}
if (current_schedules.empty?) {
# Scheduling failed! Fatal Error
# May be the box(es) weight is more than machine capacity
break
}
total_schedules.add(current_schedules)
time_units += 1
}
Python
Output:
- Diana.Savvatina November 07, 2018