# My Interview Experience at Juspay, 6 Interview Rounds | Tree of Space | Juspay

Few weeks ago, Juspay visited our campus (IIIT Nagpur), for SDE Intern position, 40k stipend + 27 LPA PPO.

Here is the detailed Hiring process:

**Round 1** - Aptitude (Online)  
• Participants - approx. 350  
• Time - 60 mins  
• 16 MCQ Questions  
• Topics - CS, System, Maths, Physics

**Round 2** - Online Assessment (DSA Round)  
• Participants - approx. 83  
• Time - 90 mins  
• 3 DSA Questions  
• Topics - Tree, Graph, Sliding Window  
• Approx 50 student shortlisted in this round

**Round 3** - Hackathon Part A (Hacker Earth) Tree of Space  
• Participants - 50  
• Time - 180 mins  
• Tree of Space (very famous problem of Juspay) - Implement 3 functions: Lock, Unlock and Upgrade  
• Topics - Tree, Graph, OOP  
• Below a detailed solution of Tree of Space problem.

**Round 4** - Elimination Round \[NEW!\] (GMeet)  
• Interviewer - **ADITYA KUMAR** 🧠🐐  
• Participants - 30  
• Time - 60-120 mins  
• Interview - Resume, Projects, Experience, CS Fundamentals, 1 Coding Question (DSA/CP)  
• Topics (For coding question) - I was asked a CP Question, first attempt passed 13 testcase but left 2, then interviewer gave me some hints and then I fix the code. It was held on Google Docs and Vs Code.

**Round 5** - Hackathon Part B (Slack + GMeet) | optimise Tree of space and make it thread safe.  
• Interviewer - **SANDEEP S J**💡💯  
• Participants - 15  
• Time - 8 hours  
• i) Explaining the complete approach of Part A and deriving time and space complexities. Some derivations like no. of a leaf node of a m-ary tree of height h.  
ii) Improving time and space complexities.  
iii) Making the solution thread-safe by introducing locking mechanisms. I wasn’t allowed to lock the entire tree or use any atomic variables. I used Mutex, but it kills concurrency, you have to do it with logical approach, so if other thread processing a node of tree, other nodes know the result and their threads do not have to wait for that thread. A detailed solution given below.  
• Topics - Parallel Computing, Threading, locking, lock and test.

**Round 6** - Technical Interview (GMeet)  
• Interviewer - Piyush Banka🫡  
• Participants - 6  
• Time - 20 mins  
• Interview/Discussion  
• Topics - Puzzle / Problem solving  
• Problem Statement - I was asked to find the relation in height of a binary tree and number of nodes, (to prove h = log (N) ) without using any mathematical formula, just logically. I was not able to answer it, I was thinking in one direction, GP : 1 + 2 + 4 + ...... = N but he was not asking about it.

A logical solution is given below.

After this round, 2 students got selected for the offline round and both got the offer!

**Number of leaf nodes in m-ary Tree:**

