Amazon Interview Question
SDE-3sCountry: United States
1. If unpark was called, keep track of the parking space in priority queue where floor>length>width
2. Allocate new parking space
#include <iostream>
#include <queue>
using namespace std;
struct Location {
size_t length = -1;
size_t width = -1;
size_t floor = -1;
void Print()
{
if(IsOk()) { cout << "(" << length << ", " << width << ", " << floor << ")" << endl; }
}
bool operator>(const Location& other) const
{
// the order of comparison matters
if(this->floor > other.floor) return true;
if(this->floor < other.floor) return false;
// same floor, compare length
if(this->length > other.length) return true;
if(this->length < other.length) return false;
// same floor & length, just compare the width
return this->width > other.width;
}
bool IsOk() const { return length != string::npos; }
};
; // Min heap
class ParkingLot
{
size_t m_length = 0;
size_t m_width = 0;
size_t m_floor = 0;
size_t m_nextLen = 0;
size_t m_nextWidth = 0;
size_t m_nextFloor = 0;
bool m_isFull = false;
priority_queue<Location, vector<Location>, greater<Location>> Q;
protected:
/**
* @brief find next parking space. return false if the parking lot is full
*/
bool FindLocation(Location& loc)
{
loc = { string::npos, string::npos, string::npos };
if(!Q.empty()) {
// reuse parking spot
loc = Q.top();
Q.pop();
return true;
}
if(m_isFull) { return false; }
loc = { m_nextLen, m_nextWidth, m_nextFloor };
// Allocate new spot
if(m_nextWidth + 1 < m_width) {
// progress the width, this keeps lowest available length / floor
++m_nextWidth;
} else {
// m_nextWidth is at its max, reset it back to 0
m_nextWidth = 0;
// attempt to increase the length first, since floor has highest priority
if(m_nextLen + 1 < m_length) {
++m_nextLen;
} else {
m_nextLen = 0;
if(m_nextFloor + 1 < m_floor) {
++m_nextFloor;
} else {
// full
m_isFull = true;
return true;
}
}
}
return true;
}
public:
ParkingLot(int length, int width, int floor)
: m_length(length)
, m_width(width)
, m_floor(width)
{
}
Location Park()
{
Location loc;
if(!FindLocation(loc)) { cout << "parking lot is full" << endl; }
return loc;
}
void Unpark(size_t len, size_t width, size_t floor) { Q.push({ len, width, floor }); }
};
ParkingLot P(3, 3, 3);
void Park()
{
Location loc = P.Park();
loc.Print();
}
void Unpark(int len, int width, int floor) { P.Unpark(len, width, floor); }
Not sure why the function take i, j, and k as parameters instead of length, width and floor to be more intuitive.
- Dung Nguyen April 14, 2019