[System Design] Design an efficient parking lot system

System requirements

Functional:

1. User can reserve a parking spot.
2. User pays for the reservation.
3. User can park a car on the parking spot.
4. User can leave before the reservation time expires.
5. There are three different parking spots - compact size, standard size, and with electric charger.
6. One common error case to handle is when a user makes a reservation, but fails to show up. In this case, we would charge for the first 24 hours.

Non-Functional:

1. Scalability. We are designing this for an international company who has 1000s of parking lots across nations.
2. Availability.
3. Consistency. Once a reservation is made, the parking spot must be available for the user. No double-booking.

There can be other considerations, e.g., indoor parking vs outdoor parking, additional services like car wash, and parking cars near the entrance to have a quick enter & exist experience. But for now, I'd like to focus on the requirements I listed above.

Capacity estimation

I assume:

• The company has operations in 10 countries.
• The company has 100 parking lots, on average, in one country.
• On average, each parking lot has a capacity of 200 cars. 70% standard cars. 20% compact cars. 10% electronic cars with chargers.
• 80% of users use it for short term parking, averaging 4 hours.
• 20% of users use it for long term parking, averaging 5 days.
• For each parking lot, there are on average 50 reservation requests per day.

Estimation:

• 10 * 100 = 1000 parking lots.
• For each day, this system will receive 50,000 reservation requests per day.
• Each reservation would mainly consists of:
• User ID (20 bytes)
• Car type (1 byte)
• Reservation start time (8 byte)
• Reservation end time (8 byte)
• Roughly totaling 40 bytes.
• Each day, we would add 400KB of data.
• In 2 years, it would add up to 292MB.

This estimate leads me to choose a relational database as the storage for reservations. The estimated size is within RDB's limits. RDB also gives strong consistency guarantee, which is suitable for a reservation system because avoiding inconsistency (e.g. double booking) is an important requirement. The response time requirement is not very hard. If reservation takes a couple of seconds (instead of milliseconds), that would be acceptable.

API design

APIs used by users:

        check_capacity(lot_ID, vehicle_type, start_date_time, end_date_time): returns the number of open spots in the given parking lot. It also returns the price.

        reserve_spot(user_ID, lot_ID, vehicle_type, start_date_time, end_date_time): it returns the reservation ID and the price.

        pay(user_ID, reservation_ID)

APIs used by gate checking service at the parking lot:

        vehicle_arrived(reservation_ID, date_time)

    

        vehicle_left(reservation_ID, date_time)

Database design

Reservation table:

• reservation_ID (primary key)
• lot_ID (foreign key)
• user_ID (foreign key)
• start_time
• end_time
• vehicle_type (foreign key)
• payment_status (paid, unpaid, canceled)
• completion_status (to be completed, fulfilled, canceled)

Vehicle_Type table:

• vehicle_type_ID

Lot table:

• lot_ID (primary key)
• contact_info_ID (foreign key)
• Lot_Space ID (foreign key to Lot_Space table)
• capacities (foreign key to Lot_Capacity table)

Lot_Capacity table:

• lot_space ID (primary key)
• vehicle_type (foreign key to Vehicle_Type)
• number of space

Contact_Info table:

• contact_info_ID (primary key)
• contact_type
• contact_value

User table:

• user_ID (primary key)
• contact_info_ID (foreign key)
• vehicles (foreign key to Vehicle table)

Vehicle table:

• vehicle_ID (primary key)
• vehicle_type (foreign key to Vehicle_Type table)

Transaction table:

• transaction_ID (primary key)
• user_ID (foreign key)
• vehicle_ID (foreign key)
• check_in_date_time
• check_out_date_time

There can be enhancements, e.g., reviews for the parking lot, and reviews for the users. But for now, I will focus on the tables above.

High-level design

CDN caches static contents for high performance.

Rate Limiter protects the service from DOS attacks.