![](https://cdn.hashnode.com/uploads/covers/66f415e73faa423f90640bd1/a14e1fd0-22e3-42ee-b7e4-d68b2bbdc968.png align="center")

**Solution of Part A hackathon | Tree of Space:**

![](https://cdn.hashnode.com/uploads/covers/66f415e73faa423f90640bd1/5c1b30ca-c246-4b86-a6c6-6ef17313ae36.png align="center")

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

struct Node{
	string name;
	Node* parent;
	bool isLocked;
	int lockedBy;
	unordered_set<Node*> lockedDescendants;

	Node(string n, Node* p){
		name = n;
		parent = p;
		isLocked = false;
		lockedBy = -1;
	}
};

class Tree{
	Node* root;
	unordered_map<string, Node*> nodeMap;

public: 
	Tree(vector<string>nodes, int m){
		int n = nodes.size();
		root = new Node(nodes[0], nullptr);
		nodeMap[nodes[0]] = root;
		queue<Node*>q;
		q.push(root);

		int index = 1;
		while(!q.empty() && index<n){
			Node* curr = q.front();
			q.pop();

			for(int i=0; i<m && index<n; i++){
				Node* child = new Node(nodes[index], curr);
				nodeMap[nodes[index]] = child;
				q.push(child);
				index++;
			}
		}
	}

	bool lock(string name, int id){
		Node * node =  nodeMap[name];
		if(node->isLocked || !node->lockedDescendants.empty()) return false;
		Node* curr = node->parent;
		while(curr){
			if(curr->isLocked) return false;
			curr = curr->parent;
		}
		curr = node->parent;
		while(curr){
			curr->lockedDescendants.insert(node);
			curr = curr->parent;
		}
		

		node->isLocked = true;
		node->lockedBy = id;
		return true;
	}
	bool unlock(string name, int id){
		Node* node = nodeMap[name];
		if(!node->isLocked || node-> lockedBy != id) return false;
		Node* curr = node-> parent;
		while (curr) {
			curr->lockedDescendants.erase(node);
			curr = curr->parent;
		}
		node->isLocked = false;
		node->lockedBy = -1;
		return true;
	}

	bool upgrade(string name, int id){
		Node* node = nodeMap[name];
		if(node->isLocked || node->lockedDescendants.empty()) return false;
		for(Node* desc : node->lockedDescendants){
			if(desc-> lockedBy != id) return false;
		}
		Node* curr = node->parent;
		while(curr){
			if(curr->isLocked) return false;
			curr =  curr->parent;
		}
	unordered_set<Node*> descToUnlock = node->lockedDescendants;
		for(Node* desc: descToUnlock){
			unlock(desc->name, id);
		}
		lock(name, id);
		return true;
	}
};

int main(){
	int m,n,q;
	cin>>n>>m>>q;

	vector<string> nodes(n);
	for(int i=0; i<n; i++){
		cin>> nodes[i];
	}
	Tree tree(nodes, m);
	for(int i=0; i<q; i++){
		int type, id;
		string name;
		cin>>type>>name>>id;
		bool result=false;
		if(type==1) result = tree.lock(name, id);
		else if(type==2)	result = tree.unlock(name, id);
		else if(type==3)	result = tree.upgrade(name, id);
		if(result) cout<<"true \n";
		else cout<<"false \n";
	}
	return 0;
}
```

**Solution of Part B hackathon | Tree of Space | Thread space and optimised part A :**

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

struct Node{
	string name;
	Node* parent;
	bool isLocked;
	int lockedBy;
	unordered_set<Node*> lockedDescendants;

	Node(string n, Node* p){
		name = n;
		parent = p;
		isLocked = false;
		lockedBy = -1;
	}
};

class Tree{
	Node* root;
	unordered_map<string, Node*> nodeMap;

public:
	Tree(vector<string>nodes, int m){
		int n = nodes.size();
		root = new Node(nodes[0], nullptr);
		nodeMap[nodes[0]] = root;
		queue<Node*>q;
		q.push(root);

		int index = 1;
		while(!q.empty() && index<n){
			Node* curr = q.front();
			q.pop();

			for(int i=0; i<m && index<n; i++){
				Node* child = new Node(nodes[index], curr);
				nodeMap[nodes[index]] = child;
				q.push(child);
				index++;
			}
		}
	}

	bool lock(string name, int id){
		Node * node =  nodeMap[name];
		if(node->isLocked || !node->lockedDescendants.empty()) return false;
		Node* curr = node->parent;
		while(curr){
			if(curr->isLocked) return false;
			curr = curr->parent;
		}
		curr = node->parent;
		while(curr){
			curr->lockedDescendants.insert(node);
			curr = curr->parent;
		}
		

		node->isLocked = true;
		node->lockedBy = id;
		return true;
	}
	bool unlock(string name, int id){
		Node* node = nodeMap[name];
		if(!node->isLocked || node-> lockedBy != id) return false;
		Node* curr = node-> parent;
		while (curr) {
			curr->lockedDescendants.erase(node);
			curr = curr->parent;
		}
		node->isLocked = false;
		node->lockedBy = -1;
		return true;
	}

	bool upgrade(string name, int id){
		Node* node = nodeMap[name];
		if(node->isLocked || node->lockedDescendants.empty()) return false;
		for(Node* desc : node->lockedDescendants){
			if(desc-> lockedBy != id) return false;
		}

	unordered_set<Node*> descToUnlock = node->lockedDescendants;
		for(Node* desc: descToUnlock){
			Node* par = dec->parent;
          	desc->isLocked = false;
          	desc->lockedBy = -1;
          	while(par != node){
              if(par->lockedDescendants.empty()) break;
              	par->lockedDescendants.clear();
              	par = par->parent;
			}
          	par->lockedDescendants.clear();
		}
      	Node* par = node->parent;
      	while(par){
          for(Node* desc: descToUnlock) par->lockedDescendants.erase(desc);
          par = par->parent;
		}
		lock(name, id);
		return true;
	}
};

int main(){
	int m,n,q;
	cin>>n>>m>>q;

	vector<string> nodes(n);
	for(int i=0; i<n; i++){
		cin>> nodes[i];
	}
	Tree tree(nodes, m);
	for(int i=0; i<q; i++){
		int type, id;
		string name;
		cin>>type>>name>>id;
		bool result=false;
		if(type==1) result = tree.lock(name, id);
		else if(type==2)	result = tree.unlock(name, id);
		else if(type==3)	result = tree.upgrade(name, id);
		if(result) cout<<"true \n";
		else cout<<"false \n";
	}
	return 0;
}




struct Node{
	string name;
	Node* parent;
	int isLocked;
  	int sibLock;
	int lockedBy;
	unordered_set<Node*> lockedDescendants;


	Node(string n, Node* p){
		name = n;
		parent = p;
		isLocked = false;
		lockedBy = -1;
	}
};




	bool lock(string name, int id){
		Node * node =  nodeMap[name];
      	node->isLocked++;

		if(node->isLocked > 1 || !node->lockedDescendants.empty() || sibLock){
          	 node->isLocked--;
			 return false;
        }
		Node* curr = node->parent;
		while(curr){
          	curr->lockedDescendants.insert(node);
			if(curr->isLocked >0 ){
              Node* curr2 = node->parent;
              while(curr2 != curr){
          		curr2->lockedDescendants.erase(node);
  				curr2 = curr2->parent;
			  }
              curr->lockedDescendants.erase(node);
              node->isLocked--;
			  return false;
			}
			curr = curr->parent;
          	
		}

		node->lockedBy = id;
		return true;
	}
```

**Solution of System round:**

height of a binary tree logically

![](https://cdn.hashnode.com/uploads/covers/66f415e73faa423f90640bd1/b1e76da1-3b76-4f1e-8c96-220f4284c237.png align="center")