Building H2O - Practice Coding Problems

Building H2O - Problem

Concurrency Medium

There are two kinds of threads: oxygen and hydrogen. Your goal is to group these threads to form water molecules.

There is a barrier where each thread has to wait until a complete molecule can be formed. Hydrogen and oxygen threads will be given releaseHydrogen and releaseOxygen methods respectively, which will allow them to pass the barrier.

These threads should pass the barrier in groups of three, and they must immediately bond with each other to form a water molecule. You must guarantee that all the threads from one molecule bond before any other threads from the next molecule do.

Constraints:

If an oxygen thread arrives at the barrier when no hydrogen threads are present, it must wait for two hydrogen threads
If a hydrogen thread arrives at the barrier when no other threads are present, it must wait for an oxygen thread and another hydrogen thread
Threads pass the barriers in complete sets of three (1 oxygen + 2 hydrogen)

Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.

Input & Output

Example 1 — Basic Thread Sequence

$ Input: n = 3 threads: H, H, O

› Output: All threads form one H2O molecule

💡 Note: Two hydrogen threads and one oxygen thread arrive, they coordinate through semaphores and all proceed together to form a water molecule.

Example 2 — Oxygen Arrives First

$ Input: n = 3 threads: O, H, H

› Output: Oxygen waits, then all form H2O molecule

💡 Note: Oxygen thread arrives first but must wait for two hydrogen threads. Once both hydrogens arrive, all three proceed together.

Example 3 — Multiple Molecules

$ Input: n = 6 threads: H, H, O, H, H, O

› Output: Two separate H2O molecules formed

💡 Note: First three threads (H, H, O) form one molecule, then the next three threads form a second molecule. No mixing between molecules.

Constraints

1 ≤ n ≤ 1000
n represents total number of threads
Threads arrive in any order
Must form complete H₂O molecules

Visualization

Tap to expand

Understanding the Visualization

Input Threads

Hydrogen and Oxygen threads arrive in random order

Synchronization

Threads coordinate using semaphores and barriers

Output Molecules

Complete H₂O molecules formed with perfect synchronization

Key Takeaway

🎯 Key Insight: Semaphores provide elegant thread coordination by counting available resources and blocking threads until complete molecules can be formed

Asked in

G Google 32 f Facebook 28 a Amazon 25 M Microsoft 22

The key insight is using semaphores to coordinate thread synchronization without busy waiting. Best approach uses semaphore-based coordination where threads register their availability and a coordinator releases exactly the right threads when a complete H₂O molecule can be formed. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Busy Waiting with Counters	O(n)	O(1)	Use shared counters with busy waiting to coordinate threads
Semaphore-Based Coordination	O(n)	O(1)	Use semaphores to efficiently block and coordinate thread synchronization

Busy Waiting with Counters — Algorithm Steps

Step 1: Each thread increments its counter
Step 2: Thread waits in loop until molecule can be formed
Step 3: One thread releases all three when ready

Visualization

Tap to expand

Step-by-Step Walkthrough

Thread Arrival

Threads increment their respective counters

Busy Wait

Threads continuously check if molecule can be formed

Molecule Formation

When 2H + 1O available, threads proceed together

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

typedef struct {
    int hCount;
    int oCount;
    pthread_mutex_t lock;
    pthread_barrier_t barrier;
} H2O;

H2O* createH2O() {
    H2O* h2o = malloc(sizeof(H2O));
    h2o->hCount = 0;
    h2o->oCount = 0;
    pthread_mutex_init(&h2o->lock, NULL);
    pthread_barrier_init(&h2o->barrier, NULL, 3);
    return h2o;
}

void hydrogen(H2O* h2o, void (*releaseHydrogen)()) {
    pthread_mutex_lock(&h2o->lock);
    h2o->hCount++;
    pthread_mutex_unlock(&h2o->lock);
    
    // Busy wait until we can form a molecule
    while (1) {
        pthread_mutex_lock(&h2o->lock);
        if (h2o->hCount >= 2 && h2o->oCount >= 1) {
            h2o->hCount -= 2;
            h2o->oCount -= 1;
            pthread_mutex_unlock(&h2o->lock);
            break;
        }
        pthread_mutex_unlock(&h2o->lock);
        usleep(1000);
    }
    
    pthread_barrier_wait(&h2o->barrier);
    releaseHydrogen();
}

void oxygen(H2O* h2o, void (*releaseOxygen)()) {
    pthread_mutex_lock(&h2o->lock);
    h2o->oCount++;
    pthread_mutex_unlock(&h2o->lock);
    
    // Busy wait until we can form a molecule
    while (1) {
        pthread_mutex_lock(&h2o->lock);
        if (h2o->hCount >= 2 && h2o->oCount >= 1) {
            h2o->hCount -= 2;
            h2o->oCount -= 1;
            pthread_mutex_unlock(&h2o->lock);
            break;
        }
        pthread_mutex_unlock(&h2o->lock);
        usleep(1000);
    }
    
    pthread_barrier_wait(&h2o->barrier);
    releaseOxygen();
}

char* solution(int n) {
    return "H2O synchronization implemented";
}

int main() {
    int n;
    scanf("%d", &n);
    char* result = solution(n);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each thread processes once, but busy waiting creates overhead

✓ Linear Growth

Space Complexity

O(1)

Only uses a few counter variables and locks

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Busy Waiting with Counters — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler