stock alert system

stock_alert_system.cpp

/* stock alert system
Context: 
User want to get notification when one stock price goes above the threshold price, 
User may want to add many alerts and delete later.
Only consider when stock price rises.
*/

/* Idea:
Users may set the same price alert for one stock. Aggregate user ids by stock_id & price

Details:
Use unordered_map store stock_id to price_alert data
price_alert is a map store price to user_ids hashset

Time & Space complexity:
Suppose M stocks with D data, N users set A alerts

- addAlert:  Log(A)
- addStockData: Log(A)
*/

/* System Design:
1. How to handle many requests
[Method 1]
Hash stock_id and distribute to servers. We can use consistent hash to mapping stock id to server.

Pros
- Distribute 
Cons 
- Bring up or bring down servers may lose previous data
- May have hotspot issue when some popular stocks distributed to the same server

[Method 2, prefered]
Evenly distribute addAlert request and fan out addStockData to all servers
So every server can notify the users which already setup alert

e.g.
(addAlert 1) ---> [Server 1]
(addAlert 2) ---> [Server 2]
(addAlert 3) ---> [Server 3]

notify all servers, since they own part of the stock alerts for the same stock
(addStockData 1) ---> [Server 1]
(addStockData 1) ---> [Server 2]
(addStockData 1) ---> [Server 3]

Pros
- Distribute more evenly
Cons
- Increase network traffic (linear with server amount)
- Use more memory (every server may have same (stock_id, price) settings 

*/

#include <iostream>
#include <map>
#include <vector>
#include <unordered_map>
#include <unordered_set>

class StockAlertSystem {
public:
    void addAlert(std::string stock_id, int user_id, int price) {
        _stock_2_price_alerts[stock_id][price].insert(user_id);
    }
    
    // timestamp since useless in current design, ignore for now
    void addStockData(std::string stock_id, int price) {
        if (_stock_2_price_alerts.find(stock_id) == _stock_2_price_alerts.end()) {
            return;
        }
        
        // iterate by price, notify users whos price alert is lower than stock price 
        std::vector<std::map<int, std::unordered_set<int>>::iterator> to_delete_records;
        std::vector<int> alert_user_ids;
        for (auto it = _stock_2_price_alerts[stock_id].begin(); it != _stock_2_price_alerts[stock_id].end() && it->first <= price; it++) {
            to_delete_records.push_back(it);
            for (const int user_id: it->second) {
                alert_user_ids.push_back(user_id);
            }
        }
        
        for (auto delete_it:to_delete_records) {
            _stock_2_price_alerts[stock_id].erase(delete_it);
        }
        
        sentNotifications(stock_id, alert_user_ids);
    }
    
    void removeAlert(std::string stock_id, int user_id, int price) {
        _stock_2_price_alerts[stock_id][price].erase(user_id);
    }

private:
    void sentNotifications(const std::string& stock_id, const std::vector<int>& user_ids) {
        // send notifications
        for (const auto user_id:user_ids) {
            std::cout << "notification: " << user_id << std::endl;
        }
    }
    
    std::unordered_map<std::string, std::map<int, std::unordered_set<int>>> _stock_2_price_alerts;
};

int main()
{
    StockAlertSystem sys;
    
    // No alert
    std::cout << "Expect none" << std::endl;
    sys.addStockData("TSLA", 110);
    
    // add user1 alert
    sys.addAlert("TSLA", 1, 120);
    
    // user1 SHOULD NOT get notification when price is lower
    std::cout << "Expect none" << std::endl;
    sys.addStockData("TSLA", 110);
    
    // user1 SHOULD get notification when price is higher
    std::cout << "Expect 1" << std::endl;
    sys.addStockData("TSLA", 130);
    
    // user1 SHOULD NOT get notification when price is higher, since it is alerted already (scene 1)
    std::cout << "Expect none" << std::endl;
    sys.addStockData("TSLA", 130);
    
    // user1, user2 should be notified
    std::cout << "Expect 1,2" << std::endl;
    sys.addAlert("TSLA", 1, 120);
    sys.addAlert("TSLA", 2, 120);
    sys.addStockData("TSLA", 130);

    return 0;
}