Load Balancer distributes requests to App Servers using weighted round robin algorithm.

As discussed above, RDB is used as the data store.

App Server uses Redis Cache for performance gain.

Request flows

check_capacity() is handled by Reservation Server consulting the data in the database.

reserve_spot() is handled by Reservation Server, which creates a new entry in Reservations table.

It would create a request for payment, which is queued by Message Queue and submitted to the external Payment System.

reserve_spot() may fail if multiple users are trying to book the same spot. Return an error and ask the client to try calling reserve_spot() again.

It would also fail if the lot is full. In that case, the client should not retry. Reservation Server may return helpful information such as estimated time spots may open up in the future.

vehicle_arrived() and vehicle_left() are handled by Transaction Server, which modifies the Transaction table to keep track of vehicle checkins and checkouts.

If vehicle does not arrive after some number of hours (e.g. 24 hours), reservation would be canceled. The user would be charged for 1 day of payment.

If inconsistent state happens, e.g., vehicle_left() is called before corresponding vehicle_arrived(), administrator at the lot should be notified. The service would assume the vehicle arrived around the corresponding reservation start time.

Detailed component design

See Sequence Diagram. It depicts how messages flow for client to make a reservation and pay for it, and for the parking lot system to notify the Transaction System when the user's vehicle arrives and leaves.

One important algorithm is how to find an open spot when reserve_spot() call is made.

To support this functionality, we would chop 24 hours into 15 minutes. One day would be represented by 96 slots. Since we just need to store occupied / unoccupied, we can use one bit to represent the 15 minute slot. 1 spot requires 96 bits per day. 35040 bits (~4KB) per year.

When reserve_spot(start_time, end_time) is called, the algorithm would be:

1. Convert start_time and end_time into index. For example, 00:00 on January 1st would be index 0. 00:15 would be index 1, and so on.
2. Create a bitmap with 1's representing time between start_time and end_time.
3. Compare this bitmap to the bitmaps representing occupied time of parking spots. Scan from parking spot 0 (closest to entrance) to N (farthest from the entrance).

This algorithm would find the closest parking spot that is available for the desired time slot.

Because this search is bound by the number of parking slots (100s) and the granularity of reservation (15 minutes), it would be performant enough.

It would probably be possible to use Interval Tree data structure to optimize this algorithm further, if further optimization is required.

Trade offs/Tech choices

The biggest decision point was the database. For this service, I chose Relational Database over NoSQL Database. The data size, estimated at increasing ~300MB in 2 years, is well within the capacity of a RDB. RDB provides strong consistency, which is beneficial for a reservation service. Once a reservation is made, the user needs the system to honor it 100%, without the risk of double booking or a reservation mistakenly deleted.

NoSQL database, for example MongoDB, would provide a better horizontal scalability than RDB. But for this service, I decided the benefit of RDB outweighs that of NoSQL DB.

Failure scenarios/bottlenecks

One bottleneck scenario is when a large number of people gather in a place near one of the parking lots, e.g., for Olympics Games.

This would put a burden on the reservation work flow (reserve_spot(), pay()). Transaction Server would be fine, as the number of requests to Transaction Server would be limited by the physical limitation of the parking lots (i.e. how many spots they have).

To prepare for such an event, all the software components must be replicated horizontally to have enough capacity. Rate Limits have to be configured to smooth out extreme level of traffic.

The database tables must be replicated in multiple ways (e.g. a copy within data center, a copy in another data center, a copy in a different region) for fault tolerance and disaster recovery.

Monitoring system must be put in place to monitor the health of all the servers and components.

Future improvements

I think this builds a foundation for more feature development in the future, e.g., additional services, more vehicle and parking types (very large vehicles, buses and trucks, motorcycles and bicycles, charging stations).

Optimizations and availability improvement based on geographic locations would be a good area to invest further. For example, using Global Load Balancer so that clients get routed to the closest data center. Replicating databases between different geographic locations as a back up mechanism in case of a regional disaster.

