PhonePe LLD Questions (Pendency System) - SDE2

Pendency System
Pendency is a system that is able to track counts of in-flight/in-progress entities.
The system is told when to start tracking a particular entity, and when to stop. And at any point the system can be asked how many entities are in-progress (or in-flight). The system is expected to give this count, as fast as possible

Problem Statement
You need to design a system that is able to track pending entities.
An entity is identified using a unique ID and a list of hierarchical tags.
There are 3 parts to this problem statement. startTracking, endTracking and getCounts.

When an entity is being tracked, you will be provided with an identifier for the entity, and a hierarchical tags associated with the entity to be tracked.

When counts are being retrieved, you will be provided with a partial list of tags, for which the accumulated counts need to be returned. This partial list of tags will follow the same hierarchy order as given in the input. (Should become clear with the example shown below).

The following is a guide for the interfaces you may have in your system.

An interface to start tracking the counts for the entity. (increment count by 1)
void startTracking (Integer id, List<String> hierarchicalTags);
where,
id = Identifier of the entity
hierarchicalTags = Tags that are properties of the entity. These tags are hierarchical in nature.

An interface to stop tracking the entity that is already being tracked (reduce count by 1)
void stopTracking (Integer id);
where,
id = Identifier of the transaction

An interface to get counts of entity being tracked, that match the tags supplied
Integer getCounts (List<String> tags);
where,
tags = a hierarchy of tags, for which counts are to be retrieved

Sample
The following is just a sample for your understanding.
Please remember: You are expected to write the system which mirrors production quality code, rather than just implementing these functions

The sample below shows the ability to track in-flight transactions happening across instruments, states and cities:

## Examples for tracking and getting counts

startTracking(1112, ["UPI", "Karnataka", "Bangalore"]); 
startTracking(2451, ["UPI", "Karnataka", "Mysore"]); 
startTracking(3421, ["UPI", "Rajasthan", "Jaipur"]); 
startTracking(1221, ["Wallet", "Karnataka", "Bangalore"]); 

getCounts(["UPI"])   # represents the counts of all pending "UPI" transactions
Output: 3
getCounts(["UPI", "Karnataka"])  # represents the counts of all pending "UPI" transactions in "Karnataka"
Output: 2
getCounts(["UPI", "Karnataka", "Bangalore"]) # represents the counts of all pending "UPI" transactions in "Karnataka" and "Bangalore"
Output: 1

getCounts(["Bangalore"]) # Does not represent a valid hierarchy in the sample
Output: 0

startTracking(4221, ["Wallet", "Karnataka", "Bangalore"]); 
stopTracking(1112); 
stopTracking(2451); 

getCounts(["UPI"])
Output: 1
getCounts(["Wallet"])
Output: 2
getCounts(["UPI", "Karnataka", "Bangalore"])
Output: 0

#include <bits/stdc++.h>
using namespace std;

// t = max no of tags in a request
// n = no of transactions

// 1] Map (Implemented) // Tree Based A
// Space Complexity: O[n*t]
// start = O[t] - increase count for each parent tag hierarchy.
// stop = O[t] - remove all counts corresponding to this id.
// get = O[t]  - Map will need to travserse through the tags internally.

void printStringVector(vector<string> tags) {
  for(int i = 0 ; i < tags.size() ; i++) {
    cout << tags[i];
    if(i != tags.size()-1) {
      printf("-");
    }
  }
}

class PendencySystem{
  public:
      void startTracking(int id, vector<string> hierarchicalTags) {}
      
      void stopTracking (int id) {}
      
      virtual int getCounts(vector<string> tags) {
        return 0;
      }
};

class Storage{
  public:
      virtual int getCountForHierarchy(vector<string> hierarchicalTags) {
      	return 0;
      }
      
      void incrementCountForHierarchy(vector<string> hierarchicalTags){}
	  
	  void decreaseCountForHierarchy(vector<string> hierarchicalTags){}
      
      virtual vector<string> getHierarchyForID(int id) {
      	return vector<string>();
      }
      
      void updateHierarchyForID(int id, vector<string> hierarchialTags){}
};

