Assume you have a car park (parking lot), with n spaces arranged linearly (let's say 10 spaces initially):
The spaces are all the same size and will fit all vehicles that come.
This car park has one attendant, whose job it is to take the key from arriving drivers, and park the car. He will want to park in the first available slot from the start to avoid walking too much.
Later, when a driver wants to collect his car, the attendant needs to look up the car's location (by a unique ID, like registration plate) and retrieve the car for the driver. This will leave an empty slot. So for example, after a while, we might have a car park that looks like this:
A B _ D E _ G _ _ _ _
So it can be seen that, after a while, the car park becomes fragmented. So as an optimisation, when the attendant has free time, he will want to consider a "defrag" operation which will close up the empty slots and move the vehicles nearer the start. So for example the above would become:
A B D E G _ _ _ _ _ _
or
A B G D E _ _ _ _ _ _
Please address the "defrag" operation after you are happy with the park & retrieve operations.
For verification, we will want "unit tests" (these can just be calls from main) which show the state of the car park after each change (park, retrieve, defrag).
Example 1
park("A")
park("B")
park("C")
unpark("B")
park("D")Expected output:
A _ _ _ _ _ _ _ _ _
A B _ _ _ _ _ _ _ _
A B C _ _ _ _ _ _ _
A _ C _ _ _ _ _ _ _
A D C _ _ _ _ _ _ _
Example 2
park("A");
park("B");
park("C");
park("D");
park("E");
unpark("D");
unpark("B");
defrag();*Expected Output:
A _ _ _ _ _ _ _ _ _
A B _ _ _ _ _ _ _ _
A B C _ _ _ _ _ _ _
A B C D _ _ _ _ _ _
A B C D E _ _ _ _ _
A B C _ E _ _ _ _ _
A _ C _ E _ _ _ _ _
A E C _ _ _ _ _ _ _
class parking_system
{
private:
std::set<int> free_slots;
std::set<int> used_slots;
std::unordered_map<std::string, int> vehicle_parking_id_map;
std::vector<std::string> parking_slots;
int number_of_slots_;
public:
parking_system(int number_of_slots):parking_slots(number_of_slots, "-")
{
number_of_slots_ = number_of_slots;
for(int i = 0; i < number_of_slots; ++i)
{
free_slots.insert(i);
}
}
bool park(const std::string& vehicle_id)
{
if(free_slots.size() == 0)
return false;
int next_free_slot = *(free_slots.begin());
vehicle_parking_id_map.insert(std::make_pair(vehicle_id, next_free_slot));
parking_slots[next_free_slot] = vehicle_id;
free_slots.erase(next_free_slot);
used_slots.insert(next_free_slot);
print_parking_state();
return true;
}
bool unpark(const std::string& vehicle_id)
{
auto it = vehicle_parking_id_map.find(vehicle_id);
if(it == vehicle_parking_id_map.end())
return false;
int parking_id_to_free = it->second;
vehicle_parking_id_map.erase(it);
parking_slots[parking_id_to_free] = "-";
used_slots.erase(parking_id_to_free);
free_slots.insert(parking_id_to_free);
print_parking_state();
return true;
}
void defrag()
{
while(calculate_number_of_holes() != 0)
{
int last_parking_slot_filled = *(std::prev(std::end(used_slots)));
std::string vehicle_id_to_unpark = parking_slots[last_parking_slot_filled];
unpark(vehicle_id_to_unpark);
park(vehicle_id_to_unpark);
}
print_parking_state();
}
int calculate_number_of_holes()
{
if(used_slots.size() == 0)
return 0;
int last_parking_slot_filled = *(std::prev(std::end(used_slots)));
int number_of_parking_slots_used = used_slots.size();
int number_of_holes = (last_parking_slot_filled + 1) - number_of_parking_slots_used;
return number_of_holes;
}
void print_parking_state()
{
for(int i = 0; i < number_of_slots_; ++i)
{
std::cout << parking_slots[i] << ", ";
}
std::cout << std::endl;
}
};
Above is the code submitted part of the interview.
But didnt get selected to the next round.
Any other better way to implement the same?