[Leetcode]: 2536. Increment Submatrices by One

You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes.

You are also given a 2D integer array query. For each query[i] = [row1i, col1i, row2i, col2i], you should do the following operation:

Add 1 to every element in the submatrix with the top left corner (row1i, col1i) and the bottom right corner (row2i, col2i). That is, add 1 to mat[x][y] for for all row1i <= x <= row2i and col1i <= y <= col2i.

Return the matrix mat after performing every query.

Constraints:

1 <= n <= 500

1 <= queries.length <= 10^4

0 <= row1i <= row2i < n

0 <= col1i <= col2i < n

Analysis:

This question looks very straightforward: for each query, we can just update all the elements in the block by adding 1. But the overall time complexity is O(10^4 * n * n) ~ O (25 x 10^6), which cannot pass the large cases in the OJ.

So how can we improve it?

One way is to lower the dimension: from 2D to 1D. Then for the 1D problem, we can solve it using scanning line algorithm. The key observation is that, for each update (or query), we just need to adjust the staring and the ending of the range (for example, the beginning is +1, and the ending is -1), and we do not need to do the updates for every element between the starting and ending. Then we can run a one-time accumulation from left to right to get the actual updates for all the elements.

So similarly, for 2D we can add a labeling for the changes in a block by just update the four corners of the block: 

1. the top left corner: +1;

2. the top right corner: -1;

3. the bottom left corner: -1;

4. the bottom right corner: +1.

How do we rationalize this?

1 is for the staring of the change; 2 and 3 means the end of the changes in horizontal and vertical directions, respectively; then what is 4 for?

The reason is simple: by ending the change in 2 and 3, we have double the changing in range staring with 4. But we just need one change. So we need to set it back by adding 1.

After the labeling, we can get the updated values for every elements by performing accumulations like the case in 1D.

The 2D accumulation formula is:

1: res[i][j] +=  changes[i][j]

2. res[i][j] += res[i-1][j];

3. res[i][j] += res[i][j-1];

4. res[i][j] -= res[i-1][j-1].

res[i][j] is the accumulated sum (like a prefix sum) of the block starting from top left corner (0, 0) to bottom right corner (i, j).

The changes[i][j] is for the changes at the (i, j).

The sum of the block except the element at (i, j) is: res[i-1][j] + res[i[j-1] - res[i-1][j-1]. (why?)

Thus the formula is:

res[i][j] = changes[i][j] + res[i-1][j] + res[i][j-1] - res[i-1][j-1]

which is the sum of the above formula from 1 to 4.

For easier coding, we set the change matrix with one more row and column than that of the element matrix.

See the code below:

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> res(n, vector<int>(n, 0)), diff(n+1, vector<int>(n+1, 0));
        for(auto &a : queries) {
            int x1 = a[0], y1 = a[1], x2 = a[2], y2 = a[3];
            ++diff[x1][y1];
            --diff[x1][y2+1];
            --diff[x2+1][y1];
            ++diff[x2+1][y2+1];
        }
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                res[i][j] += diff[i][j];
                if(i>0) res[i][j] += res[i-1][j];
                if(j>0) res[i][j] += res[i][j-1];
                if(i>0 && j>0) res[i][j] -= res[i-1][j-1];
            }
        }
        return res;
    }
};

[Leetcode] 2296. Design a Text Editor

2296. Design a Text Editor

Design a text editor with a cursor that can do the following:

Add text to where the cursor is.

Delete text from where the cursor is (simulating the backspace key).

Move the cursor either left or right.

When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that 0 <= cursor.position <= currentText.length always holds.

Implement the TextEditor class:

TextEditor() Initializes the object with empty text.

void addText(string text) Appends text to where the cursor is. The cursor ends to the right of text.

int deleteText(int k) Deletes k characters to the left of the cursor. Returns the number of characters actually deleted.