class InMemoryMap: public Storage {
	private:
	  map<int, vector<string>> idTagMapping;
	  map<vector<string>, int> countforTags;
	public:
		
	  InMemoryMap() {
  		idTagMapping.clear();
  		countforTags.clear();
	  } // Constructor
		
      int getCountForHierarchy(vector<string> hierarchicalTags) {
      	return countforTags[hierarchicalTags];
      }
      
      void incrementCountForHierarchy(vector<string> hierarchicalTags){
      	countforTags[hierarchicalTags] += 1;
      }
	  
	  void decreaseCountForHierarchy(vector<string> hierarchicalTags){
      	countforTags[hierarchicalTags] -= 1;
      }
      
      virtual vector<string> getHierarchyForID(int id) {
      	return idTagMapping[id];
      }
      
      void updateHierarchyForID(int id, vector<string> hierarchialTags){
      	idTagMapping[id] = hierarchialTags;
      }
};

class PhonePePendencySystem : public PendencySystem {
public:
  InMemoryMap db;
  
  PhonePePendencySystem(InMemoryMap psStorage) {
  	db = psStorage;
  } // Constructor
  
  void startTracking(int id, vector<string> hierarchicalTags) {
    vector<string> curTags;
    if(db.getHierarchyForID(id) != vector<string>{}) {
      // Repeated ID found.
      // An error can be thrown here.
      printf("startTracking(%d) => Duplicate request with ID\n", id);
      return;
    }
    db.updateHierarchyForID(id, hierarchicalTags);
    
    for(int i = 0 ; i < hierarchicalTags.size(); i++) {
      curTags.push_back(hierarchicalTags[i]);
	  db.incrementCountForHierarchy(curTags);
    }
  }

  void stopTracking (int id) {
    if(db.getHierarchyForID(id) == vector<string>{}) {
      // No request present with Given ID.
      // No processing required, warning can be thrown here.
      printf("stopTracking(%d) => No Request found with ID\n", id);
      return;
    }
    
    vector<string> hierarchicalTags = db.getHierarchyForID(id), curTags;
	db.updateHierarchyForID(id, vector<string>{});
    
    for(int i = 0 ; i < hierarchicalTags.size(); i++) {
      curTags.push_back(hierarchicalTags[i]);
	  db.decreaseCountForHierarchy(curTags);
    }
  }

  int getCounts(vector<string> tags) {
    int totalTransactionsWithTag = db.getCountForHierarchy(tags);
    
    cout << "getCounts(" ;
    printStringVector(tags) ;
    cout <<  ") = " << totalTransactionsWithTag << endl;
    
    return totalTransactionsWithTag;
  }
};

int main() {
  std::cout << "PhonePe Pendency System\n\n" ;
  InMemoryMap mapStorage = InMemoryMap();
  PhonePePendencySystem phonePePendencySystem = PhonePePendencySystem(mapStorage);
  
  phonePePendencySystem.startTracking(1112, vector<string>{"UPI", "Karnataka", "Bangalore"});
  phonePePendencySystem.startTracking(2451, vector<string>{"UPI", "Karnataka", "Mysore"}); 
  phonePePendencySystem.startTracking(3421, vector<string>{"UPI", "Rajasthan", "Jaipur"}); 
  phonePePendencySystem.startTracking(1221, vector<string>{"Wallet", "Karnataka", "Bangalore"}); 

  phonePePendencySystem.getCounts(vector<string>{"UPI"});
  phonePePendencySystem.getCounts(vector<string>{"UPI", "Karnataka"});
  phonePePendencySystem.getCounts(vector<string>{"UPI", "Karnataka", "Bangalore"});
  
  phonePePendencySystem.getCounts(vector<string>{"Bangalore"});
  
  phonePePendencySystem.startTracking(4221, vector<string>{"Wallet", "Karnataka", "Bangalore"}); 
  phonePePendencySystem.stopTracking(1112);
  phonePePendencySystem.stopTracking(2451);

  phonePePendencySystem.getCounts(vector<string>{"UPI"});
  phonePePendencySystem.getCounts(vector<string>{"Wallet"});
  phonePePendencySystem.getCounts(vector<string>{"UPI", "Karnataka", "Bangalore"});

  return 0;
}