Juspay Tree of Space Hackathon Part B Thread Safe
Mohit Panjikar
2216
JuspayC++n-ary treeMultithreadingInterview

🔒 Juspay Tree of Space Hackathon Part B Solution | Thread-Safe

My Juspay On-Campus Experience:

Design a thread-safe locking system for a tree

Each node can be locked by a user only if:
None of its ancestors or descendants are locked.
Locking/Unlocking must be thread-safe (no race conditions).
The solution should efficiently support concurrent operations.

Interviewer shared Hackthon part A solution that was submitted by me during Hackathon Part A.

✅ Proposed Approaches
🔧 Approach 1 : Mutex + Manual Locking
Manually use .lock() and .unlock() for synchronization.

🔐 Approach 2: lock_guard
Automatically manages unlocking.
Safer alternative to manual locking.

🔁 Approach 3: Per-Node Mutexes
Each node has its own std::mutex.
Fine-grained locking improves concurrency.

⚡ Approach 4: Atomic Variables
Use std::atomic to represent lock state.
Requires careful memory ordering for correctness.

🌀 Approach 5: Peterson’s Algorithm
Classic mutual exclusion algorithm for two threads only.

🧱 Approach 6: Binary Semaphore
Custom semaphore puts thread to sleep while waiting.
Saves CPU during wait but adds some overhead.

🔄 Approach 7: Custom SpinLock (Manual Locking)
Busy-wait approach using CPU cycles.
Efficient for very short critical sections.

🔍 Spinlock vs Binary Semaphore

  1. Waiting Method
    Spinlock: Busy-wait (spins in loop)
    Binary Semaphore: Thread sleeps when unavailable

  2. CPU Usage
    Spinlock: High (does not release CPU)
    Binary Semaphore: Low (releases CPU)

  3. Overhead
    Spinlock: Low (no context switch)
    Binary Semaphore: High (context switch required)

  4. Best For
    Spinlock: Very short critical sections
    Binary Semaphore: Longer wait times

  5. Implementation
    Spinlock: Simple (uses atomic_flag)
    Binary Semaphore: Requires signaling mechanism

🧩 Spinlock – Custom C++ Implementation

#include <atomic>

class Spinlock {
private:
    std::atomic_flag flag = ATOMIC_FLAG_INIT;

public:
    void lock() {
        while (flag.test_and_set(std::memory_order_acquire)) {
            // Busy-wait (spin)
        }
    }

    void unlock() {
        flag.clear(std::memory_order_release);
    }
};

🔑 How it Works
std::atomic_flag is a low-level atomic boolean.

test_and_set() sets the flag to true and returns its old value atomically.

If it was already true, the thread keeps spinning (busy-waiting).

clear() releases the lock by setting the flag back to false.

The interviewer was looking for a solution without using any libraries. He wanted me to break down the algorithm and make it thread-safe. All the best for this round — just stay calm and communicate clearly. That’s all you can do.

Study Material :

Comments (1)