string cursorLeft(int k) Moves the cursor to the left k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

string cursorRight(int k) Moves the cursor to the right k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

Constraints:

1 <= text.length, k <= 40

text consists of lowercase English letters.

At most 2 * 10^4 calls in total will be made to addText, deleteText, cursorLeft and cursorRight.

Analysis:

This question is labeled as hard in Leetcode, but the logic is quick straightforward. The only problem is the efficiency. 

If we use a string and an index for the cursor position, then we will see TLE or MLE.

One neat method is to use two stacks, one is the left stack and the other is right stack. 

For add, we just push the new string into left stack;

for delete, we just pop up the chars from the left stack;

for leftMove, we just pop out k or less (if less than k elements remains) chars from left stack, and push in right stack; then return 10 or less(if less than 10 elements remains) from the left stack;

for rightMore we just need to do the reversed operation as that for the leftMove.

See the code below

class TextEditor {
public:
    TextEditor() {
    }
    
    void addText(string text) {
        for(auto &a : text) lt.push(a);
    }
    
    int deleteText(int k) {
        int res = 0;
        while (lt.size() && k > 0) {
            lt.pop();
            ++res;
            --k;
        }
        // cout << "delet" << endl;
        return res;
    }
    
    string cursorLeft(int k) {
        while(lt.size() && k > 0) {
            auto t = lt.top();
            lt.pop();
            rt.push(t);
            --k;
        }
        return f(lt, 10);
    }
    
    string cursorRight(int k) {
         while(rt.size() && k > 0) {
            auto t = rt.top();
            rt.pop();
            lt.push(t);
            --k;
        }
        return f(lt, 10);
    }
private:
    stack<int> lt, rt;
    string f(stack<int> &sk, int k) {
        string res;
        while(sk.size() && k > 0) {
            res.push_back(sk.top());
            sk.pop();
            --k;
        }
        reverse(res.begin(), res.end());
        for(auto &a : res) sk.push(a);
        return res;
    }
};

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor* obj = new TextEditor();
 * obj->addText(text);
 * int param_2 = obj->deleteText(k);
 * string param_3 = obj->cursorLeft(k);
 * string param_4 = obj->cursorRight(k);
 */

[Leetcode] 2293. Min Max Game

2293. Min Max Game

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.

For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).

For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).

Replace the array nums with newNums.

Repeat the entire process starting from step 1.

Return the last number that remains in nums after applying the algorithm.

Constraints:

1 <= nums.length <= 1024

1 <= nums[i] <= 10^9

nums.length is a power of 2.

Analysis

This question can be resolved by the classic Divide and Conquer algorithm.

The only extra thing is we need a flag to indicate whether it is the first half or the second half.

when flag == 0, we choose the min;

when flag == 1, we choose the max.

See the code below:

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        return f(nums, 0, nums.size(), 0);
    }
private:
    int f(vector<int>&ns, int left, int right, int flag) {
        if(left+1 == right) return ns[left];
        int mid = left + (right - left)/2;
        int x = f(ns, left, mid, 0), y = f(ns, mid, right, 1);
        return flag ? max(x, y) : min(x, y);
    }
};

[Leetcode] 2145. Count the Hidden Sequences

2262. Total Appeal of A String

The appeal of a string is the number of distinct characters found in the string.

For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.

Given a string s, return the total appeal of all of its substrings.

A substring is a contiguous sequence of characters within a string.

Constraints:

1 <= s.length <= 10^5

s consists of lowercase English letters.

Analysis:

This question is quite straightforward if we do not care about the time complexity.

The upper bound is O(n^2), where n is the total number of chars in the string, since we only have O(n^2) substrings in total. (If we count the number of unique chars while expanding, the time complexity is O(n^2); if count after the expanding, the time complexity is O(n^3)).

But O(n^2) is not the optimal solution, which cannot pass the OJ since n could be 10^5.

