Lock-Free Concurrent Payment Tree
Build a lock-free M-ary tree payment engine in C++ using atomic CAS operations.
Introduction
30 Second Summary
Every time you tap your phone to pay for coffee, your payment races through a tree of gateways, processors, and banks. When thousands of people pay at the same instant, those payments compete for the same routing paths. Something has to prevent collisions without slowing everything to a crawl.
In this project, you will build a C++ payment gateway orchestration engine that solves this exact concurrency problem using lock-free atomic operations. You will implement the same "Tree of Space" locking system that Juspay tests in their hackathon interviews, then deploy it live with a real-time visualization dashboard.
What You'll Build
A production-grade concurrent tree system in C++ that models payment routing, with lock-free thread safety using atomic CAS operations, a web-based visualization frontend, and a live deployment on AWS EC2 and GitHub Pages.
By the end of this project, you'll have:
- A fully functional M-ary payment gateway tree with Lock, Unlock, and UpgradeLock operations achieving O(log_m N) time complexity.
- A lock-free thread-safe version using only std::atomic and CAS operations (no mutex, no semaphore) that passes concurrent stress tests with 16+ threads.
- A live deployed system with an EC2 backend, a GitHub Pages frontend dashboard built with D3.js, professional documentation, and interview-ready talking points.
- Secret Mission: Implement a lock-free priority transaction queue with fairness guarantees and visualize contention hotspots as a heatmap overlay on the tree dashboard.
Are there any prerequisites?
You need basic C++ knowledge: variables, functions, classes, and pointers. No prior concurrency or tree data structure experience is required. This project teaches lock-free programming, atomic operations, and tree algorithms from scratch.
Before We Start
You're about to build a payment gateway orchestration engine in C++. This system solves the exact "Tree of Space" locking problem that Juspay uses in their hackathon interviews.
Before writing any code, you need a working C++ toolchain, version control, and a project structure. This step gets all of those in place so you can focus purely on the tree and concurrency logic from Step 2 onwards.
In this step, get ready to:
- Install and verify g++ with C++17 and threading support.
- Install Git and configure your identity.
- Create the project directory, download cpp-httplib, and write the Makefile.
Install and verify g++
The project uses C++17 features and POSIX threading. You need a compiler that supports both.
- Check whether g++ is already installed by running this command in your terminal:
g++ --version✔️ I see version 11 or higher
Your compiler supports C++17 by default. You're ready to move on.
ⓧ I see an older version
You need GCC 11 or higher for default C++17 support. Follow the instructions for your operating system below.
macOS
On macOS, the g++ command is actually Apple Clang, which fully supports C++17. If your version is outdated, reinstall the command line tools.
- Update your Xcode Command Line Tools by running:
xcode-select --installFollow the on-screen prompt to complete the installation. Once done, run g++ --version again to confirm.
Windows
On Windows, install GCC through MSYS2.
- Download and install MSYS2 from msys2.org.
- Open the MSYS2 UCRT64 terminal from your Start menu.
- Install the GCC toolchain by running:
pacman -S mingw-w64-ucrt-x86_64-gcc- Add C:\msys64\ucrt64\bin to your Windows System PATH so that g++ is available in any terminal.
- Open a new terminal and run g++ --version to confirm it shows GCC 11 or higher.
ⓧ Command not found
g++ is not installed. Follow the instructions for your operating system below.
macOS
- Install the Xcode Command Line Tools by running:
xcode-select --installA dialog will appear asking you to confirm the installation. Click Install and wait for it to complete. This provides Apple Clang (which responds to the g++ command) with full C++17 support.
- After installation, confirm by running g++ --version again.
Windows
- Download and install MSYS2 from msys2.org.
- Open the MSYS2 UCRT64 terminal from your Start menu.
- Install the GCC toolchain by running:
pacman -S mingw-w64-ucrt-x86_64-gcc- Add C:\msys64\ucrt64\bin to your Windows System PATH.
- Open a new terminal and run g++ --version to verify the installation shows GCC 11 or higher.
Now verify that threading support works. This project uses -pthread for multithreading.
- Confirm threading support by running this quick compilation test:
echo '#include <thread>
int main() { return 0; }' | g++ -std=c++17 -pthread -x c++ - -o /dev/null && echo "Threading OK"What does this command do?
This pipes a tiny C++ program (that includes the <thread> header) into g++ and compiles it with -std=c++17 and -pthread. If it prints "Threading OK", your compiler handles both features correctly.
Seeing an error about threads?
On some Linux distributions, you may need to install the threading library separately. Try sudo apt install libpthread-stubs0-dev on Debian/Ubuntu. On macOS, threading is built in and should work out of the box.
Help me fix my g++ threading support issue
Install Git and configure your identity
You'll use Git throughout the project to track your progress with meaningful commits. Interviewers look at commit history to understand your development process.
- Check whether Git is already installed by running:
git --version✔️ I see a version number
Git is installed. Move on to configuring your identity below.
ⓧ Command not found
macOS
- If you installed Xcode Command Line Tools earlier, Git is already included. Run git --version again.
- If it's still not found, install it with:
xcode-select --installWindows
- Download Git from git-scm.com.
- Run the installer and accept the default settings.
- Open a new terminal and run git --version to confirm.
- Configure your Git identity by running these commands (replace the placeholder values with your actual name and email):
git config --global user.name "Your Name"
git config --global user.email "your.email@example.com"Why configure Git identity?
Every Git commit records who made it. Setting your name and email now ensures your commit history looks professional on GitHub. Use the same email associated with your GitHub account.
- If you don't have a GitHub account yet, create one at github.com. You'll need it for hosting your repository and deploying the frontend later.
Create the project directory, download cpp-httplib, and write the Makefile
Now set up the project folder structure. The engine needs separate directories for source code, headers, the web frontend, and documentation.
- Open your code editor. Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
- Type VS Code and press Enter to open it.
- Open a terminal inside VS Code by pressing Ctrl+` (backtick key, same shortcut on macOS and Windows).
- Move to your Desktop by running this command:
cd ~/Desktop- Create your project folder with all subdirectories by running these commands:
mkdir -p payment-gateway-engine/{src,include,frontend,docs,build}
cd payment-gateway-engine- Confirm the directories exist by running:
lsYou should see build, docs, frontend, include, and src listed in the output.
What is each directory for?
- src/ holds your C++ implementation files (.cpp).
- include/ holds your header files (.h) with class declarations.
- frontend/ holds the HTML/JS visualization dashboard.
- docs/ holds architecture docs and the GitHub Pages deployment.
- build/ holds compiled object files (kept out of source control).
Next, download the HTTP library. cpp-httplib is a single-header C++ library that gives your engine a web API with zero build complexity.
- Download httplib.h into your include/ directory by running:
curl -o include/httplib.h https://raw.githubusercontent.com/yhirose/cpp-httplib/v0.46.0/httplib.hWhat is cpp-httplib?
It's a header-only HTTP server and client library for C++. "Header-only" means you just include the single httplib.h file in your code. No separate compilation or linking step needed for the library itself.
- Verify the download succeeded by running:
ls include/httplib.hYou should see include/httplib.h printed. If you see "No such file or directory", re-run the curl command above.
Now create the Makefile. This tells the compiler how to build your entire project with a single command.
- Create a file called Makefile in the root of your payment-gateway-engine folder. In VS Code, click File then New File.
- Name the file Makefile (capital M, no extension).
- Paste the following code into Makefile:
CXX = g++
CXXFLAGS = -std=c++17 -pthread -O2 -Wall -Wextra
LDFLAGS = -pthread -latomic
SRC_DIR = src
INC_DIR = include
BUILD_DIR = build
SOURCES = $(SRC_DIR)/main.cpp $(SRC_DIR)/tree.cpp $(SRC_DIR)/atomic_tree.cpp $(SRC_DIR)/simulator.cpp $(SRC_DIR)/server.cpp
OBJECTS = $(SOURCES:$(SRC_DIR)/%.cpp=$(BUILD_DIR)/%.o)
TARGET = payment_engine
all: $(BUILD_DIR) $(TARGET)
$(BUILD_DIR):
mkdir -p $(BUILD_DIR)
$(TARGET): $(OBJECTS)
$(CXX) $(OBJECTS) -o $(TARGET) $(LDFLAGS)
$(BUILD_DIR)/%.o: $(SRC_DIR)/%.cpp
$(CXX) $(CXXFLAGS) -I$(INC_DIR) -c $< -o $@
clean:
rm -rf $(BUILD_DIR) $(TARGET)
run: $(TARGET)
./$(TARGET)
.PHONY: all clean runWhat does this Makefile do?
- -std=c++17 enables C++17 features like structured bindings and std::optional.
- -pthread enables POSIX threads for concurrent transaction simulation.
- -latomic links the atomic operations library, required on some platforms for std::atomic operations.
- -O2 turns on compiler optimizations so your lock-free code runs at realistic speeds during stress tests.
- -Wall -Wextra enables warnings that catch common mistakes before they become runtime bugs.
- Save Makefile.
Makefile indentation errors?
Makefiles require real tab characters for indentation, not spaces. If you see an error like "missing separator", your editor may have converted tabs to spaces.
In VS Code, look at the bottom status bar. Click where it says Spaces: 4 and switch to Indent Using Tabs for this file.
Help me fix my Makefile indentation
Finally, note the D3.js CDN URL for later use in the frontend. You'll use https://d3js.org/d3.v7.min.js when building the visualization dashboard. No download needed now.
✔️ Awesome, I've got everything!
Great. Double check you've saved your Makefile.
ⓧ I'd like to double check the full code
CXX = g++
CXXFLAGS = -std=c++17 -pthread -O2 -Wall -Wextra
LDFLAGS = -pthread -latomic
SRC_DIR = src
INC_DIR = include
BUILD_DIR = build
SOURCES = $(SRC_DIR)/main.cpp $(SRC_DIR)/tree.cpp $(SRC_DIR)/atomic_tree.cpp $(SRC_DIR)/simulator.cpp $(SRC_DIR)/server.cpp
OBJECTS = $(SOURCES:$(SRC_DIR)/%.cpp=$(BUILD_DIR)/%.o)
TARGET = payment_engine
all: $(BUILD_DIR) $(TARGET)
$(BUILD_DIR):
mkdir -p $(BUILD_DIR)
$(TARGET): $(OBJECTS)
$(CXX) $(OBJECTS) -o $(TARGET) $(LDFLAGS)
$(BUILD_DIR)/%.o: $(SRC_DIR)/%.cpp
$(CXX) $(CXXFLAGS) -I$(INC_DIR) -c $< -o $@
clean:
rm -rf $(BUILD_DIR) $(TARGET)
run: $(TARGET)
./$(TARGET)
.PHONY: all clean runYour development environment is ready. Next up, you'll initialize Git, write your README with an architecture diagram, and push your project skeleton to GitHub.
Scaffold the Project and Set Up Version Control
Your C++ toolchain is installed, your project folders are created, and your Makefile is ready. Now it's time to put everything under version control so every change you make from here on is tracked and recoverable.
A clean initial commit establishes the project's foundation on GitHub. This gives you a safety net to roll back mistakes, and it builds the professional commit history that interviewers look at when evaluating your repository.
In this step, get ready to:
- Initialize a Git repository with a .gitignore file.
- Create a README with a Mermaid architecture diagram.
- Commit and push the initial project skeleton to GitHub.
Initialize the Git repository
Git needs to be told which folder to track. Initializing a repository creates a hidden .git folder that stores your project's entire change history.
- In your terminal, make sure you're inside the payment-gateway-engine folder, then initialize the repository by running this command:
git initYou should see a message saying the repository was initialized.
Not every file belongs in version control. Build artifacts and OS-generated files are noise that clutters your repository and confuses collaborators.
- Create a .gitignore file in the project root with the following content:
build/
payment_engine
*.o
*.d
.DS_StoreWhat does this file do?
Each line tells Git to ignore matching files or folders. build/ excludes compiled object files. payment_engine excludes the final binary.
The wildcard patterns *.o and *.d catch any stray object or dependency files. .DS_Store is a macOS metadata file that has no place in a shared repo.
- Save .gitignore.
- Verify Git recognizes it by running:
git statusYou should see .gitignore and Makefile listed as untracked files. The build/ directory should NOT appear.
Seeing build/ in the untracked list?
Double-check that .gitignore is saved in the project root (the same folder as your Makefile). If the file is in the wrong directory, Git won't find it.
Also confirm the first line of the file is exactly build/ with the trailing slash.
help me troubleshoot why my .gitignore isn't working
✔️ Awesome, I've got everything!
Great. Make sure .gitignore is saved before moving on.
ⓧ I'd like to double check the full code
build/
payment_engine
*.o
*.d
.DS_StoreCreate the README with an architecture diagram
A README is the first thing anyone sees when they visit your GitHub repository. Including an architecture diagram up front signals that you think in systems, not just code.
GitHub renders Mermaid diagrams natively inside markdown files. This means your payment tree hierarchy shows up as a visual graph without any plugins or external tools.
- Create a README.md file in the project root with the following content:
# Payment Gateway Orchestration Engine
A production-grade C++ lock-free concurrent tree system modeling Juspay's 'Tree of Space' hackathon problem as a real payment routing system.
## Architecture
```mermaid
graph TD
A[PaymentSystem] --> B[Cards]
A --> C[UPI]
A --> D[Wallets]
B --> E[Visa]
B --> F[Mastercard]
B --> G[RuPay]
C --> H[GPay]
C --> I[PhonePe]
C --> J[BHIM]
D --> K[Paytm]
D --> L[AmazonPay]
```
## Build
```bash
make
./payment_engine
```What does this README cover?
The title and description immediately tell visitors what the project is. The Mermaid diagram under ## Architecture shows the payment tree hierarchy that the locking system will operate on.
The ## Build section gives anyone cloning the repo the two commands they need to compile and run the project.
- Save README.md.
✔️ Awesome, I've got everything!
Great. Make sure README.md is saved before moving on.
ⓧ I'd like to double check the full code
# Payment Gateway Orchestration Engine
A production-grade C++ lock-free concurrent tree system modeling Juspay's 'Tree of Space' hackathon problem as a real payment routing system.
## Architecture
```mermaid
graph TD
A[PaymentSystem] --> B[Cards]
A --> C[UPI]
A --> D[Wallets]
B --> E[Visa]
B --> F[Mastercard]
B --> G[RuPay]
C --> H[GPay]
C --> I[PhonePe]
C --> J[BHIM]
D --> K[Paytm]
D --> L[AmazonPay]
```
## Build
```bash
make
./payment_engine
```Commit and push to GitHub
With the project files in place, it's time to make your first commit and push everything to a remote repository on GitHub.
- Move the httplib.h file you downloaded in the previous step into the include/ directory by running:
mv httplib.h include/httplib.h- Confirm it landed in the right place by running:
ls include/You should see httplib.h in the output.
Git does not track empty directories. To make sure src/, frontend/, and docs/ appear in your repo, you need a placeholder file in each one.
- Create placeholder files so Git tracks the empty directories by running:
touch src/.gitkeep frontend/.gitkeep docs/.gitkeep- Stage all project files by running:
git add .- Create your initial commit by running:
git commit -m "Initial project scaffold with tree structure and build system"What did this commit include?
This commit captures your Makefile, .gitignore, README.md, the cpp-httplib header, and the empty directory placeholders. It forms the project's foundation that all future commits build on.
Now you need a remote repository on GitHub to push this commit to.
- Open GitHub in your browser and click the + icon in the top-right corner.
- Select New repository.
- Enter payment-gateway-engine as the repository name.
- Leave the repository set to Public.
- Do NOT check any of the initialization boxes (README, .gitignore, or license). You already have these locally.
- Click Create repository.
GitHub shows you a set of commands for an existing repository. You only need the remote and push commands.
- Connect your local repo to GitHub by running:
git remote add origin [[YOUR_GITHUB_URL="https://github.com/YOUR_USERNAME/payment-gateway-engine.git"]]- Rename your default branch to main and push by running:
git branch -M main
git push -u origin main- Refresh your GitHub repository page in the browser.
- You should see your README.md rendered with the Mermaid architecture diagram displayed as a visual tree graph.
Push rejected or authentication failed?
If you see an authentication error, GitHub no longer accepts passwords for git push over HTTPS. Generate a personal access token from Settings > Developer settings > Personal access tokens and use it as your password when prompted.
If the push is rejected because the remote already has commits, you may have accidentally initialized the repo with a README on GitHub. Delete the remote repo, recreate it empty, and try again.
help me fix a git push authentication or rejection error
Your project foundation is committed and live on GitHub. Next, you'll build the M-ary tree data structure that forms the backbone of the payment routing system.
Build the M-ary Tree Data Structure
Payment gateways route transactions through a hierarchy. A card payment might travel from a top-level Cards category down to Visa, then to a specific bank like HDFC. This hierarchy is a tree, and in Juspay's hackathon, it's called the "Tree of Space."
In this step, you'll build the M-ary tree data structure that represents this payment routing hierarchy. Each node can have up to m children, and every node carries metadata that will power the locking system in later steps.
In this step, get ready to:
- Define the TreeNode struct with lock metadata fields.
- Implement the PaymentTree class for constructing and querying the tree.
- Build the payment gateway hierarchy from root to leaf banks.
Implement the TreeNode struct and PaymentTree class
Every node in the tree needs to know its name, its parent, its children, and whether it's currently locked. These metadata fields are what make the locking algorithm efficient later.
- Create a new file called tree_node.h inside your include/ directory.
- Add the TreeNode struct with its fields by pasting this code:
#ifndef TREE_NODE_H
#define TREE_NODE_H
#include <string>
#include <vector>
#include <unordered_map>
#include <atomic>
struct TreeNode {
std::string name;
TreeNode* parent;
std::vector<TreeNode*> children;
bool isLocked;
int lockedBy;
int ancestorLockedCount;
int descendantLockedCount;
TreeNode(const std::string& nodeName, TreeNode* parentNode = nullptr)
: name(nodeName), parent(parentNode), isLocked(false),
lockedBy(-1), ancestorLockedCount(0), descendantLockedCount(0) {}
};What does this struct do?
Each TreeNode stores the data needed for the locking algorithm:
- parent lets us walk up the tree to check ancestor locks.
- children lets us walk down the tree to check descendant locks.
- ancestorLockedCount tracks how many ancestors above this node are locked. If it's greater than 0, this node cannot be locked.
- descendantLockedCount tracks how many descendants below are locked. This avoids a full subtree traversal when checking lock eligibility.
- Below the TreeNode struct (but before #endif), add the PaymentTree class declaration:
class PaymentTree {
public:
PaymentTree(int childrenPerNode);
~PaymentTree();
void addNode(const std::string& name, const std::string& parentName = "");
bool lock(const std::string& nodeName, int userId);
bool unlock(const std::string& nodeName, int userId);
bool upgradeLock(const std::string& nodeName, int userId);
TreeNode* getNode(const std::string& name);
std::string toJson() const;
private:
TreeNode* root;
int m;
std::unordered_map<std::string, TreeNode*> nodeMap;
void informAncestors(TreeNode* node, int delta);
void informDescendants(TreeNode* node, int delta);
void collectLockedDescendants(TreeNode* node, int userId, std::vector<TreeNode*>& result, bool& valid);
void deleteTree(TreeNode* node);
};
#endifWhat does this class declare?
PaymentTree is the public interface for building and querying the tree. The nodeMap is a hash map that gives O(1) lookup of any node by name, instead of traversing the tree each time.
The lock, unlock, and upgradeLock methods are declared here but won't be implemented until the next step.
- Save include/tree_node.h.
✔️ Awesome, I've got everything!
Great. Double check you've saved your file before continuing.
ⓧ I'd like to double check the full code
#ifndef TREE_NODE_H
#define TREE_NODE_H
#include <string>
#include <vector>
#include <unordered_map>
#include <atomic>
struct TreeNode {
std::string name;
TreeNode* parent;
std::vector<TreeNode*> children;
bool isLocked;
int lockedBy;
int ancestorLockedCount;
int descendantLockedCount;
TreeNode(const std::string& nodeName, TreeNode* parentNode = nullptr)
: name(nodeName), parent(parentNode), isLocked(false),
lockedBy(-1), ancestorLockedCount(0), descendantLockedCount(0) {}
};
class PaymentTree {
public:
PaymentTree(int childrenPerNode);
~PaymentTree();
void addNode(const std::string& name, const std::string& parentName = "");
bool lock(const std::string& nodeName, int userId);
bool unlock(const std::string& nodeName, int userId);
bool upgradeLock(const std::string& nodeName, int userId);
TreeNode* getNode(const std::string& name);
std::string toJson() const;
private:
TreeNode* root;
int m;
std::unordered_map<std::string, TreeNode*> nodeMap;
void informAncestors(TreeNode* node, int delta);
void informDescendants(TreeNode* node, int delta);
void collectLockedDescendants(TreeNode* node, int userId, std::vector<TreeNode*>& result, bool& valid);
void deleteTree(TreeNode* node);
};
#endifImplement tree construction in src/tree.cpp
The header declares the interface. Now you need the implementation that actually builds nodes and connects them into a tree.
- Create a new file called tree.cpp inside your src/ directory.
- Add the constructor, destructor, and tree cleanup logic by pasting this code:
#include "tree_node.h"
// Constructor: store the branching factor (max children per node)
PaymentTree::PaymentTree(int childrenPerNode) : root(nullptr), m(childrenPerNode) {}
// Destructor: recursively free all heap-allocated nodes
PaymentTree::~PaymentTree() {
deleteTree(root);
}
// Recursively delete a node and all its descendants
void PaymentTree::deleteTree(TreeNode* node) {
if (!node) return;
for (TreeNode* child : node->children) {
deleteTree(child);
}
delete node;
}What does this code do?
The constructor stores the branching factor m (how many children each node can have) and starts with an empty tree. The destructor calls deleteTree to walk through every node and free the memory.
Since each TreeNode is heap-allocated with new, we must delete every one when the tree is destroyed. The recursive approach visits children first (post-order), so no child is left dangling.
- Below the deleteTree function, add the addNode implementation:
// Add a new node to the tree under the specified parent
void PaymentTree::addNode(const std::string& name, const std::string& parentName) {
if (parentName.empty()) {
// No parent means this is the root node
root = new TreeNode(name);
nodeMap[name] = root;
return;
}
// Find the parent node and attach the new child
TreeNode* parent = getNode(parentName);
if (!parent) return;
TreeNode* newNode = new TreeNode(name, parent);
parent->children.push_back(newNode);
nodeMap[name] = newNode;
}What does addNode do?
addNode handles two cases. If parentName is empty, the node becomes the root. Otherwise, it finds the parent by name, creates the new child with a back-pointer to its parent, and registers it in the nodeMap for O(1) future lookups.
This is how you'll build the full payment hierarchy. Call addNode("PaymentSystem") first (empty parent creates root), then addNode("Cards", "PaymentSystem") to attach children.
Implement node lookup and compile the tree
The unordered_map gives you O(1) node access by name. Without it, every operation would need to traverse the tree from the root, making lock checks far slower.
- Below addNode in src/tree.cpp, add the getNode implementation and stub methods:
// Look up any node by name in O(1) using the hash map
TreeNode* PaymentTree::getNode(const std::string& name) {
auto it = nodeMap.find(name);
if (it != nodeMap.end()) {
return it->second;
}
return nullptr;
}
// Stub implementations - will be completed in the next step
bool PaymentTree::lock(const std::string& /*nodeName*/, int /*userId*/) {
return false;
}
bool PaymentTree::unlock(const std::string& /*nodeName*/, int /*userId*/) {
return false;
}
bool PaymentTree::upgradeLock(const std::string& /*nodeName*/, int /*userId*/) {
return false;
}
std::string PaymentTree::toJson() const {
return "{}";
}
void PaymentTree::informAncestors(TreeNode* /*node*/, int /*delta*/) {}
void PaymentTree::informDescendants(TreeNode* /*node*/, int /*delta*/) {}
void PaymentTree::collectLockedDescendants(TreeNode* /*node*/, int /*userId*/,
std::vector<TreeNode*>& /*result*/, bool& /*valid*/) {}Why are there stub methods?
The header declares all the methods the class will eventually have. The compiler requires every declared method to have a definition somewhere. These empty stubs satisfy the compiler while you focus on the tree structure first.
The commented-out parameter names (/*nodeName*/) tell the compiler you intentionally aren't using them yet. This prevents "unused parameter" warnings.
- Save src/tree.cpp.
- Verify the file compiles by running this command:
g++ -std=c++17 -c src/tree.cpp -Iinclude -o build/tree.oYou should see no output if the compilation succeeds. A new file build/tree.o now exists.
- Confirm the object file was created by running:
ls build/You should see tree.o in the output.
Seeing compilation errors?
- If you see "No such file or directory" for the include, make sure you're running the command from your project root folder (the one containing src/ and include/).
- If you see "undefined reference" errors, that's a linker error. Make sure you used the -c flag, which compiles without linking.
- If build/ doesn't exist yet, create it first with mkdir -p build.
Help me debug my tree.cpp compilation error
- Commit your progress by running these commands:
git add include/tree_node.h src/tree.cpp
git commit -m "Add M-ary tree data structure with TreeNode and PaymentTree"
git push✔️ Awesome, I've got everything!
Great. Make sure both files are saved and committed before moving on.
ⓧ I'd like to double check the full code
#ifndef TREE_NODE_H
#define TREE_NODE_H
#include <string>
#include <vector>
#include <unordered_map>
#include <atomic>
struct TreeNode {
std::string name;
TreeNode* parent;
std::vector<TreeNode*> children;
bool isLocked;
int lockedBy;
int ancestorLockedCount;
int descendantLockedCount;
TreeNode(const std::string& nodeName, TreeNode* parentNode = nullptr)
: name(nodeName), parent(parentNode), isLocked(false),
lockedBy(-1), ancestorLockedCount(0), descendantLockedCount(0) {}
};
class PaymentTree {
public:
PaymentTree(int childrenPerNode);
~PaymentTree();
void addNode(const std::string& name, const std::string& parentName = "");
bool lock(const std::string& nodeName, int userId);
bool unlock(const std::string& nodeName, int userId);
bool upgradeLock(const std::string& nodeName, int userId);
TreeNode* getNode(const std::string& name);
std::string toJson() const;
private:
TreeNode* root;
int m;
std::unordered_map<std::string, TreeNode*> nodeMap;
void informAncestors(TreeNode* node, int delta);
void informDescendants(TreeNode* node, int delta);
void collectLockedDescendants(TreeNode* node, int userId, std::vector<TreeNode*>& result, bool& valid);
void deleteTree(TreeNode* node);
};
#endif#include "tree_node.h"
// Constructor: store the branching factor (max children per node)
PaymentTree::PaymentTree(int childrenPerNode) : root(nullptr), m(childrenPerNode) {}
// Destructor: recursively free all heap-allocated nodes
PaymentTree::~PaymentTree() {
deleteTree(root);
}
// Recursively delete a node and all its descendants
void PaymentTree::deleteTree(TreeNode* node) {
if (!node) return;
for (TreeNode* child : node->children) {
deleteTree(child);
}
delete node;
}
// Add a new node to the tree under the specified parent
void PaymentTree::addNode(const std::string& name, const std::string& parentName) {
if (parentName.empty()) {
// No parent means this is the root node
root = new TreeNode(name);
nodeMap[name] = root;
return;
}
// Find the parent node and attach the new child
TreeNode* parent = getNode(parentName);
if (!parent) return;
TreeNode* newNode = new TreeNode(name, parent);
parent->children.push_back(newNode);
nodeMap[name] = newNode;
}
// Look up any node by name in O(1) using the hash map
TreeNode* PaymentTree::getNode(const std::string& name) {
auto it = nodeMap.find(name);
if (it != nodeMap.end()) {
return it->second;
}
return nullptr;
}
// Stub implementations - will be completed in the next step
bool PaymentTree::lock(const std::string& /*nodeName*/, int /*userId*/) {
return false;
}
bool PaymentTree::unlock(const std::string& /*nodeName*/, int /*userId*/) {
return false;
}
bool PaymentTree::upgradeLock(const std::string& /*nodeName*/, int /*userId*/) {
return false;
}
std::string PaymentTree::toJson() const {
return "{}";
}
void PaymentTree::informAncestors(TreeNode* /*node*/, int /*delta*/) {}
void PaymentTree::informDescendants(TreeNode* /*node*/, int /*delta*/) {}
void PaymentTree::collectLockedDescendants(TreeNode* /*node*/, int /*userId*/,
std::vector<TreeNode*>& /*result*/, bool& /*valid*/) {}Your M-ary tree structure is complete. Next up, you'll implement the lock operation that makes concurrent transactions compete for routing paths through this tree.
Implement Lock, Unlock, and UpgradeLock Operations
Your tree can represent a payment gateway hierarchy, but it has no way to control access to individual nodes. The three core operations (Lock, Unlock, UpgradeLock) are what make this tree useful for real payment routing.
These operations solve a fundamental problem: when multiple transactions compete for the same gateway, you need a way to grant exclusive access while preventing conflicts across ancestor and descendant nodes. This is the exact logic Juspay tests in their hackathon Part A.
In this step, get ready to:
- Implement the lock operation with O(log_m N) time complexity using metadata counters.
- Implement unlock and upgradeLock operations with full conflict detection.
- Write and run unit tests validating correctness and edge cases.
Implement the lock operation and helper functions
The lock operation needs to check three conditions before granting access to a node: the node itself is not locked, no ancestor is locked, and no descendant is locked. Instead of traversing the entire tree for each check, you use two metadata counters to achieve O(log_m N) time complexity.
Why metadata counters instead of full traversal?
Each node stores ancestorLockedCount (how many ancestors above are locked) and descendantLockedCount (how many descendants below are locked). Checking these counters is O(1) instead of walking the whole subtree.
Every time you lock or unlock a node, you propagate the change up and down the tree by adjusting these counters. The propagation cost is O(log_m N) up the parent chain, which keeps overall lock time efficient.
- In src/tree.cpp, add the following two helper functions below your existing getNode implementation:
void PaymentTree::informAncestors(TreeNode* node, int delta) {
// Walk up the parent chain, adjusting each ancestor's
// descendantLockedCount so they know a descendant changed state
TreeNode* current = node->parent;
while (current != nullptr) {
current->descendantLockedCount += delta;
current = current->parent;
}
}
void PaymentTree::informDescendants(TreeNode* node, int delta) {
// Recursively visit all children, adjusting their
// ancestorLockedCount so they know an ancestor changed state
for (TreeNode* child : node->children) {
child->ancestorLockedCount += delta;
informDescendants(child, delta);
}
}What does this code do?
- informAncestors walks UP the parent chain. When you lock a node, you call this with delta = 1 so every ancestor increments its descendantLockedCount. When you unlock, you pass -1.
- informDescendants walks DOWN to every child recursively. It adjusts ancestorLockedCount so descendants know whether any ancestor above them is locked.
- Save src/tree.cpp.
You will not see a visible change yet. The next chunk uses these helpers in the lock function.
- Below the informDescendants function you just added, add the lock implementation:
bool PaymentTree::lock(const std::string& nodeName, int userId) {
TreeNode* node = getNode(nodeName);
if (node == nullptr) return false;
// Check 1: node must not already be locked
if (node->isLocked) return false;
// Check 2: no ancestor can be locked (O(1) check using counter)
if (node->ancestorLockedCount > 0) return false;
// Check 3: no descendant can be locked (O(1) check using counter)
if (node->descendantLockedCount > 0) return false;
// All checks passed - set the lock state
node->isLocked = true;
node->lockedBy = userId;
// Propagate metadata: tell ancestors and descendants about this lock
informAncestors(node, 1);
informDescendants(node, 1);
return true;
}Why is this O(log_m N)?
The three condition checks are each O(1). They read a single integer rather than traversing the tree.
The informAncestors call walks from the node to the root. In a balanced M-ary tree with N nodes, the height is log_m(N). The informDescendants call visits all children, but since you already verified descendantLockedCount == 0, the subtree has zero locked nodes and the propagation cost stays bounded.
- Save src/tree.cpp.
You will not see a visible change yet. The next substep adds unlock and upgradeLock so you can test the full cycle.
Seeing a compile error?
Make sure your informAncestors and informDescendants functions appear BEFORE the lock function in src/tree.cpp. The compiler needs to see them before they are called.
Also verify the function signatures match the declarations in include/tree_node.h exactly.
help me fix a compile error in my lock function
Implement unlock and upgradeLock operations
The unlock operation reverses a lock. It validates that the requesting user actually owns the lock, then clears the state and decrements the metadata counters.
- Below the lock function, add the unlock implementation:
bool PaymentTree::unlock(const std::string& nodeName, int userId) {
TreeNode* node = getNode(nodeName);
if (node == nullptr) return false;
// Only the user who locked it can unlock it
if (!node->isLocked) return false;
if (node->lockedBy != userId) return false;
// Clear the lock state
node->isLocked = false;
node->lockedBy = -1;
// Reverse the metadata propagation
informAncestors(node, -1);
informDescendants(node, -1);
return true;
}What does this code do?
unlock is the mirror image of lock. It validates ownership (rejects if lockedBy != userId), clears the lock fields, and calls informAncestors and informDescendants with -1 to decrement the counters.
- Save src/tree.cpp.
You will not see a visible change yet. The upgradeLock function below completes the trio of operations.
The upgradeLock operation is the most complex. It lets a user who has locked multiple descendants consolidate those locks into a single lock on a higher node. This is useful when a user has locked individual banks (like HDFC and ICICI) and wants to lock the entire Visa gateway instead.
- Below unlock, add the collectLockedDescendants helper and upgradeLock function:
void PaymentTree::collectLockedDescendants(TreeNode* node, int userId,
std::vector<TreeNode*>& result, bool& valid) {
// Recursively find all locked descendants and verify they
// all belong to the same userId
for (TreeNode* child : node->children) {
if (child->isLocked) {
if (child->lockedBy != userId) {
valid = false;
return;
}
result.push_back(child);
}
collectLockedDescendants(child, userId, result, valid);
if (!valid) return;
}
}
bool PaymentTree::upgradeLock(const std::string& nodeName, int userId) {
TreeNode* node = getNode(nodeName);
if (node == nullptr) return false;
// Target node must not already be locked
if (node->isLocked) return false;
// No ancestor can be locked
if (node->ancestorLockedCount > 0) return false;
// Must have at least one locked descendant to upgrade from
if (node->descendantLockedCount == 0) return false;
// Collect all locked descendants and verify they belong to this user
std::vector<TreeNode*> lockedDescendants;
bool valid = true;
collectLockedDescendants(node, userId, lockedDescendants, valid);
if (!valid) return false;
// Unlock all descendants (consolidating into the parent)
for (TreeNode* desc : lockedDescendants) {
desc->isLocked = false;
desc->lockedBy = -1;
informAncestors(desc, -1);
informDescendants(desc, -1);
}
// Lock the target node
node->isLocked = true;
node->lockedBy = userId;
informAncestors(node, 1);
informDescendants(node, 1);
return true;
}What does upgradeLock do?
upgradeLock is a composite operation. It atomically (in the single-threaded sense) unlocks multiple descendant nodes and locks a higher ancestor instead.
- collectLockedDescendants traverses the subtree and gathers all locked nodes. If any locked descendant belongs to a different user, the operation fails immediately.
- The early descendantLockedCount == 0 check prevents upgradeLock from being called when there is nothing to upgrade.
- After unlocking all descendants and locking the target, the metadata counters are fully consistent.
- Save src/tree.cpp.
- Compile to check for errors by running:
g++ -std=c++17 -pthread -Wall -Wextra -Iinclude -c src/tree.cpp -o build/tree.oIf the command completes with no output, the file compiled successfully.
Seeing undeclared identifier errors?
Ensure you have #include "tree_node.h" at the top of src/tree.cpp. Also check that #include <vector> is included in your header since collectLockedDescendants uses std::vector.
help me fix undeclared identifier errors in tree.cpp
Write unit tests for the locking operations
You need to verify that your lock, unlock, and upgradeLock operations behave correctly across multiple scenarios. A focused test file exercises conflict detection, ownership validation, and edge cases.
- Create a new file src/test_tree.cpp inside your src/ directory with the following test code:
#include "tree_node.h"
#include <iostream>
#include <cassert>
void testBasicLock() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("HDFC", "Visa");
// Lock a leaf node
assert(tree.lock("HDFC", 1) == true);
// Cannot lock same node again
assert(tree.lock("HDFC", 2) == false);
// Cannot lock an ancestor while descendant is locked
assert(tree.lock("Visa", 2) == false);
assert(tree.lock("Cards", 2) == false);
std::cout << "[PASS] testBasicLock" << std::endl;
}
void testAncestorBlocking() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("HDFC", "Visa");
// Lock an ancestor
assert(tree.lock("Cards", 1) == true);
// Cannot lock any descendant
assert(tree.lock("Visa", 2) == false);
assert(tree.lock("HDFC", 2) == false);
std::cout << "[PASS] testAncestorBlocking" << std::endl;
}
void testUnlockOwnership() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
assert(tree.lock("Visa", 1) == true);
// Wrong user cannot unlock
assert(tree.unlock("Visa", 2) == false);
// Correct user can unlock
assert(tree.unlock("Visa", 1) == true);
// After unlock, another user can lock
assert(tree.lock("Visa", 2) == true);
std::cout << "[PASS] testUnlockOwnership" << std::endl;
}
void testUpgradeLock() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("HDFC", "Visa");
tree.addNode("ICICI", "Visa");
// Lock two descendants with same user
assert(tree.lock("HDFC", 1) == true);
assert(tree.lock("ICICI", 1) == true);
// Upgrade to parent - should succeed
assert(tree.upgradeLock("Visa", 1) == true);
// Verify Visa is now locked
assert(tree.getNode("Visa")->isLocked == true);
// Verify descendants are unlocked
assert(tree.getNode("HDFC")->isLocked == false);
assert(tree.getNode("ICICI")->isLocked == false);
std::cout << "[PASS] testUpgradeLock" << std::endl;
}
void testUpgradeLockMixedUsers() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("HDFC", "Visa");
tree.addNode("ICICI", "Visa");
// Lock descendants with different users
assert(tree.lock("HDFC", 1) == true);
assert(tree.lock("ICICI", 2) == true);
// Upgrade should fail - mixed users
assert(tree.upgradeLock("Visa", 1) == false);
std::cout << "[PASS] testUpgradeLockMixedUsers" << std::endl;
}
void testUpgradeLockNoDescendants() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
// No descendants are locked - upgrade should fail
assert(tree.upgradeLock("Cards", 1) == false);
std::cout << "[PASS] testUpgradeLockNoDescendants" << std::endl;
}
int main() {
std::cout << "=== Payment Tree Unit Tests ===" << std::endl;
testBasicLock();
testAncestorBlocking();
testUnlockOwnership();
testUpgradeLock();
testUpgradeLockMixedUsers();
testUpgradeLockNoDescendants();
std::cout << "\nAll tests passed!" << std::endl;
return 0;
}What do these tests verify?
- testBasicLock verifies that a locked node rejects new locks and that ancestors cannot be locked while a descendant holds a lock.
- testAncestorBlocking verifies that locking an ancestor blocks all descendant lock attempts.
- testUnlockOwnership verifies that only the user who locked a node can unlock it.
- testUpgradeLock verifies that descendants owned by the same user get consolidated into the parent.
- testUpgradeLockMixedUsers verifies that upgradeLock fails when descendants belong to different users.
- testUpgradeLockNoDescendants verifies that upgradeLock fails when there is nothing to upgrade.
- Save src/test_tree.cpp.
- Compile and run the tests by running:
g++ -std=c++17 -pthread -Wall -Wextra -Iinclude src/tree.cpp src/test_tree.cpp -o test_tree && ./test_treeYou should see all six tests passing with the output ending in All tests passed!.
Seeing assertion failures?
If a test fails, the program aborts with an assertion error naming the file and line number. Check that your lock function returns false (not crashes) when getNode returns nullptr.
Also verify that upgradeLock checks descendantLockedCount == 0 to reject attempts with no locked descendants.
help me debug my failing tree lock tests
- Commit your progress by running:
git add src/tree.cpp src/test_tree.cpp
git commit -m "Implement lock, unlock, upgradeLock with unit tests"- Push to GitHub by running:
git push origin mainWhy commit at this milestone?
You now have working single-threaded locking operations with full test coverage. This is the foundation that Juspay's Hackathon Part A tests. A clean commit here means you can always return to a known-good state before adding concurrency in later steps.
✔️ Awesome, I've got everything!
Great. Double check that all six tests pass and you have saved src/tree.cpp.
ⓧ I'd like to double check the full code
Here is the complete src/tree.cpp file with all locking operations implemented:
#include "tree_node.h"
#include <iostream>
PaymentTree::PaymentTree(int childrenPerNode) : root(nullptr), m(childrenPerNode) {}
PaymentTree::~PaymentTree() {
deleteTree(root);
}
void PaymentTree::deleteTree(TreeNode* node) {
if (node == nullptr) return;
for (TreeNode* child : node->children) {
deleteTree(child);
}
delete node;
}
void PaymentTree::addNode(const std::string& name, const std::string& parentName) {
TreeNode* parentNode = nullptr;
if (!parentName.empty()) {
auto it = nodeMap.find(parentName);
if (it == nodeMap.end()) return;
parentNode = it->second;
}
TreeNode* newNode = new TreeNode(name, parentNode);
if (parentNode != nullptr) {
parentNode->children.push_back(newNode);
} else {
root = newNode;
}
nodeMap[name] = newNode;
}
TreeNode* PaymentTree::getNode(const std::string& name) {
auto it = nodeMap.find(name);
if (it == nodeMap.end()) return nullptr;
return it->second;
}
void PaymentTree::informAncestors(TreeNode* node, int delta) {
// Walk up the parent chain, adjusting each ancestor's
// descendantLockedCount so they know a descendant changed state
TreeNode* current = node->parent;
while (current != nullptr) {
current->descendantLockedCount += delta;
current = current->parent;
}
}
void PaymentTree::informDescendants(TreeNode* node, int delta) {
// Recursively visit all children, adjusting their
// ancestorLockedCount so they know an ancestor changed state
for (TreeNode* child : node->children) {
child->ancestorLockedCount += delta;
informDescendants(child, delta);
}
}
bool PaymentTree::lock(const std::string& nodeName, int userId) {
TreeNode* node = getNode(nodeName);
if (node == nullptr) return false;
// Check 1: node must not already be locked
if (node->isLocked) return false;
// Check 2: no ancestor can be locked (O(1) check using counter)
if (node->ancestorLockedCount > 0) return false;
// Check 3: no descendant can be locked (O(1) check using counter)
if (node->descendantLockedCount > 0) return false;
// All checks passed - set the lock state
node->isLocked = true;
node->lockedBy = userId;
// Propagate metadata: tell ancestors and descendants about this lock
informAncestors(node, 1);
informDescendants(node, 1);
return true;
}
bool PaymentTree::unlock(const std::string& nodeName, int userId) {
TreeNode* node = getNode(nodeName);
if (node == nullptr) return false;
// Only the user who locked it can unlock it
if (!node->isLocked) return false;
if (node->lockedBy != userId) return false;
// Clear the lock state
node->isLocked = false;
node->lockedBy = -1;
// Reverse the metadata propagation
informAncestors(node, -1);
informDescendants(node, -1);
return true;
}
void PaymentTree::collectLockedDescendants(TreeNode* node, int userId,
std::vector<TreeNode*>& result, bool& valid) {
// Recursively find all locked descendants and verify they
// all belong to the same userId
for (TreeNode* child : node->children) {
if (child->isLocked) {
if (child->lockedBy != userId) {
valid = false;
return;
}
result.push_back(child);
}
collectLockedDescendants(child, userId, result, valid);
if (!valid) return;
}
}
bool PaymentTree::upgradeLock(const std::string& nodeName, int userId) {
TreeNode* node = getNode(nodeName);
if (node == nullptr) return false;
// Target node must not already be locked
if (node->isLocked) return false;
// No ancestor can be locked
if (node->ancestorLockedCount > 0) return false;
// Must have at least one locked descendant to upgrade from
if (node->descendantLockedCount == 0) return false;
// Collect all locked descendants and verify they belong to this user
std::vector<TreeNode*> lockedDescendants;
bool valid = true;
collectLockedDescendants(node, userId, lockedDescendants, valid);
if (!valid) return false;
// Unlock all descendants (consolidating into the parent)
for (TreeNode* desc : lockedDescendants) {
desc->isLocked = false;
desc->lockedBy = -1;
informAncestors(desc, -1);
informDescendants(desc, -1);
}
// Lock the target node
node->isLocked = true;
node->lockedBy = userId;
informAncestors(node, 1);
informDescendants(node, 1);
return true;
}
std::string PaymentTree::toJson() const {
return "{}";
}And here is the complete src/test_tree.cpp file:
#include "tree_node.h"
#include <iostream>
#include <cassert>
void testBasicLock() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("HDFC", "Visa");
// Lock a leaf node
assert(tree.lock("HDFC", 1) == true);
// Cannot lock same node again
assert(tree.lock("HDFC", 2) == false);
// Cannot lock an ancestor while descendant is locked
assert(tree.lock("Visa", 2) == false);
assert(tree.lock("Cards", 2) == false);
std::cout << "[PASS] testBasicLock" << std::endl;
}
void testAncestorBlocking() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("HDFC", "Visa");
// Lock an ancestor
assert(tree.lock("Cards", 1) == true);
// Cannot lock any descendant
assert(tree.lock("Visa", 2) == false);
assert(tree.lock("HDFC", 2) == false);
std::cout << "[PASS] testAncestorBlocking" << std::endl;
}
void testUnlockOwnership() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
assert(tree.lock("Visa", 1) == true);
// Wrong user cannot unlock
assert(tree.unlock("Visa", 2) == false);
// Correct user can unlock
assert(tree.unlock("Visa", 1) == true);
// After unlock, another user can lock
assert(tree.lock("Visa", 2) == true);
std::cout << "[PASS] testUnlockOwnership" << std::endl;
}
void testUpgradeLock() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("HDFC", "Visa");
tree.addNode("ICICI", "Visa");
// Lock two descendants with same user
assert(tree.lock("HDFC", 1) == true);
assert(tree.lock("ICICI", 1) == true);
// Upgrade to parent - should succeed
assert(tree.upgradeLock("Visa", 1) == true);
// Verify Visa is now locked
assert(tree.getNode("Visa")->isLocked == true);
// Verify descendants are unlocked
assert(tree.getNode("HDFC")->isLocked == false);
assert(tree.getNode("ICICI")->isLocked == false);
std::cout << "[PASS] testUpgradeLock" << std::endl;
}
void testUpgradeLockMixedUsers() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("HDFC", "Visa");
tree.addNode("ICICI", "Visa");
// Lock descendants with different users
assert(tree.lock("HDFC", 1) == true);
assert(tree.lock("ICICI", 2) == true);
// Upgrade should fail - mixed users
assert(tree.upgradeLock("Visa", 1) == false);
std::cout << "[PASS] testUpgradeLockMixedUsers" << std::endl;
}
void testUpgradeLockNoDescendants() {
PaymentTree tree(3);
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("Visa", "Cards");
// No descendants are locked - upgrade should fail
assert(tree.upgradeLock("Cards", 1) == false);
std::cout << "[PASS] testUpgradeLockNoDescendants" << std::endl;
}
int main() {
std::cout << "=== Payment Tree Unit Tests ===" << std::endl;
testBasicLock();
testAncestorBlocking();
testUnlockOwnership();
testUpgradeLock();
testUpgradeLockMixedUsers();
testUpgradeLockNoDescendants();
std::cout << "\nAll tests passed!" << std::endl;
return 0;
}Your single-threaded tree locking system is complete and tested. Next up, you will model this tree as a real payment routing hierarchy and build a transaction processor on top of it.
Build the Lock-Free Atomic Tree
Your single-threaded payment tree works perfectly. But real payment systems process thousands of transactions simultaneously across multiple threads. If two threads try to lock the same gateway node at the same time, your current bool and int fields will race and corrupt state.
In this step, you will rebuild the tree using std::atomic operations and compare_exchange_weak (CAS) loops. This eliminates the need for mutexes or semaphores entirely. The result is a lock-free tree that multiple threads can safely operate on concurrently.
In this step, get ready to:
- Design the atomic tree node structure with std::atomic<int> fields.
- Implement lock-free lock, unlock, and upgradeLock using CAS retry loops.
- Write concurrent correctness tests proving thread safety.
Design the atomic tree node
The key insight of lock-free programming is replacing mutable shared state with atomic operations. Instead of bool isLocked that any thread can flip without coordination, you use std::atomic<int> lockState and the CAS pattern to guarantee only one thread succeeds at a time.
What is Compare-and-Swap (CAS)?
CAS is an atomic CPU instruction exposed in C++ as compare_exchange_weak. It says: "If the value is still what I expect, swap it to my new value. Otherwise, tell me what it actually is." This happens in a single uninterruptible step at the hardware level.
When multiple threads race, exactly one CAS succeeds and the rest fail immediately. Failed threads can retry in a loop or bail out. No thread ever blocks or waits for a lock to be released.
- Create the file include/atomic_tree_node.h by running:
touch include/atomic_tree_node.h- Open include/atomic_tree_node.h in your editor and paste the following header:
#ifndef ATOMIC_TREE_NODE_H
#define ATOMIC_TREE_NODE_H
#include <string>
#include <vector>
#include <unordered_map>
#include <atomic>
// Lock-free tree node using atomic integers for all mutable state
struct AtomicTreeNode {
std::string name;
AtomicTreeNode* parent;
std::vector<AtomicTreeNode*> children;
std::atomic<int> lockState; // 0 = unlocked, 1 = locked
std::atomic<int> lockedBy; // userId who holds the lock (-1 = none)
std::atomic<int> ancestorLockedCount; // how many ancestors are locked
std::atomic<int> descendantLockedCount; // how many descendants are locked
AtomicTreeNode(const std::string& nodeName, AtomicTreeNode* parentNode = nullptr)
: name(nodeName), parent(parentNode),
lockState(0), lockedBy(-1),
ancestorLockedCount(0), descendantLockedCount(0) {}
};
// Lock-free payment tree with CAS-based operations
class AtomicPaymentTree {
public:
AtomicPaymentTree(int childrenPerNode);
~AtomicPaymentTree();
void addNode(const std::string& name, const std::string& parentName = "");
bool lock(const std::string& nodeName, int userId);
bool unlock(const std::string& nodeName, int userId);
bool upgradeLock(const std::string& nodeName, int userId);
AtomicTreeNode* getNode(const std::string& name);
std::string toJson() const;
// Performance metrics tracked atomically
struct Metrics {
std::atomic<long long> totalTransactions{0};
std::atomic<long long> successfulLocks{0};
std::atomic<long long> failedLocks{0};
std::atomic<long long> casRetries{0};
};
Metrics metrics;
private:
AtomicTreeNode* root;
int m;
std::unordered_map<std::string, AtomicTreeNode*> nodeMap;
void informAncestorsAtomic(AtomicTreeNode* node, int delta);
void informDescendantsAtomic(AtomicTreeNode* node, int delta);
void deleteTree(AtomicTreeNode* node);
};
#endifWhat does this header define?
- AtomicTreeNode replaces every mutable field with std::atomic<int>. The lockState field uses 0/1 instead of bool so CAS can compare integers atomically.
- The Metrics struct tracks CAS retries and lock success/failure counts. These are also atomic because multiple threads update them simultaneously.
- informAncestorsAtomic and informDescendantsAtomic use fetch_add for lock-free counter propagation instead of plain ++ and --.
Why not use a mutex?
Juspay's Hackathon Part B explicitly requires thread safety without shared_mutex or locks. The interviewer wants to see that you understand how atomic hardware primitives work at a low level. A mutex-based solution would pass correctness tests but fail the interview criteria.
Lock-free code also scales better under high contention because threads never block waiting for each other. They simply retry the CAS until they succeed or give up.
- Save include/atomic_tree_node.h.
- Confirm the file exists by running:
ls include/atomic_tree_node.hYou should see include/atomic_tree_node.h listed in the output.
File not showing up?
Make sure you are in the project root directory (the folder containing your Makefile). If you are inside src/ or include/, run cd .. first.
Help me verify my file location
Implement lock-free operations with CAS
Now you will write the implementation file that powers the atomic tree. The core pattern is the CAS retry loop: attempt to change a value atomically, and if another thread beat you to it, either retry or return failure.
- Create src/atomic_tree.cpp and add the tree management functions by pasting:
#include "atomic_tree_node.h"
#include <queue>
#include <functional>
// Constructor initializes an empty tree with max children per node
AtomicPaymentTree::AtomicPaymentTree(int childrenPerNode) : root(nullptr), m(childrenPerNode) {}
// Destructor recursively frees all nodes
AtomicPaymentTree::~AtomicPaymentTree() {
deleteTree(root);
}
void AtomicPaymentTree::deleteTree(AtomicTreeNode* node) {
if (!node) return;
for (auto* child : node->children) {
deleteTree(child);
}
delete node;
}
// Add a node to the tree (called during setup, not thread-safe)
void AtomicPaymentTree::addNode(const std::string& name, const std::string& parentName) {
if (parentName.empty()) {
root = new AtomicTreeNode(name);
nodeMap[name] = root;
return;
}
auto it = nodeMap.find(parentName);
if (it == nodeMap.end()) return;
AtomicTreeNode* parent = it->second;
AtomicTreeNode* node = new AtomicTreeNode(name, parent);
parent->children.push_back(node);
nodeMap[name] = node;
}
// O(1) lookup by name
AtomicTreeNode* AtomicPaymentTree::getNode(const std::string& name) {
auto it = nodeMap.find(name);
return (it != nodeMap.end()) ? it->second : nullptr;
}
// Propagate lock count changes up to all ancestors using fetch_add
void AtomicPaymentTree::informAncestorsAtomic(AtomicTreeNode* node, int delta) {
AtomicTreeNode* current = node->parent;
while (current) {
current->descendantLockedCount.fetch_add(delta, std::memory_order_release);
current = current->parent;
}
}
// Propagate lock count changes down to all descendants using fetch_add
void AtomicPaymentTree::informDescendantsAtomic(AtomicTreeNode* node, int delta) {
for (auto* child : node->children) {
child->ancestorLockedCount.fetch_add(delta, std::memory_order_release);
informDescendantsAtomic(child, delta);
}
}What does this code do?
- The constructor, destructor, addNode, and getNode mirror the single-threaded tree. Tree construction happens before threads start, so it does not need to be atomic.
- informAncestorsAtomic walks up the parent chain and uses fetch_add with memory_order_release to atomically increment or decrement the descendantLockedCount of each ancestor.
- memory_order_release ensures all preceding writes in this thread become visible to other threads that subsequently read this atomic variable with memory_order_acquire.
Now add the lock() function. This is the heart of the lock-free design.
- Below the informDescendantsAtomic function, paste the lock implementation:
// Lock-free lock using CAS retry loop
bool AtomicPaymentTree::lock(const std::string& nodeName, int userId) {
AtomicTreeNode* node = getNode(nodeName);
if (!node) return false;
// Check if any ancestor is locked (atomic read with acquire semantics)
if (node->ancestorLockedCount.load(std::memory_order_acquire) > 0) {
return false;
}
// Check if any descendant is locked
if (node->descendantLockedCount.load(std::memory_order_acquire) > 0) {
return false;
}
// CAS loop: atomically set lockState from 0 (unlocked) to 1 (locked)
int expected = 0;
while (!node->lockState.compare_exchange_weak(expected, 1,
std::memory_order_release, std::memory_order_relaxed)) {
if (expected != 0) {
// Node is already locked by someone else
return false;
}
// Spurious failure - reset expected and retry
metrics.casRetries.fetch_add(1, std::memory_order_relaxed);
expected = 0;
}
// Re-validate after CAS success (another thread may have locked an ancestor/descendant)
if (node->ancestorLockedCount.load(std::memory_order_acquire) > 0 ||
node->descendantLockedCount.load(std::memory_order_acquire) > 0) {
// Rollback: release the lock we just acquired
node->lockState.store(0, std::memory_order_release);
return false;
}
// Lock acquired successfully - record owner and propagate counts
node->lockedBy.store(userId, std::memory_order_release);
informAncestorsAtomic(node, 1);
informDescendantsAtomic(node, 1);
return true;
}How does the CAS loop work?
- compare_exchange_weak checks if lockState is 0 (unlocked). If yes, it atomically sets it to 1 in a single CPU instruction. If no, it writes the actual value into expected.
- The "weak" variant may fail spuriously (even when the value matches) but yields better performance on some platforms when used in a loop.
- After the CAS succeeds, the code re-validates ancestor and descendant counts. This handles the race where another thread locked a relative node between the initial check and the CAS.
- If re-validation fails, the code rolls back by storing 0 into lockState. This ensures no inconsistent state persists.
- Below the lock function, add the unlock implementation:
// Lock-free unlock: CAS clears lock only if the userId matches
bool AtomicPaymentTree::unlock(const std::string& nodeName, int userId) {
AtomicTreeNode* node = getNode(nodeName);
if (!node) return false;
// Verify the node is locked by this user (atomic read)
if (node->lockedBy.load(std::memory_order_acquire) != userId) {
return false;
}
// CAS to clear lock state from 1 to 0
int expected = 1;
if (!node->lockState.compare_exchange_weak(expected, 0,
std::memory_order_release, std::memory_order_relaxed)) {
metrics.casRetries.fetch_add(1, std::memory_order_relaxed);
return false;
}
// Clear ownership and propagate count decrements
node->lockedBy.store(-1, std::memory_order_release);
informAncestorsAtomic(node, -1);
informDescendantsAtomic(node, -1);
return true;
}What does unlock do differently?
The unlock CAS swaps lockState from 1 back to 0. Only the thread that owns the lock (verified by checking lockedBy) can execute this path. The ownership check prevents other users from unlocking nodes they do not own.
- Below unlock, add the upgradeLock and toJson functions:
// Multi-step CAS sequence: collect locked descendants, verify ownership, unlock them, lock target
bool AtomicPaymentTree::upgradeLock(const std::string& nodeName, int userId) {
AtomicTreeNode* node = getNode(nodeName);
if (!node) return false;
// Node must not already be locked
if (node->lockState.load(std::memory_order_acquire) != 0) {
return false;
}
// No ancestor can be locked
if (node->ancestorLockedCount.load(std::memory_order_acquire) > 0) {
return false;
}
// BFS to collect all locked descendants and verify they belong to userId
std::vector<AtomicTreeNode*> lockedDescendants;
std::queue<AtomicTreeNode*> bfs;
for (auto* child : node->children) {
bfs.push(child);
}
while (!bfs.empty()) {
AtomicTreeNode* current = bfs.front();
bfs.pop();
if (current->lockState.load(std::memory_order_acquire) == 1) {
if (current->lockedBy.load(std::memory_order_acquire) != userId) {
return false; // A descendant is locked by a different user
}
lockedDescendants.push_back(current);
}
for (auto* child : current->children) {
bfs.push(child);
}
}
// Must have at least one locked descendant to upgrade
if (lockedDescendants.empty()) {
return false;
}
// Unlock all descendants atomically
for (auto* desc : lockedDescendants) {
desc->lockState.store(0, std::memory_order_release);
desc->lockedBy.store(-1, std::memory_order_release);
informAncestorsAtomic(desc, -1);
informDescendantsAtomic(desc, -1);
}
// Lock the target node via CAS
int expected = 0;
if (!node->lockState.compare_exchange_weak(expected, 1,
std::memory_order_release, std::memory_order_relaxed)) {
return false;
}
node->lockedBy.store(userId, std::memory_order_release);
informAncestorsAtomic(node, 1);
informDescendantsAtomic(node, 1);
return true;
}
// Serialize tree state to JSON for the frontend
std::string AtomicPaymentTree::toJson() const {
if (!root) return "{}";
std::function<std::string(AtomicTreeNode*)> serialize = [&](AtomicTreeNode* node) -> std::string {
std::string json = "{\"name\":\"" + node->name + "\",\"isLocked\":" +
(node->lockState.load(std::memory_order_acquire) == 1 ? "true" : "false") +
",\"children\":[";
for (size_t i = 0; i < node->children.size(); i++) {
if (i > 0) json += ",";
json += serialize(node->children[i]);
}
json += "]}";
return json;
};
return serialize(root);
}What does upgradeLock do?
UpgradeLock is the most complex operation. It consolidates multiple descendant locks into a single lock at a higher node. A payment system uses this when a user who has locked individual bank gateways (HDFC, ICICI) wants to lock the entire Visa category instead.
The multi-step CAS sequence first collects all locked descendants via BFS, verifies they all belong to the same userId, unlocks them while propagating counter decrements, then locks the target node. If any step fails, the operation returns false.
- Save src/atomic_tree.cpp.
- Verify the file compiles by running:
mkdir -p build
g++ -std=c++17 -pthread -c src/atomic_tree.cpp -Iinclude -o build/atomic_tree.oYou should see no errors or warnings in the terminal output.
Getting errors about atomic?
The -latomic flag is needed at link time (when building the final executable), not during compile-only steps. If you see errors about missing includes, confirm your g++ supports C++17 by running g++ --version. GCC 11 through 15 default to C++17.
Help me fix atomic compile errors
✔️ Awesome, I've got everything!
Great. Double check you have saved src/atomic_tree.cpp and that it compiled without errors.
ⓧ I'd like to double check the full code
Here is the complete src/atomic_tree.cpp file:
#include "atomic_tree_node.h"
#include <queue>
#include <functional>
// Constructor initializes an empty tree with max children per node
AtomicPaymentTree::AtomicPaymentTree(int childrenPerNode) : root(nullptr), m(childrenPerNode) {}
// Destructor recursively frees all nodes
AtomicPaymentTree::~AtomicPaymentTree() {
deleteTree(root);
}
void AtomicPaymentTree::deleteTree(AtomicTreeNode* node) {
if (!node) return;
for (auto* child : node->children) {
deleteTree(child);
}
delete node;
}
// Add a node to the tree (called during setup, not thread-safe)
void AtomicPaymentTree::addNode(const std::string& name, const std::string& parentName) {
if (parentName.empty()) {
root = new AtomicTreeNode(name);
nodeMap[name] = root;
return;
}
auto it = nodeMap.find(parentName);
if (it == nodeMap.end()) return;
AtomicTreeNode* parent = it->second;
AtomicTreeNode* node = new AtomicTreeNode(name, parent);
parent->children.push_back(node);
nodeMap[name] = node;
}
// O(1) lookup by name
AtomicTreeNode* AtomicPaymentTree::getNode(const std::string& name) {
auto it = nodeMap.find(name);
return (it != nodeMap.end()) ? it->second : nullptr;
}
// Propagate lock count changes up to all ancestors using fetch_add
void AtomicPaymentTree::informAncestorsAtomic(AtomicTreeNode* node, int delta) {
AtomicTreeNode* current = node->parent;
while (current) {
current->descendantLockedCount.fetch_add(delta, std::memory_order_release);
current = current->parent;
}
}
// Propagate lock count changes down to all descendants using fetch_add
void AtomicPaymentTree::informDescendantsAtomic(AtomicTreeNode* node, int delta) {
for (auto* child : node->children) {
child->ancestorLockedCount.fetch_add(delta, std::memory_order_release);
informDescendantsAtomic(child, delta);
}
}
// Lock-free lock using CAS retry loop
bool AtomicPaymentTree::lock(const std::string& nodeName, int userId) {
AtomicTreeNode* node = getNode(nodeName);
if (!node) return false;
// Check if any ancestor is locked (atomic read with acquire semantics)
if (node->ancestorLockedCount.load(std::memory_order_acquire) > 0) {
return false;
}
// Check if any descendant is locked
if (node->descendantLockedCount.load(std::memory_order_acquire) > 0) {
return false;
}
// CAS loop: atomically set lockState from 0 (unlocked) to 1 (locked)
int expected = 0;
while (!node->lockState.compare_exchange_weak(expected, 1,
std::memory_order_release, std::memory_order_relaxed)) {
if (expected != 0) {
// Node is already locked by someone else
return false;
}
// Spurious failure - reset expected and retry
metrics.casRetries.fetch_add(1, std::memory_order_relaxed);
expected = 0;
}
// Re-validate after CAS success (another thread may have locked an ancestor/descendant)
if (node->ancestorLockedCount.load(std::memory_order_acquire) > 0 ||
node->descendantLockedCount.load(std::memory_order_acquire) > 0) {
// Rollback: release the lock we just acquired
node->lockState.store(0, std::memory_order_release);
return false;
}
// Lock acquired successfully - record owner and propagate counts
node->lockedBy.store(userId, std::memory_order_release);
informAncestorsAtomic(node, 1);
informDescendantsAtomic(node, 1);
return true;
}
// Lock-free unlock: CAS clears lock only if the userId matches
bool AtomicPaymentTree::unlock(const std::string& nodeName, int userId) {
AtomicTreeNode* node = getNode(nodeName);
if (!node) return false;
// Verify the node is locked by this user (atomic read)
if (node->lockedBy.load(std::memory_order_acquire) != userId) {
return false;
}
// CAS to clear lock state from 1 to 0
int expected = 1;
if (!node->lockState.compare_exchange_weak(expected, 0,
std::memory_order_release, std::memory_order_relaxed)) {
metrics.casRetries.fetch_add(1, std::memory_order_relaxed);
return false;
}
// Clear ownership and propagate count decrements
node->lockedBy.store(-1, std::memory_order_release);
informAncestorsAtomic(node, -1);
informDescendantsAtomic(node, -1);
return true;
}
// Multi-step CAS sequence: collect locked descendants, verify ownership, unlock them, lock target
bool AtomicPaymentTree::upgradeLock(const std::string& nodeName, int userId) {
AtomicTreeNode* node = getNode(nodeName);
if (!node) return false;
// Node must not already be locked
if (node->lockState.load(std::memory_order_acquire) != 0) {
return false;
}
// No ancestor can be locked
if (node->ancestorLockedCount.load(std::memory_order_acquire) > 0) {
return false;
}
// BFS to collect all locked descendants and verify they belong to userId
std::vector<AtomicTreeNode*> lockedDescendants;
std::queue<AtomicTreeNode*> bfs;
for (auto* child : node->children) {
bfs.push(child);
}
while (!bfs.empty()) {
AtomicTreeNode* current = bfs.front();
bfs.pop();
if (current->lockState.load(std::memory_order_acquire) == 1) {
if (current->lockedBy.load(std::memory_order_acquire) != userId) {
return false; // A descendant is locked by a different user
}
lockedDescendants.push_back(current);
}
for (auto* child : current->children) {
bfs.push(child);
}
}
// Must have at least one locked descendant to upgrade
if (lockedDescendants.empty()) {
return false;
}
// Unlock all descendants atomically
for (auto* desc : lockedDescendants) {
desc->lockState.store(0, std::memory_order_release);
desc->lockedBy.store(-1, std::memory_order_release);
informAncestorsAtomic(desc, -1);
informDescendantsAtomic(desc, -1);
}
// Lock the target node via CAS
int expected = 0;
if (!node->lockState.compare_exchange_weak(expected, 1,
std::memory_order_release, std::memory_order_relaxed)) {
return false;
}
node->lockedBy.store(userId, std::memory_order_release);
informAncestorsAtomic(node, 1);
informDescendantsAtomic(node, 1);
return true;
}
// Serialize tree state to JSON for the frontend
std::string AtomicPaymentTree::toJson() const {
if (!root) return "{}";
std::function<std::string(AtomicTreeNode*)> serialize = [&](AtomicTreeNode* node) -> std::string {
std::string json = "{\"name\":\"" + node->name + "\",\"isLocked\":" +
(node->lockState.load(std::memory_order_acquire) == 1 ? "true" : "false") +
",\"children\":[";
for (size_t i = 0; i < node->children.size(); i++) {
if (i > 0) json += ",";
json += serialize(node->children[i]);
}
json += "]}";
return json;
};
return serialize(root);
}ⓧ I'd like to double check the header
Here is the complete include/atomic_tree_node.h file:
#ifndef ATOMIC_TREE_NODE_H
#define ATOMIC_TREE_NODE_H
#include <string>
#include <vector>
#include <unordered_map>
#include <atomic>
struct AtomicTreeNode {
std::string name;
AtomicTreeNode* parent;
std::vector<AtomicTreeNode*> children;
std::atomic<int> lockState;
std::atomic<int> lockedBy;
std::atomic<int> ancestorLockedCount;
std::atomic<int> descendantLockedCount;
AtomicTreeNode(const std::string& nodeName, AtomicTreeNode* parentNode = nullptr)
: name(nodeName), parent(parentNode),
lockState(0), lockedBy(-1),
ancestorLockedCount(0), descendantLockedCount(0) {}
};
class AtomicPaymentTree {
public:
AtomicPaymentTree(int childrenPerNode);
~AtomicPaymentTree();
void addNode(const std::string& name, const std::string& parentName = "");
bool lock(const std::string& nodeName, int userId);
bool unlock(const std::string& nodeName, int userId);
bool upgradeLock(const std::string& nodeName, int userId);
AtomicTreeNode* getNode(const std::string& name);
std::string toJson() const;
struct Metrics {
std::atomic<long long> totalTransactions{0};
std::atomic<long long> successfulLocks{0};
std::atomic<long long> failedLocks{0};
std::atomic<long long> casRetries{0};
};
Metrics metrics;
private:
AtomicTreeNode* root;
int m;
std::unordered_map<std::string, AtomicTreeNode*> nodeMap;
void informAncestorsAtomic(AtomicTreeNode* node, int delta);
void informDescendantsAtomic(AtomicTreeNode* node, int delta);
void deleteTree(AtomicTreeNode* node);
};
#endifWrite concurrent correctness tests
Your atomic tree compiles, but does it actually work under concurrent pressure? You need a test that spawns multiple threads competing for the same nodes and verifies no invariants are violated.
- Create a test file test_atomic.cpp in your project root by pasting:
#include "atomic_tree_node.h"
#include <iostream>
#include <thread>
#include <vector>
#include <cassert>
// Build a small test tree
void buildTestTree(AtomicPaymentTree& tree) {
tree.addNode("Root");
tree.addNode("A", "Root");
tree.addNode("B", "Root");
tree.addNode("C", "A");
tree.addNode("D", "A");
tree.addNode("E", "B");
}
// Each thread tries to lock a leaf node, hold it briefly, then unlock
void workerThread(AtomicPaymentTree& tree, int threadId, int iterations) {
std::vector<std::string> targets = {"C", "D", "E"};
std::string target = targets[threadId % targets.size()];
for (int i = 0; i < iterations; i++) {
if (tree.lock(target, threadId)) {
// Verify we actually own it
AtomicTreeNode* node = tree.getNode(target);
assert(node->lockedBy.load() == threadId);
assert(node->lockState.load() == 1);
// Simulate brief work
std::this_thread::yield();
// Unlock and verify
bool unlocked = tree.unlock(target, threadId);
assert(unlocked);
}
}
}
int main() {
AtomicPaymentTree tree(3);
buildTestTree(tree);
std::cout << "=== Concurrent Correctness Test ===\n";
// Test 1: Basic lock exclusivity
assert(tree.lock("C", 1) == true);
assert(tree.lock("C", 2) == false); // Already locked
assert(tree.lock("A", 3) == false); // Descendant locked
assert(tree.unlock("C", 1) == true);
std::cout << "[PASS] Basic lock exclusivity\n";
// Test 2: Ancestor/descendant conflict
assert(tree.lock("A", 1) == true);
assert(tree.lock("C", 2) == false); // Ancestor locked
assert(tree.lock("D", 2) == false); // Ancestor locked
assert(tree.lock("B", 2) == true); // Sibling is fine
assert(tree.unlock("A", 1) == true);
assert(tree.unlock("B", 2) == true);
std::cout << "[PASS] Ancestor/descendant conflict\n";
// Test 3: UpgradeLock
assert(tree.lock("C", 1) == true);
assert(tree.lock("D", 1) == true);
assert(tree.upgradeLock("A", 1) == true); // Consolidate C+D into A
assert(tree.getNode("C")->lockState.load() == 0); // C now unlocked
assert(tree.getNode("D")->lockState.load() == 0); // D now unlocked
assert(tree.getNode("A")->lockState.load() == 1); // A now locked
assert(tree.unlock("A", 1) == true);
std::cout << "[PASS] UpgradeLock\n";
// Test 4: Multi-threaded stress test
int numThreads = 8;
int iterationsPerThread = 1000;
std::vector<std::thread> threads;
for (int i = 0; i < numThreads; i++) {
threads.emplace_back(workerThread, std::ref(tree), i, iterationsPerThread);
}
for (auto& t : threads) {
t.join();
}
// Verify invariants after all threads complete
AtomicTreeNode* root = tree.getNode("Root");
assert(root->descendantLockedCount.load() == 0);
AtomicTreeNode* a = tree.getNode("A");
assert(a->descendantLockedCount.load() == 0);
assert(a->ancestorLockedCount.load() == 0);
std::cout << "[PASS] Multi-threaded stress test (" << numThreads
<< " threads x " << iterationsPerThread << " iterations)\n";
std::cout << "CAS retries: " << tree.metrics.casRetries.load() << "\n";
std::cout << "\n=== All tests passed! ===\n";
return 0;
}What does this test verify?
- Tests 1-3 verify single-threaded correctness: lock exclusivity, ancestor/descendant conflict detection, and upgradeLock behavior.
- Test 4 spawns 8 threads that each try to lock, verify ownership, and unlock the same nodes 1000 times. If any CAS logic is broken, the assert statements will catch it immediately.
- After all threads finish, the test checks that all counters have returned to zero (no orphaned locks, no inconsistent propagation).
- Compile and run the test by running:
g++ -std=c++17 -pthread test_atomic.cpp src/atomic_tree.cpp -Iinclude -o test_atomic -latomic
./test_atomicYou should see all four tests pass with output like this:
=== Concurrent Correctness Test ===
[PASS] Basic lock exclusivity
[PASS] Ancestor/descendant conflict
[PASS] UpgradeLock
[PASS] Multi-threaded stress test (8 threads x 1000 iterations)
CAS retries: 42
=== All tests passed! ===Why might the CAS retry count vary?
The exact number of CAS retries depends on your CPU architecture, thread scheduling, and system load. A number between 0 and a few hundred is normal for 8 threads. Higher numbers indicate more contention. The important thing is that no assertions fail.
Seeing assertion failures?
If an assertion fires in the stress test, the most common cause is a missing re-validation step after CAS success in your lock() function. Check that you re-read ancestorLockedCount and descendantLockedCount AFTER the CAS succeeds, and roll back if either is non-zero.
Help me debug my concurrent test failures
- Commit your changes to Git by running:
git add include/atomic_tree_node.h src/atomic_tree.cpp test_atomic.cpp
git commit -m "Add lock-free atomic tree with CAS operations and concurrent tests"
git pushYour lock-free tree passes concurrent stress tests with 8 threads. Next up, you will build a full transaction simulator that pushes even harder with 16+ threads and thousands of transactions.
Build the Concurrent Transaction Simulator
Your lock-free tree operations work correctly under concurrent access. Now you need to prove they hold up under real-world pressure.
In a payment system, hundreds of transactions arrive simultaneously, all competing to lock different gateway nodes. A stress test simulates this chaos and then verifies the tree is still in a consistent state afterwards. This is exactly what Juspay's Part B evaluates.
In this step, get ready to:
- Build a multi-threaded transaction simulator that spawns 8+ worker threads.
- Implement a correctness verifier that validates tree invariants after all threads complete.
- Run stress tests with thousands of concurrent transactions and confirm zero invariant violations.
Create the simulator with the thread pool and transaction worker
Each worker thread simulates a payment processor. It picks a random gateway node, attempts to lock it, holds it briefly to simulate processing, then unlocks it.
- Create a new file src/simulator.cpp in your project's src/ directory.
- Add the includes and the tree construction function by pasting this code:
#include "atomic_tree_node.h"
#include <iostream>
#include <thread>
#include <vector>
#include <random>
#include <chrono>
// Build the payment gateway tree hierarchy
void buildPaymentTree(AtomicPaymentTree& tree) {
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("UPI", "PaymentSystem");
tree.addNode("Wallets", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("Mastercard", "Cards");
tree.addNode("RuPay", "Cards");
tree.addNode("GPay", "UPI");
tree.addNode("PhonePe", "UPI");
tree.addNode("BHIM", "UPI");
tree.addNode("Paytm", "Wallets");
tree.addNode("AmazonPay", "Wallets");
tree.addNode("HDFC", "Visa");
tree.addNode("ICICI", "Visa");
tree.addNode("SBI", "Mastercard");
tree.addNode("Axis", "Mastercard");
tree.addNode("PNB", "RuPay");
tree.addNode("BOB", "RuPay");
}What does this code do?
This builds the same payment routing hierarchy you designed earlier: PaymentSystem at the root, branching into Cards, UPI, and Wallets, then down to specific gateways and banks.
Each leaf node (HDFC, ICICI, SBI, etc.) represents a bank endpoint that transactions will compete to lock.
- Below buildPaymentTree, add the worker function that each thread will execute:
// Simulate concurrent transactions for a single thread
void simulateTransactions(AtomicPaymentTree& tree, int threadId, int numTransactions) {
std::mt19937 rng(threadId * 42);
std::vector<std::string> gateways = {
"HDFC", "ICICI", "SBI", "Axis", "PNB", "BOB",
"GPay", "PhonePe", "BHIM", "Paytm", "AmazonPay"
};
std::uniform_int_distribution<int> dist(0, gateways.size() - 1);
for (int i = 0; i < numTransactions; i++) {
std::string target = gateways[dist(rng)];
tree.metrics.totalTransactions.fetch_add(1, std::memory_order_relaxed);
if (tree.lock(target, threadId)) {
tree.metrics.successfulLocks.fetch_add(1, std::memory_order_relaxed);
// Simulate transaction processing time
std::this_thread::sleep_for(std::chrono::microseconds(100));
tree.unlock(target, threadId);
} else {
tree.metrics.failedLocks.fetch_add(1, std::memory_order_relaxed);
}
}
}What does this code do?
Each thread gets a deterministic random number generator seeded by its thread ID. This makes runs reproducible for debugging while still creating realistic contention patterns.
The gateways vector contains the leaf-level nodes that transactions target. Each iteration picks a random gateway, atomically increments the total transaction counter, then attempts to lock.
On success, the thread holds the lock for 100 microseconds (simulating real payment processing latency) before unlocking. On failure, it records the contention. The memory_order_relaxed ordering is safe here because these counters are purely informational and don't need ordering guarantees relative to other operations.
Add the correctness verifier and test harness
After all threads finish, the tree must be in a clean state. No orphaned locks should remain, and all metadata counters must be zero.
- Below simulateTransactions, add the invariant verifier function:
// Verify tree invariants after all threads complete
bool verifyTreeInvariants(AtomicPaymentTree& tree) {
std::vector<std::string> allNodes = {
"PaymentSystem", "Cards", "UPI", "Wallets",
"Visa", "Mastercard", "RuPay",
"GPay", "PhonePe", "BHIM", "Paytm", "AmazonPay",
"HDFC", "ICICI", "SBI", "Axis", "PNB", "BOB"
};
bool valid = true;
for (const auto& name : allNodes) {
AtomicTreeNode* node = tree.getNode(name);
if (!node) continue;
// Check no orphaned locks remain
if (node->lockState.load(std::memory_order_acquire) != 0) {
std::cerr << "INVARIANT VIOLATION: " << name << " still locked\n";
valid = false;
}
// Check ancestor/descendant counts are consistent
if (node->ancestorLockedCount.load(std::memory_order_acquire) != 0) {
std::cerr << "INVARIANT VIOLATION: " << name << " ancestorLockedCount != 0\n";
valid = false;
}
if (node->descendantLockedCount.load(std::memory_order_acquire) != 0) {
std::cerr << "INVARIANT VIOLATION: " << name << " descendantLockedCount != 0\n";
valid = false;
}
}
return valid;
}What does this code do?
The verifier iterates every node in the tree and checks three invariants. First, no node should still be locked (every lock() was paired with an unlock()). Second, every node's ancestorLockedCount should be zero. Third, every node's descendantLockedCount should be zero.
Using memory_order_acquire on the loads ensures you see all preceding writes from the worker threads. If any check fails, the function prints which node violated which invariant so you can debug the race condition.
- Finally, add the main function that ties everything together as the stress test harness:
int main() {
std::cout << "=== Payment Gateway Concurrent Stress Test ===\n\n";
AtomicPaymentTree tree(3);
buildPaymentTree(tree);
int numThreads = 8;
int txnPerThread = 1000;
std::cout << "Launching " << numThreads << " threads, "
<< txnPerThread << " transactions each...\n";
auto start = std::chrono::high_resolution_clock::now();
// Spawn worker threads
std::vector<std::thread> threads;
for (int i = 0; i < numThreads; i++) {
threads.emplace_back(simulateTransactions, std::ref(tree), i, txnPerThread);
}
// Wait for all threads to complete
for (auto& t : threads) {
t.join();
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
// Print results
std::cout << "\n=== Results ===\n";
std::cout << "Duration: " << duration.count() << " ms\n";
std::cout << "Total transactions: " << tree.metrics.totalTransactions.load() << "\n";
std::cout << "Successful locks: " << tree.metrics.successfulLocks.load() << "\n";
std::cout << "Failed locks: " << tree.metrics.failedLocks.load() << "\n";
std::cout << "CAS retries: " << tree.metrics.casRetries.load() << "\n";
std::cout << "Throughput: "
<< (tree.metrics.totalTransactions.load() * 1000) / std::max(1LL, (long long)duration.count())
<< " txn/sec\n";
// Verify tree invariants
std::cout << "\n=== Correctness Verification ===\n";
if (verifyTreeInvariants(tree)) {
std::cout << "All invariants passed! No orphaned locks or inconsistent counts.\n";
} else {
std::cerr << "FAILURE: Tree invariants violated!\n";
return 1;
}
return 0;
}What's happening here?
The harness creates 8 threads, each processing 1000 transactions. The threads.emplace_back(simulateTransactions, std::ref(tree), i, txnPerThread) line constructs each thread in the vector. You must use std::ref(tree) because std::thread copies arguments by default. Without std::ref, each thread would get its own copy of the tree instead of sharing the same one.
After all threads join(), the program calculates throughput (transactions per second) and runs the correctness verifier. A return code of 0 means all invariants passed.
- Save src/simulator.cpp.
Getting compile errors later?
Make sure the closing brace of each function is on its own line. A missing brace after simulateTransactions or verifyTreeInvariants causes cascading errors that look unrelated.
Help me debug a compile error in my simulator.cpp file.
✔️ Awesome, I've got everything!
Great. Double check you've saved src/simulator.cpp with all four functions: buildPaymentTree, simulateTransactions, verifyTreeInvariants, and main.
ⓧ I'd like to double check the full code
#include "atomic_tree_node.h"
#include <iostream>
#include <thread>
#include <vector>
#include <random>
#include <chrono>
// Build the payment gateway tree hierarchy
void buildPaymentTree(AtomicPaymentTree& tree) {
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("UPI", "PaymentSystem");
tree.addNode("Wallets", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("Mastercard", "Cards");
tree.addNode("RuPay", "Cards");
tree.addNode("GPay", "UPI");
tree.addNode("PhonePe", "UPI");
tree.addNode("BHIM", "UPI");
tree.addNode("Paytm", "Wallets");
tree.addNode("AmazonPay", "Wallets");
tree.addNode("HDFC", "Visa");
tree.addNode("ICICI", "Visa");
tree.addNode("SBI", "Mastercard");
tree.addNode("Axis", "Mastercard");
tree.addNode("PNB", "RuPay");
tree.addNode("BOB", "RuPay");
}
// Simulate concurrent transactions for a single thread
void simulateTransactions(AtomicPaymentTree& tree, int threadId, int numTransactions) {
std::mt19937 rng(threadId * 42);
std::vector<std::string> gateways = {
"HDFC", "ICICI", "SBI", "Axis", "PNB", "BOB",
"GPay", "PhonePe", "BHIM", "Paytm", "AmazonPay"
};
std::uniform_int_distribution<int> dist(0, gateways.size() - 1);
for (int i = 0; i < numTransactions; i++) {
std::string target = gateways[dist(rng)];
tree.metrics.totalTransactions.fetch_add(1, std::memory_order_relaxed);
if (tree.lock(target, threadId)) {
tree.metrics.successfulLocks.fetch_add(1, std::memory_order_relaxed);
// Simulate transaction processing time
std::this_thread::sleep_for(std::chrono::microseconds(100));
tree.unlock(target, threadId);
} else {
tree.metrics.failedLocks.fetch_add(1, std::memory_order_relaxed);
}
}
}
// Verify tree invariants after all threads complete
bool verifyTreeInvariants(AtomicPaymentTree& tree) {
std::vector<std::string> allNodes = {
"PaymentSystem", "Cards", "UPI", "Wallets",
"Visa", "Mastercard", "RuPay",
"GPay", "PhonePe", "BHIM", "Paytm", "AmazonPay",
"HDFC", "ICICI", "SBI", "Axis", "PNB", "BOB"
};
bool valid = true;
for (const auto& name : allNodes) {
AtomicTreeNode* node = tree.getNode(name);
if (!node) continue;
// Check no orphaned locks remain
if (node->lockState.load(std::memory_order_acquire) != 0) {
std::cerr << "INVARIANT VIOLATION: " << name << " still locked\n";
valid = false;
}
// Check ancestor/descendant counts are consistent
if (node->ancestorLockedCount.load(std::memory_order_acquire) != 0) {
std::cerr << "INVARIANT VIOLATION: " << name << " ancestorLockedCount != 0\n";
valid = false;
}
if (node->descendantLockedCount.load(std::memory_order_acquire) != 0) {
std::cerr << "INVARIANT VIOLATION: " << name << " descendantLockedCount != 0\n";
valid = false;
}
}
return valid;
}
int main() {
std::cout << "=== Payment Gateway Concurrent Stress Test ===\n\n";
AtomicPaymentTree tree(3);
buildPaymentTree(tree);
int numThreads = 8;
int txnPerThread = 1000;
std::cout << "Launching " << numThreads << " threads, "
<< txnPerThread << " transactions each...\n";
auto start = std::chrono::high_resolution_clock::now();
// Spawn worker threads
std::vector<std::thread> threads;
for (int i = 0; i < numThreads; i++) {
threads.emplace_back(simulateTransactions, std::ref(tree), i, txnPerThread);
}
// Wait for all threads to complete
for (auto& t : threads) {
t.join();
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
// Print results
std::cout << "\n=== Results ===\n";
std::cout << "Duration: " << duration.count() << " ms\n";
std::cout << "Total transactions: " << tree.metrics.totalTransactions.load() << "\n";
std::cout << "Successful locks: " << tree.metrics.successfulLocks.load() << "\n";
std::cout << "Failed locks: " << tree.metrics.failedLocks.load() << "\n";
std::cout << "CAS retries: " << tree.metrics.casRetries.load() << "\n";
std::cout << "Throughput: "
<< (tree.metrics.totalTransactions.load() * 1000) / std::max(1LL, (long long)duration.count())
<< " txn/sec\n";
// Verify tree invariants
std::cout << "\n=== Correctness Verification ===\n";
if (verifyTreeInvariants(tree)) {
std::cout << "All invariants passed! No orphaned locks or inconsistent counts.\n";
} else {
std::cerr << "FAILURE: Tree invariants violated!\n";
return 1;
}
return 0;
}Run the stress test and scale up
Time to compile the simulator as a standalone binary and prove your lock-free tree handles real concurrent load.
- Compile the stress test by running this command:
g++ -std=c++17 -pthread -O2 src/simulator.cpp src/atomic_tree.cpp -Iinclude -o stress_test -latomicWhy compile separately from the Makefile?
The simulator.cpp file has its own main() function for standalone testing. The project's Makefile compiles all source files together for the final integrated binary. You compile the simulator separately now to test it in isolation.
- Run the 8-thread stress test:
./stress_test- You should see output showing 8000 total transactions (8 threads x 1000 each), a mix of successful and failed locks, the CAS retry count, throughput in transactions per second, and "All invariants passed!" at the end.
What should the output look like?
Expect the failed lock count to be significant. This is normal and expected. Multiple threads targeting the same 11 gateway nodes means heavy contention. The important thing is that the invariant check passes, proving no lock was lost or orphaned.
Throughput varies by machine, but you should see thousands of transactions per second even with the 100-microsecond sleep.
- To push harder, edit src/simulator.cpp and change numThreads to 16 for a more aggressive test.
- Recompile and run again:
g++ -std=c++17 -pthread -O2 src/simulator.cpp src/atomic_tree.cpp -Iinclude -o stress_test -latomic
./stress_test- You should see 16000 total transactions, higher contention (more failed locks and CAS retries), and the invariant check still passes.
Seeing invariant violations?
If verifyTreeInvariants reports a node still locked or a non-zero count, the bug is in your src/atomic_tree.cpp implementation. The most common cause is a CAS loop that exits without properly rolling back metadata on failure. Check that every fetch_add in your lock path has a matching fetch_sub in the failure/rollback path.
Help me debug invariant violations in my lock-free tree stress test.
- Set numThreads back to 8 for the final version, then save src/simulator.cpp.
- Commit your work:
git add src/simulator.cpp
git commit -m "Add concurrent transaction simulator with stress test and invariant verifier"- Push to GitHub:
git pushYour lock-free tree just survived thousands of concurrent transactions without a single invariant violation. Next up, you'll expose this engine through an HTTP API so the frontend dashboard can visualize it in real time.
Build the HTTP Backend and Frontend Dashboard
Your lock-free payment tree passes stress tests with thousands of concurrent transactions across 16 threads. But right now, nobody can see it in action. To showcase this system to interviewers or deploy it as a live service, you need a way for the outside world to interact with it.
In this step, you'll wire up an HTTP REST API using cpp-httplib that exposes your atomic tree's state and metrics as JSON endpoints. Then you'll build a D3.js dashboard that renders the payment hierarchy with color-coded lock states in real-time.
In this step, get ready to:
- Set up an HTTP server with REST endpoints for tree state, metrics, and concurrent simulation.
- Build a real-time D3.js frontend dashboard with live metrics and color-coded nodes.
- Build and verify the full system end-to-end with curl.
Write the HTTP backend server
The cpp-httplib header you downloaded earlier is a single-file HTTP library. You'll use it to create three REST endpoints that let the frontend (and curl) query tree state, read metrics, and trigger concurrent simulations.
- Open src/main.cpp in your editor and replace its entire contents with the following code. Start with the includes and the buildPaymentTree function:
#include "atomic_tree_node.h"
#include "httplib.h"
#include <iostream>
#include <thread>
#include <vector>
#include <random>
#include <chrono>
// Build the full payment gateway hierarchy
void buildPaymentTree(AtomicPaymentTree& tree) {
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("UPI", "PaymentSystem");
tree.addNode("Wallets", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("Mastercard", "Cards");
tree.addNode("RuPay", "Cards");
tree.addNode("GPay", "UPI");
tree.addNode("PhonePe", "UPI");
tree.addNode("BHIM", "UPI");
tree.addNode("Paytm", "Wallets");
tree.addNode("AmazonPay", "Wallets");
tree.addNode("HDFC", "Visa");
tree.addNode("ICICI", "Visa");
tree.addNode("SBI", "Mastercard");
tree.addNode("Axis", "Mastercard");
tree.addNode("PNB", "RuPay");
tree.addNode("BOB", "RuPay");
}What does this code do?
The includes pull in your AtomicPaymentTree class, the cpp-httplib header, and standard library headers for threading and random number generation.
The buildPaymentTree function constructs the full M-ary tree hierarchy. It mirrors the real-world payment routing path: PaymentSystem at the root, payment methods (Cards, UPI, Wallets), then gateways (Visa, Mastercard, GPay), then banks (HDFC, ICICI, SBI).
- Below buildPaymentTree, add the simulateTransactions function that each worker thread runs:
// Each worker thread runs this to simulate random payment transactions
void simulateTransactions(AtomicPaymentTree& tree, int threadId, int numTransactions) {
std::mt19937 rng(threadId * 42);
std::vector<std::string> gateways = {
"HDFC", "ICICI", "SBI", "Axis", "PNB", "BOB",
"GPay", "PhonePe", "BHIM", "Paytm", "AmazonPay"
};
std::uniform_int_distribution<int> dist(0, gateways.size() - 1);
for (int i = 0; i < numTransactions; i++) {
std::string target = gateways[dist(rng)];
tree.metrics.totalTransactions.fetch_add(1, std::memory_order_relaxed);
if (tree.lock(target, threadId)) {
tree.metrics.successfulLocks.fetch_add(1, std::memory_order_relaxed);
// Simulate transaction processing time
std::this_thread::sleep_for(std::chrono::microseconds(100));
tree.unlock(target, threadId);
} else {
tree.metrics.failedLocks.fetch_add(1, std::memory_order_relaxed);
}
}
}What does this code do?
Each thread picks a random gateway node, attempts to lock it, holds it briefly (simulating transaction processing), then unlocks it. The fetch_add calls atomically increment the metrics counters so the dashboard can track throughput and contention in real-time.
The seed threadId * 42 ensures each thread targets a different random sequence of gateways, creating realistic contention patterns.
- Finally, add the main() function that creates the tree, registers the HTTP endpoints, and starts the server:
int main() {
AtomicPaymentTree tree(3);
buildPaymentTree(tree);
std::cout << "=== Payment Gateway Orchestration Engine ===\n";
std::cout << "Starting HTTP server on http://localhost:8080\n\n";
httplib::Server svr;
// Serve static frontend files from the frontend/ directory
svr.set_mount_point("/", "./frontend");
// GET /api/tree - returns current tree state as JSON
svr.Get("/api/tree", [&tree](const httplib::Request&, httplib::Response& res) {
res.set_header("Access-Control-Allow-Origin", "*");
res.set_content(tree.toJson(), "application/json");
});
// GET /api/metrics - returns throughput and contention stats
svr.Get("/api/metrics", [&tree](const httplib::Request&, httplib::Response& res) {
res.set_header("Access-Control-Allow-Origin", "*");
std::string json = "{\"totalTransactions\":" +
std::to_string(tree.metrics.totalTransactions.load()) +
",\"successfulLocks\":" +
std::to_string(tree.metrics.successfulLocks.load()) +
",\"failedLocks\":" +
std::to_string(tree.metrics.failedLocks.load()) +
",\"casRetries\":" +
std::to_string(tree.metrics.casRetries.load()) + "}";
res.set_content(json, "application/json");
});
// POST /api/simulate - run a concurrent simulation with 8 threads
svr.Post("/api/simulate", [&tree](const httplib::Request&, httplib::Response& res) {
res.set_header("Access-Control-Allow-Origin", "*");
int numThreads = 8;
int txnPerThread = 100;
std::vector<std::thread> threads;
for (int i = 0; i < numThreads; i++) {
threads.emplace_back(simulateTransactions, std::ref(tree), i, txnPerThread);
}
for (auto& t : threads) {
t.join();
}
res.set_content("{\"status\":\"complete\",\"threads\":" +
std::to_string(numThreads) + ",\"txnPerThread\":" +
std::to_string(txnPerThread) + "}", "application/json");
});
svr.listen("0.0.0.0", 8080);
return 0;
}What does this code do?
The main() function is the server entry point. It creates an AtomicPaymentTree with branching factor 3, builds the payment hierarchy, then registers three endpoints.
- GET /api/tree returns the entire tree structure as JSON (nodes, lock states, children).
- GET /api/metrics returns cumulative throughput counters (total transactions, successful locks, failed locks, CAS retries).
- POST /api/simulate spawns 8 threads that each run 100 random transactions, then returns a summary once all threads join.
The set_mount_point("/", "./frontend") line tells cpp-httplib to serve static files from the frontend/ directory. When a browser visits http://localhost:8080, it automatically serves frontend/index.html.
- Save src/main.cpp.
✔️ Awesome, I've got everything!
Great. Double check you've saved src/main.cpp before moving on.
ⓧ I'd like to double check the full code
#include "atomic_tree_node.h"
#include "httplib.h"
#include <iostream>
#include <thread>
#include <vector>
#include <random>
#include <chrono>
void buildPaymentTree(AtomicPaymentTree& tree) {
tree.addNode("PaymentSystem");
tree.addNode("Cards", "PaymentSystem");
tree.addNode("UPI", "PaymentSystem");
tree.addNode("Wallets", "PaymentSystem");
tree.addNode("Visa", "Cards");
tree.addNode("Mastercard", "Cards");
tree.addNode("RuPay", "Cards");
tree.addNode("GPay", "UPI");
tree.addNode("PhonePe", "UPI");
tree.addNode("BHIM", "UPI");
tree.addNode("Paytm", "Wallets");
tree.addNode("AmazonPay", "Wallets");
tree.addNode("HDFC", "Visa");
tree.addNode("ICICI", "Visa");
tree.addNode("SBI", "Mastercard");
tree.addNode("Axis", "Mastercard");
tree.addNode("PNB", "RuPay");
tree.addNode("BOB", "RuPay");
}
void simulateTransactions(AtomicPaymentTree& tree, int threadId, int numTransactions) {
std::mt19937 rng(threadId * 42);
std::vector<std::string> gateways = {
"HDFC", "ICICI", "SBI", "Axis", "PNB", "BOB",
"GPay", "PhonePe", "BHIM", "Paytm", "AmazonPay"
};
std::uniform_int_distribution<int> dist(0, gateways.size() - 1);
for (int i = 0; i < numTransactions; i++) {
std::string target = gateways[dist(rng)];
tree.metrics.totalTransactions.fetch_add(1, std::memory_order_relaxed);
if (tree.lock(target, threadId)) {
tree.metrics.successfulLocks.fetch_add(1, std::memory_order_relaxed);
std::this_thread::sleep_for(std::chrono::microseconds(100));
tree.unlock(target, threadId);
} else {
tree.metrics.failedLocks.fetch_add(1, std::memory_order_relaxed);
}
}
}
int main() {
AtomicPaymentTree tree(3);
buildPaymentTree(tree);
std::cout << "=== Payment Gateway Orchestration Engine ===\n";
std::cout << "Starting HTTP server on http://localhost:8080\n\n";
httplib::Server svr;
svr.set_mount_point("/", "./frontend");
svr.Get("/api/tree", [&tree](const httplib::Request&, httplib::Response& res) {
res.set_header("Access-Control-Allow-Origin", "*");
res.set_content(tree.toJson(), "application/json");
});
svr.Get("/api/metrics", [&tree](const httplib::Request&, httplib::Response& res) {
res.set_header("Access-Control-Allow-Origin", "*");
std::string json = "{\"totalTransactions\":" +
std::to_string(tree.metrics.totalTransactions.load()) +
",\"successfulLocks\":" +
std::to_string(tree.metrics.successfulLocks.load()) +
",\"failedLocks\":" +
std::to_string(tree.metrics.failedLocks.load()) +
",\"casRetries\":" +
std::to_string(tree.metrics.casRetries.load()) + "}";
res.set_content(json, "application/json");
});
svr.Post("/api/simulate", [&tree](const httplib::Request&, httplib::Response& res) {
res.set_header("Access-Control-Allow-Origin", "*");
int numThreads = 8;
int txnPerThread = 100;
std::vector<std::thread> threads;
for (int i = 0; i < numThreads; i++) {
threads.emplace_back(simulateTransactions, std::ref(tree), i, txnPerThread);
}
for (auto& t : threads) {
t.join();
}
res.set_content("{\"status\":\"complete\",\"threads\":" +
std::to_string(numThreads) + ",\"txnPerThread\":" +
std::to_string(txnPerThread) + "}", "application/json");
});
svr.listen("0.0.0.0", 8080);
return 0;
}Create the frontend visualization dashboard
The frontend uses D3.js's tree layout algorithm to render the payment hierarchy as a node-link diagram. Nodes are color-coded by lock state: green for unlocked, red for locked.
- Create the frontend/ directory by running:
mkdir -p frontend- Create frontend/index.html and paste in the following dashboard code:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Payment Gateway Orchestration Engine</title>
<script src="https://d3js.org/d3.v7.min.js"></script>
<style>
* { margin: 0; padding: 0; box-sizing: border-box; }
body { font-family: 'Segoe UI', system-ui, sans-serif; background: #0f1419; color: #e7e9ea; }
.container { display: grid; grid-template-columns: 1fr 350px; height: 100vh; }
.tree-panel { padding: 20px; overflow: hidden; }
.sidebar { background: #1a1f25; padding: 20px; overflow-y: auto; border-left: 1px solid #2f3336; }
h1 { font-size: 1.4rem; margin-bottom: 10px; color: #1d9bf0; }
h2 { font-size: 1rem; margin: 15px 0 8px; color: #8b98a5; text-transform: uppercase; letter-spacing: 1px; }
.metric { background: #1e2732; border-radius: 8px; padding: 12px; margin-bottom: 8px; }
.metric-value { font-size: 1.5rem; font-weight: bold; color: #1d9bf0; }
.metric-label { font-size: 0.75rem; color: #8b98a5; }
.node circle { stroke-width: 2px; cursor: pointer; }
.node text { font-size: 11px; fill: #e7e9ea; }
.link { fill: none; stroke: #2f3336; stroke-width: 1.5px; }
.btn { background: #1d9bf0; color: white; border: none; padding: 10px 20px; border-radius: 20px; cursor: pointer; font-size: 0.9rem; width: 100%; margin-top: 10px; }
.btn:hover { background: #1a8cd8; }
.log { background: #1e2732; border-radius: 8px; padding: 10px; max-height: 200px; overflow-y: auto; font-family: monospace; font-size: 0.75rem; line-height: 1.6; }
.log-entry { border-bottom: 1px solid #2f3336; padding: 3px 0; }
.locked { fill: #f4212e; }
.unlocked { fill: #00ba7c; }
.contended { fill: #ffd400; }
</style>
</head>
<body>
<div class="container">
<div class="tree-panel">
<h1>Payment Gateway Orchestration Engine</h1>
<svg id="tree-svg" width="100%" height="90%"></svg>
</div>
<div class="sidebar">
<h2>Metrics</h2>
<div class="metric">
<div class="metric-value" id="total-txn">0</div>
<div class="metric-label">Total Transactions</div>
</div>
<div class="metric">
<div class="metric-value" id="success-locks">0</div>
<div class="metric-label">Successful Locks</div>
</div>
<div class="metric">
<div class="metric-value" id="failed-locks">0</div>
<div class="metric-label">Failed Locks (Contention)</div>
</div>
<div class="metric">
<div class="metric-value" id="cas-retries">0</div>
<div class="metric-label">CAS Retries</div>
</div>
<button class="btn" onclick="runSimulation()">Run Concurrent Simulation (8 threads)</button>
<h2>Transaction Log</h2>
<div class="log" id="log"></div>
</div>
</div>
<script>
const BACKEND_URL = '';
const DEMO_MODE = !window.location.hostname.includes('localhost') && !BACKEND_URL;
const DEMO_DATA = {name:"PaymentSystem",isLocked:false,children:[{name:"Cards",isLocked:false,children:[{name:"Visa",isLocked:true,children:[{name:"HDFC",isLocked:false,children:[]},{name:"ICICI",isLocked:false,children:[]}]},{name:"Mastercard",isLocked:false,children:[{name:"SBI",isLocked:true,children:[]},{name:"Axis",isLocked:false,children:[]}]},{name:"RuPay",isLocked:false,children:[{name:"PNB",isLocked:false,children:[]},{name:"BOB",isLocked:false,children:[]}]}]},{name:"UPI",isLocked:false,children:[{name:"GPay",isLocked:false,children:[]},{name:"PhonePe",isLocked:true,children:[]},{name:"BHIM",isLocked:false,children:[]}]},{name:"Wallets",isLocked:false,children:[{name:"Paytm",isLocked:false,children:[]},{name:"AmazonPay",isLocked:false,children:[]}]}]};
function apiUrl(path) { return BACKEND_URL ? BACKEND_URL + path : path; }
async function fetchTree() {
if (DEMO_MODE) return DEMO_DATA;
try { const res = await fetch(apiUrl('/api/tree')); return await res.json(); }
catch(e) { return DEMO_DATA; }
}
async function fetchMetrics() {
if (DEMO_MODE) { document.getElementById('total-txn').textContent = '847'; document.getElementById('success-locks').textContent = '612'; document.getElementById('failed-locks').textContent = '235'; document.getElementById('cas-retries').textContent = '89'; return; }
try {
const res = await fetch(apiUrl('/api/metrics'));
const data = await res.json();
document.getElementById('total-txn').textContent = data.totalTransactions;
document.getElementById('success-locks').textContent = data.successfulLocks;
document.getElementById('failed-locks').textContent = data.failedLocks;
document.getElementById('cas-retries').textContent = data.casRetries;
} catch(e) {}
}
async function runSimulation() {
if (DEMO_MODE) { const log = document.getElementById('log'); log.innerHTML = '<div class="log-entry">[DEMO] Simulation: 8 threads x 100 txns</div>' + log.innerHTML; return; }
const res = await fetch(apiUrl('/api/simulate'), { method: 'POST' });
const data = await res.json();
const log = document.getElementById('log');
log.innerHTML = '<div class="log-entry">Simulation complete: ' + data.threads + ' threads x ' + data.txnPerThread + ' txns</div>' + log.innerHTML;
fetchMetrics();
renderTree();
}
async function renderTree() {
const data = await fetchTree();
const svg = d3.select('#tree-svg');
svg.selectAll('*').remove();
const width = svg.node().getBoundingClientRect().width;
const height = svg.node().getBoundingClientRect().height;
const g = svg.append('g').attr('transform', 'translate(40,40)');
const root = d3.hierarchy(data);
const treeLayout = d3.tree().size([width - 80, height - 80]);
treeLayout(root);
g.selectAll('.link').data(root.links()).join('path')
.attr('class', 'link')
.attr('d', d3.linkVertical().x(d => d.x).y(d => d.y));
const nodes = g.selectAll('.node').data(root.descendants()).join('g')
.attr('class', 'node')
.attr('transform', d => 'translate(' + d.x + ',' + d.y + ')');
nodes.append('circle').attr('r', 8)
.attr('class', d => d.data.isLocked ? 'locked' : 'unlocked');
nodes.append('text').attr('dy', -12).attr('text-anchor', 'middle')
.text(d => d.data.name);
}
renderTree();
fetchMetrics();
if (!DEMO_MODE) setInterval(fetchMetrics, 1000);
</script>
</body>
</html>What does this dashboard do?
- D3.js's d3.tree() computes a tidy node-link layout from the hierarchical JSON returned by /api/tree.
- Nodes get the CSS class locked (red) or unlocked (green) based on their isLocked field. A contended class (amber) is available for future use.
- The sidebar displays live metrics from /api/metrics, polling every 1000ms when the backend is reachable.
- The DEMO_MODE fallback lets the page work with static mock data when hosted on GitHub Pages without the C++ backend running.
- Save frontend/index.html.
Not sure you got all the code?
The HTML file is long. If you're unsure about copy-paste accuracy, compare your file against the double-check tab above for src/main.cpp and ensure your index.html opens with <!DOCTYPE html> and ends with </html>.
help me verify my frontend/index.html is complete
Build and test the system
With both files in place, you can now compile the project and verify each endpoint responds correctly.
- Build the project by running:
make- You should see the compilation complete without errors and produce the payment_engine binary.
- Start the server by running:
./payment_engine- You should see the output:
=== Payment Gateway Orchestration Engine ===
Starting HTTP server on http://localhost:8080- Open a second terminal tab and test the tree endpoint by running:
curl http://localhost:8080/api/tree- You should see a JSON response with the full tree structure including name, isLocked, and children fields for each node.
- Test the metrics endpoint by running:
curl http://localhost:8080/api/metrics- You should see a JSON response like {"totalTransactions":0,"successfulLocks":0,"failedLocks":0,"casRetries":0} (all zeros because no simulation has run yet).
- Trigger a simulation by running:
curl -X POST http://localhost:8080/api/simulate- You should see {"status":"complete","threads":8,"txnPerThread":100} confirming 8 threads each ran 100 transactions.
- Open your browser and navigate to http://localhost:8080. You should see the dark-themed dashboard with the payment tree visualization on the left and metrics on the right.
- Stop the server by pressing Ctrl+C in the terminal where it's running.
Build failing or server not starting?
- If make shows a missing httplib.h error, confirm the file is in your include/ directory. The Makefile passes -Iinclude to the compiler.
- If you see a linker error about atomic, make sure your Makefile includes -latomic in LDFLAGS.
- If curl shows "Connection refused", confirm the server is still running in the other terminal tab and listening on port 8080.
help me debug my payment engine build or server startup issue
- Commit your changes by running:
git add src/main.cpp frontend/index.html
git commit -m "Add HTTP backend and frontend visualization dashboard"Your payment engine now has a web interface. Anyone with your URL can see the tree state, trigger simulations, and watch contention metrics update in real-time. Next up, you'll deploy this live on AWS EC2 and host the frontend on GitHub Pages so you can share it with interviewers.
Deploy to AWS EC2 and GitHub Pages
Your payment gateway engine runs beautifully on your local machine. Now it is time to share it with the world.
In this step, you will deploy the C++ backend to a live AWS EC2 instance and publish the frontend dashboard on GitHub Pages. This gives you two shareable URLs: one for the real-time backend API and one for the interactive visualization.
In this step, get ready to:
- Launch and configure an EC2 instance running your compiled backend.
- Deploy the frontend to GitHub Pages with demo mode fallback.
- Update the README with live links and EC2 start/stop instructions.
Launch an EC2 instance and run the backend
EC2 gives you a virtual server in the cloud where your compiled C++ binary can serve HTTP traffic to anyone on the internet. You will launch a free-tier eligible instance, install the compiler, and run your payment engine.
- Sign in to the AWS Management Console at console.aws.amazon.com.
- In the search bar at the top, type EC2 and select the EC2 service.
- Click Launch instance on the EC2 Dashboard.
- Under Name and tags, enter payment-gateway-engine as the instance name.
- Under Application and OS Images (Amazon Machine Image), choose Quick Start, then select Amazon Linux. Confirm the AMI is marked Free Tier eligible (Amazon Linux 2023).
- Under Instance type, select t2.micro (Free Tier eligible).
- Under Key pair (login), click Create new key pair.
- Enter payment-engine-key as the name. Select RSA for the key type and .pem for the format.
- Click Create key pair. The .pem file downloads automatically. Save it somewhere safe.
- Under Network settings, click Edit to configure the security group.
- Add two inbound rules: SSH on port 22 (Source: Anywhere) and Custom TCP on port 8080 (Source: Anywhere).
- Leave Configure storage at the default 8 GB.
- In the Summary panel, review your settings, then click Launch instance.
- Wait for the instance state to change from pending to running. Copy the Public IPv4 address from the instance details.
What is a security group?
A security group is a virtual firewall for your EC2 instance. Port 22 allows SSH connections so you can access the server. Port 8080 allows HTTP traffic so browsers can reach your payment engine API.
Now SSH into your instance and set up the build environment. Set the correct permissions on your key file first by running this command:
chmod 400 ~/Downloads/payment-engine-key.pem- Connect to your EC2 instance by running this command (replace the IP with your instance's public IP):
ssh -i ~/Downloads/payment-engine-key.pem ec2-user@[[EC2_PUBLIC_IP="your EC2 public IPv4 address"]]You should see a welcome message from Amazon Linux. You are now inside your remote server.
- Install the C++ compiler by running:
sudo dnf install gcc-c++ -y- Clone your GitHub repository onto the instance by running:
git clone [[REPO_URL="https://github.com/YOUR_USERNAME/payment-gateway-engine.git"]]
cd payment-gateway-engine- Compile the project by running:
make- Start the binary as a background process by running:
nohup ./payment_engine &- Verify the backend is accessible by running:
curl http://localhost:8080/api/treeYou should see a JSON response containing your payment tree structure. The backend is now live.
What does nohup do?
The nohup command tells Linux to keep the process running even after you close the SSH session. The & puts it in the background so you can continue typing commands.
- Open a browser on your local machine and navigate to http://your EC2 public IP:8080/api/tree.
- You should see the same JSON tree response in your browser. Your backend is publicly accessible.
Connection timed out?
If the browser cannot connect, check that your security group has port 8080 open. In the EC2 console, select your instance, go to the Security tab, click the security group link, and verify the inbound rules include Custom TCP on port 8080.
Also confirm the process is still running on the instance with ps aux | grep payment_engine.
Why can't I reach my EC2 backend on port 8080?
Deploy the frontend to GitHub Pages
GitHub Pages serves static files for free from any public repository. You will copy your frontend into a docs/ folder and configure Pages to publish from there.
- Back on your local machine (exit the SSH session if needed), open frontend/index.html in your code editor.
- Find this line near the top of the <script> section:
const BACKEND_URL = '';- Replace it with your EC2 public IP so the GitHub Pages frontend connects to your live backend:
const BACKEND_URL = 'http://[[EC2_PUBLIC_IP="your EC2 public IPv4 address"]]:8080';What about demo mode?
The frontend already has fallback logic built in. If BACKEND_URL is set but the backend is unreachable (for example, the EC2 instance is stopped), the fetchTree() function catches the error and falls back to DEMO_DATA. Your GitHub Pages site stays interactive regardless of whether the backend is running.
- Create the docs/ folder and copy the frontend files into it by running these commands from your project root:
cp -r frontend/ docs/- Copy the updated index.html (with the BACKEND_URL set) into docs/ as well:
cp frontend/index.html docs/index.html- Create the .nojekyll file to prevent GitHub from processing the site with Jekyll:
touch docs/.nojekyllWhy .nojekyll?
GitHub Pages processes sites through Jekyll by default. Adding an empty .nojekyll file tells GitHub to serve your static HTML directly without any build processing.
- Commit and push the docs folder by running:
git add docs/
git commit -m "Add docs/ for GitHub Pages deployment"
git push origin mainNow enable GitHub Pages in your repository settings:
- Open your repository on GitHub in a browser.
- Click Settings in the repository navigation.
- In the Code and automation section of the sidebar, click Pages.
- Under Build and deployment, under Source, select Deploy from a branch.
- Use the branch dropdown to select main.
- Use the folder dropdown to select /docs.
- Click Save.
GitHub will build and deploy your site within a minute or two. Your frontend will be live at https://your GitHub username.github.io/payment-gateway-engine.
Page shows a 404?
GitHub Pages can take a few minutes to deploy. Check the Actions tab in your repository to see if the deployment workflow is still running.
Also confirm that docs/index.html exists in your repository on the main branch. GitHub Pages requires an index.html at the top level of the publishing source.
My GitHub Pages site shows a 404. How do I fix it?
Update the README with live links and EC2 instructions
Anyone visiting your GitHub repository should immediately see how to access the live demo and how to start or stop the EC2 instance for cost management.
- Open README.md in your code editor.
- Replace the entire file contents with the following updated README:
# Payment Gateway Orchestration Engine
A production-grade C++ lock-free concurrent tree system modeling Juspay's 'Tree of Space' hackathon problem as a real payment routing system.
**Live Demo**: https://<username>.github.io/payment-gateway-engine
**Backend**: http://<public-ip>:8080
## Architecture
```mermaid
graph TD
A[PaymentSystem] --> B[Cards]
A --> C[UPI]
A --> D[Wallets]
B --> E[Visa]
B --> F[Mastercard]
B --> G[RuPay]
C --> H[GPay]
C --> I[PhonePe]
C --> J[BHIM]
D --> K[Paytm]
D --> L[AmazonPay]
```
## Build
```bash
make
./payment_engine
```
## EC2 Demo Instructions
To start the backend for demos:
1. AWS Console -> EC2 -> Select instance -> Instance state -> Start
2. SSH in and run: `nohup ./payment_engine &`
To stop after demo (avoid charges):
- AWS Console -> EC2 -> Select instance -> Instance state -> Stop
- Stopped instance costs ~$0.80/month for EBS disk onlyWhat should I put in the Live Demo and Backend lines?
Replace <username> with your actual GitHub username and <public-ip> with your EC2 instance's public IPv4 address. These make your README immediately actionable for anyone who finds your repository.
- Save README.md, then commit and push by running:
git add README.md frontend/index.html
git commit -m "Add live demo links and EC2 start/stop instructions"
git push origin mainYour GitHub Pages site will automatically redeploy with the latest docs/ content after the push.
Keep costs near zero
Stop your EC2 instance whenever you are not actively demoing. A stopped t2.micro costs only about $0.80/month for the 8 GB EBS disk. The GitHub Pages frontend stays live for free regardless, falling back to demo mode when the backend is unreachable.
You now have two shareable URLs: a GitHub Pages frontend anyone can interact with, and an EC2 backend that powers live data when running. Next up, you will write interview talking points that explain every design decision you have made.
Write Interview Documentation and Polish the Repository
Your payment gateway engine is deployed and working. The code proves you can build lock-free concurrent systems. But in a Juspay hackathon interview, working code is only half the battle.
Interviewers evaluate your ability to justify design choices and discuss trade-offs. In this step, you will write structured interview documentation, create a design document with sequence diagrams, and polish your GitHub repository into a professional portfolio piece.
In this step, get ready to:
- Write an interview guide with structured answers to common follow-up questions.
- Create a design document with memory ordering explanations and a CAS retry sequence diagram.
- Polish the README with API docs, tag release v1.0.0, and push everything to GitHub.
Create the interview guide
Juspay's Hackathon Part B evaluators ask follow-up questions about your concurrency approach. Having pre-written, structured answers means you can speak confidently about every design decision under pressure.
- Create a new file called INTERVIEW_GUIDE.md in your project root (the payment-gateway-engine folder) by running:
touch INTERVIEW_GUIDE.md- Open INTERVIEW_GUIDE.md in your editor and paste the following content:
# Interview Guide
## Why not use a mutex?
Mutexes block threads, causing context switches and priority inversion. Our CAS-based approach is non-blocking: threads retry in a tight loop without OS involvement, giving lower latency under low contention.
## How does your lock achieve O(log_m N)?
By maintaining ancestorLockedCount and descendantLockedCount metadata on each node, we avoid full tree traversal. Checking ancestors/descendants is O(depth) = O(log_m N) for a balanced M-ary tree.
## What happens if a thread dies mid-lock?
The node remains locked indefinitely (no automatic release). Production systems add heartbeat timeouts or lease-based locks to handle this.
## How would you scale to millions of nodes?
Partition the tree across shards, use per-subtree locks, and add a distributed coordination layer (e.g., etcd) for cross-shard locking.
## Trade-off Analysis
- compare_exchange_weak vs strong: weak may spuriously fail but is faster on some architectures; use weak in retry loops.
- memory_order_seq_cst vs acquire/release: seq_cst is simpler but adds full barriers; acquire/release is sufficient for our producer-consumer pattern.
- Per-node atomics vs global lock: per-node allows fine-grained concurrency; global lock is simpler but serializes all operations.What does this document cover?
The interview guide addresses four questions that Juspay interviewers commonly ask about lock-free systems. Each answer is concise enough to deliver in 30 seconds while demonstrating deep understanding.
The trade-off analysis section shows you can think beyond "it works" to explain WHY you chose one approach over another. This is exactly what separates passing candidates from those who get rejected.
- Save INTERVIEW_GUIDE.md.
- Confirm the file exists by running:
ls INTERVIEW_GUIDE.md- You should see INTERVIEW_GUIDE.md in the output.
Practice out loud
Read each answer aloud as if explaining to an interviewer. Time yourself. Each answer should take 20-40 seconds to deliver naturally. If it takes longer, trim it. If it feels rushed, slow down and focus on the key insight.
File not showing up?
Make sure you ran touch from within the payment-gateway-engine folder. If you are in a subdirectory like src/, navigate back to the project root first with cd ...
Why isn't my INTERVIEW_GUIDE.md file appearing in the correct location?
Create the design document
A design document shows reviewers (and interviewers) your system-level thinking. It captures the architecture decisions that aren't obvious from reading code alone.
- Create a new file called DESIGN.md in your project root by running:
touch DESIGN.md- Open DESIGN.md in your editor and paste the following content:
# Design Document
## Lock-Free Concurrency Approach
Each node carries atomic integers for lockState, lockedBy, ancestorLockedCount, and descendantLockedCount. Lock acquisition uses a CAS retry loop: read current state, verify preconditions, attempt compare_exchange_weak. On failure, retry.
## Memory Ordering
- Reads use memory_order_acquire to see all prior writes by the locking thread.
- Writes use memory_order_release to publish state to other threads.
- fetch_add/fetch_sub on counters use memory_order_acq_rel.
## CAS Retry Loop Sequence
```mermaid
sequenceDiagram
participant T1 as Thread 1
participant N as Node (atomic)
T1->>N: load lockState (acquire)
T1->>T1: check preconditions
T1->>N: CAS(0 -> 1)
alt CAS succeeds
N-->>T1: lock acquired
else CAS fails
N-->>T1: spurious/contention
T1->>T1: increment casRetries
T1->>N: retry loop
end
```
## Performance Characteristics
O(log_m N) lock/unlock. CAS retry rate increases with thread count. Stress tests show <5% retry rate at 8 threads on leaf nodes.What does this document cover?
The design document has four sections. The concurrency approach explains your overall strategy. The memory ordering section justifies why you use memory_order_acquire and memory_order_release instead of the simpler (but slower) memory_order_seq_cst.
The Mermaid sequence diagram renders natively on GitHub as an interactive diagram. It shows exactly how the CAS retry loop works when two threads contend for the same node.
Why Mermaid diagrams?
GitHub renders Mermaid code blocks as visual diagrams automatically. You do not need any plugins or external tools. Anyone viewing your repository sees a professional sequence diagram without extra setup.
- Save DESIGN.md.
- Confirm both documentation files exist by running:
ls *.md- You should see DESIGN.md, INTERVIEW_GUIDE.md, and README.md in the output.
Not seeing all three files?
Check that you are in the project root directory. Run pwd to see your current location. You should be inside the payment-gateway-engine directory.
Help me find where my markdown files ended up in my project.
Polish the README and tag the release
Your README already has the architecture diagram and build instructions. The final polish is adding API documentation so anyone visiting your repo knows exactly how to interact with the running server.
- Open README.md in your editor.
- Find the ## Build section. It currently looks like this:
## Build
```bash
make
./payment_engine
```
## EC2 Demo Instructions- Add a new ## API section between the Build section and the EC2 Demo Instructions section, so it looks like this:
## Build
```bash
make
./payment_engine
```
## API
- `GET /api/tree` - Current tree state as JSON
- `GET /api/metrics` - Throughput and contention stats
- `POST /api/simulate` - Run 8-thread concurrent simulation
## EC2 Demo Instructions- Also in the EC2 Demo Instructions section, find and delete the line that says - Stopped instance costs ~$0.80/month for EBS disk only.
- Save README.md.
Why document the API endpoints?
Anyone who clones your repo (including an interviewer testing your project) needs to know which endpoints exist. Listing them in the README saves them from reading your source code to figure out how to interact with the server.
Now commit all documentation and tag the release.
- Stage and commit all new documentation by running these commands:
git add INTERVIEW_GUIDE.md DESIGN.md README.md
git commit -m "Add interview guide, design doc, and API documentation"- Tag the release as v1.0.0 by running:
git tag v1.0.0- Push everything to GitHub (including the tag) by running:
git push origin main --tags- Verify the tag was created by running:
git tag- You should see v1.0.0 in the output.
What does tagging a release do?
A Git tag marks a specific commit as a named release point. On GitHub, tags appear under the Releases section of your repository. Interviewers and recruiters browsing your repo see a polished, versioned project rather than a stream of loose commits.
Push rejected?
If the push fails with a permission error, make sure your Git credentials are configured correctly. If you are using HTTPS, GitHub requires a personal access token instead of your password.
Help me fix my Git push authentication error.
✔️ Awesome, I've got everything!
Great. Double check you have saved all three files and pushed to GitHub.
ⓧ I'd like to double check the full README
Here is the complete README.md as it should look now:
# Payment Gateway Orchestration Engine
A production-grade C++ lock-free concurrent tree system modeling Juspay's 'Tree of Space' hackathon problem as a real payment routing system.
**Live Demo**: https://<username>.github.io/payment-gateway-engine
**Backend**: http://<public-ip>:8080
## Architecture
```mermaid
graph TD
A[PaymentSystem] --> B[Cards]
A --> C[UPI]
A --> D[Wallets]
B --> E[Visa]
B --> F[Mastercard]
B --> G[RuPay]
C --> H[GPay]
C --> I[PhonePe]
C --> J[BHIM]
D --> K[Paytm]
D --> L[AmazonPay]
```
## Build
```bash
make
./payment_engine
```
## API
- `GET /api/tree` - Current tree state as JSON
- `GET /api/metrics` - Throughput and contention stats
- `POST /api/simulate` - Run 8-thread concurrent simulation
## EC2 Demo Instructions
To start the backend for demos:
1. AWS Console -> EC2 -> Select instance -> Instance state -> Start
2. SSH in and run: `nohup ./payment_engine &`
To stop after demo (avoid charges):
- AWS Console -> EC2 -> Select instance -> Instance state -> StopYour project is complete. You have a professional, interview-ready repository with working code, live deployment, design documentation, and structured talking points. Next up is a bonus challenge that takes your concurrency skills even further.
Secret mission
Priority Queue with Fairness Guarantees
Your lock-free tree handles concurrent transactions, but in the real world not all transactions are equal. A recurring subscription payment should get gateway access before a one-off low-value transaction. Can you build a lock-free priority queue that enforces this ordering while preventing starvation of lower-priority transactions?
Clean Up Your Resources
Clean Up Your Resources
This project uses an AWS EC2 instance that can incur charges if left running. Decide whether to keep your resources running, pause them to come back later, or delete them entirely.
Cost warning
Your EC2 t2.micro instance is free-tier eligible for 750 hours per month. If you exceed that, or if your free-tier year has expired, leaving the instance running costs money.
A stopped instance costs approximately $0.80/month for the 8GB EBS disk. Terminating the instance removes all charges. Your GitHub Pages frontend stays live for free regardless.
Resources you used:
- AWS EC2 t2.micro instance (running backend on port 8080, with security group and EBS volume).
- GitHub repository (payment-gateway-engine) with GitHub Pages enabled.
- Local project directory (payment-gateway-engine on your Desktop).
Keep everything running
No action needed. Choose this if you're still actively building or want the live demo available for immediate showcase.
- Your EC2 instance stays running and accessible at its public IP on port 8080.
- Your GitHub Pages frontend remains live at your github.io URL.
- Your local project files stay on your Desktop.
Pause - I'll come back to this later
Stop the EC2 instance to avoid compute charges while keeping your work intact. You can restart it any time for demos.
- Open the AWS Console and navigate to the EC2 service.
- Click Instances in the left navigation pane.
- Select your instance by checking the box next to it.
- Click Instance state, then select Stop instance.
- Confirm by clicking Stop.
A stopped instance costs approximately $0.80/month for the 8GB EBS disk. Your GitHub Pages frontend continues to work in demo mode (using mock data) while the backend is stopped.
Delete - I don't want to use this again
Remove all project resources and start fresh. This is permanent and removes all charges.
Terminate the EC2 instance
- Open the AWS Console and navigate to the EC2 service.
- Click Instances in the left navigation pane.
- Select your instance by checking the box next to it.
- Click Instance state, then select Terminate instance.
- Confirm by clicking Terminate. The instance state changes to shutting-down and then terminated. This also deletes the attached EBS volume and security group.
Delete the GitHub repository
- Go to your repository's main page on GitHub.
- Click the Settings tab near the top of the page.
- Scroll down to the Danger Zone section at the bottom.
- Click Delete this repository.
- Type the repository name to confirm, then click the final deletion button. This also disables GitHub Pages.
Delete local project files
- Remove the project directory from your Desktop by running this command:
macOS
rm -rf ~/Desktop/payment-gateway-engineWindows
rmdir /s /q %USERPROFILE%\Desktop\payment-gateway-engineThat's a Wrap!
That's a Wrap!
Nice work! You've just built a production-grade lock-free concurrent system that directly mirrors Juspay's hackathon challenge.
You've learned how to:
- Build a lock-free M-ary tree with Lock, Unlock, and UpgradeLock operations using only atomic CAS operations and deploy it as a live backend on AWS EC2.
- Create a real-time visualization dashboard with D3.js and deploy it on GitHub Pages, complete with live metrics, color-coded lock states, and a concurrent transaction simulator.
- Produce interview-ready documentation with architecture diagrams, memory ordering trade-off analysis, and structured talking points that prepare you for Juspay's hackathon follow-up questions.
- Implement a lock-free priority queue with fairness promotion guarantees and a contention heatmap overlay visualizing CAS retry hotspots across the tree.
Ready to quiz yourself?