One way to think about this question is that: when we add a new char [C] into account and the index of the new char is idx, then we will have (idx + 1) new substrings ending with C.

For all the (id+1) substrings, we have calculated (or known) the total unique chars before the last char, or the new char C.

Since we only care about the unique chars, we just need to know when the char C appears last time, or we just need to know the index of the previous char C, prev_idx. Before this position, the new char is not considered as a unique one. After this position, the new char will contribute 1 to the count. For all the (idx + 1) new substrings ending with the new char C, the total delta to total count is (idx - prev_idx) due to the new char C, or

delta = idx - prev_idx

If we have memorize the total count of the unique chars for the (id+1) new substrings excluding the new char C as prev_count, then we can update this to (prev_count + delta), or

cur_count = prev + delta

This is the total increase in count by taking the new char C into account.

So we just need to sum up all of these for each char in the string.

A tiny trick can be used with a vector of size ~ 26 to record the previous index of each char.

The time complexity is O(n), and space complexity is O(26), where n is the number of elements.

See the code below:

class Solution {
public:
    long long appealSum(string s) {
        long long res = 0, n = s.size(), prev_count = 0;
        vector<long long> cts(26, -1);
        for(int i=0; i<n; ++i) {
            int id = s[i] - 'a';
            int delta = i - cts[id];
            int cur_count = prev_count + delta;
            res += cur_count;
            // update
            prev_count = cur_count;
            cts[id] = i;
        }
        return res;
    }
};

[Leetcode] 2145. Count the Hidden Sequences

2145. Count the Hidden Sequences

You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] - hidden[i].

You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain.

For example, given differences = [1, -3, 4], lower = 1, upper = 6, the hidden sequence is a sequence of length 4 whose elements are in between 1 and 6 (inclusive).

[3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.

[5, 6, 3, 7] is not possible since it contains an element greater than 6.

[1, 2, 3, 4] is not possible since the differences are not correct.

Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

Constraints:

n == differences.length

1 <= n <= 10^5

-10^5 <= differences[i] <= 10^5

-10^5 <= lower <= upper <= 10^5 

Analysis:

This question is quick interesting, which needs some derivations. 

If check the first example carefully, this question is equivalent to ask for the total number of valid first element A0.

Since the values of all the elements should be in some range, then we just need to take care of the minimum and maximum of the elements. Or if the minimum and maximum elements valid, then all the rest should be valid as well.

So we can write down some equations first:

lower <= A0 <= upper        (1)

lower <= Amin <= upper    (2)

lower <= Amax <= upper    (3)

How to find the Amin and Amax?

The only thing we know is the diffs. So we can get the (Amin - A0) and (Amax - A0) by cumulating the diffs from the first one.

Once we get these two values, Dmin and Dmax, we can modify the equations above a little bit:

Amin - A0 = Dmin   =>  Amin = A0 + Dmin

Amax - A0 = Dmax  =>  Amax = A0 + Dmax

Then we can re-write (2) and (3)

lower <= A0 + Dmin <= upper    => lower - Dmin <= A0 <= upper - Dmin    (4)

lower <= A0 + Dmax <= upper   => lower - Dmax <= A0 <= upper - Dmax   (5)

Putting (1), (4) and (5) together, we can derive the valid range of A0,

max(lower, lower - Dmin, lower - Dmax)  <= A0 <= min(upper, upper - Dmin, upper - Dmax)

Since (lower - Dmin) is always no larger than (lower - Dmax), and (upper - Dmin) <= (upper - Dmax), the above range can be re-written as

max(lower, lower - Dmin) <= A0 <= min(upper, upper - Dmax).

The time complexity is O(n), and space complexity is O(1), where n is the number of elements.

See the code below:

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        long sum = 0, mn = differences[0], mx = mn;
        for(auto &a : differences) {
            sum += a;
            mn = min(mn, sum);
            mx = max(mx, sum);
        }
        // d0: the first element
        // d_min: the min element exclude d0
        // d_max: the max element exclude d0
        // d_min - d0 = mn ---> d_min = d0 + mn
        // d_max - d0 = mx ---> d_max = d0 + mx
        // lower(L) <= di <= upper(R) for all i, so
        // (1) L <= d0 + mn <= R ---> L - mn <= d0 <= R - mn
        // (2) L <= d0 + mx <= R ---> L - mx <= d0 <= R - mx
        // (3) L <= d0 <= R
        // combine (1) - (3)
        // max(L-mn, L) <= d0 <= min(R, R - mx)
        // so question becomes: how many valid d0?
        long l = max((long)lower, lower - mn), r = min((long)upper, upper - mx);
        return r >= l ? r - l + 1 : 0;
    }
};

[Leetcode] 813. Largest Sum of Averages

813. Largest Sum of Averages

You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in nums, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.

Constraints:

1 <= nums.length <= 100

1 <= nums[i] <= 10^4

1 <= k <= nums.length

Analysis:

This question asks for the an maximum value, so we usually can consider dp first.

As it is known, the key for dp is to find the transition formula. Or find the key parameters than describe an "intermediate state" completely.

The intermediate state here represents a similar question but with a smaller size.

For this question, we can try to define the state as dp[i][k], where i is the index of the elements and k is the number of subarrays.

The meaning of dp[i][k] is the maximum of average sum ending with the ith element with at most k subarrays.

Then the next step is to derive the formula to calculate the value of dp[i][k] using the previous dp with smaller values of i and k.

dp[i][k] = max(dp[x][k-1] + sum(num[x+1] to nums[i])/(i-x)), where x from 0 to i-1.

With the meaning of dp[x][k-1], the above formula is not hard to understand:

The right-hand side (rhs) enumerates all the possible ways to calculate dp[i][k], so we just need to pick up the maximum of it.

In the implementation, the boundary conditions are tricky. The thumb rule is to make sure the dp[i][k] is valid. For example, dp[i>0][0] is not valid, since there is no such case that we have non-zero elements in 0 subarray.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        // dp[i][j]: the max, ending at i, up to j subarray;
        // dp[i][j] = max(dp[d][j-1] + sum(nums[d+1], ..., nums[i])/(i-d))
        // where d from j-1 to i-1.
        double res = 0;
        int n = nums.size();
        vector<double> sums(n+1, 0);
        for(int i=0; i<n; ++i) sums[i+1] = sums[i] + nums[i];
        vector<vector<double>> dp(n+1, vector<double>(k+1, 0));
        for(int i=1; i<=n; ++i) {
            for(int j=min(i, k); j>=1; --j) {
                for(int d=max(j-1, 1); d<=i; ++d) {
                    double v = (j==1&&d>1) ? 0 : (dp[d-1][j-1] + (sums[i]-sums[d-1])/(i-d+1));
                    dp[i][j] = max(dp[i][j], v);
                }
            }
        }
        return dp[n][k];
    }
};

If do not like the boundary conditions of the above dp solution, we can try dfs + memoization.

We can start from the beginning of the array, and stop to make a subarray at any possible places.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<double>> memo(n, vector<double>(k, -1));
        return dfs(nums, 0, k-1, memo);
    }
private:
    double dfs(vector<int>& ns, int id, int k, vector<vector<double>>& memo) {
        // invalid ending since we cannot have more than k subarrays
        if(k<0 && id<ns.size()) return -2;
        if(id==ns.size()) return 0;
        if(memo[id][k] != -1) return memo[id][k];
        double t = 0, sum = 0;
        for(int i=id; i<ns.size(); ++i) {
            sum += ns[i];
            double v = dfs(ns, i+1, k-1, memo);
            if(v>-2) t = max(t, sum/(i-id+1) + v);
        }
        return memo[id][k] = t;
    }
};