Printing Even and Odd numbers using 2 different classes

Question

This was a question asked in one of my job interviews:

You have 2 different classes (that implements Runnable) say EvenThread & OddThread. As the name suggests, the EvenThread prints only even numbers and the odd thread prints only odd numbers, consider a range of 0-100.

class EvenThread implements Runnable {

    @Override
    public void run() {
        for (int i = 0; i <= 10; i += 2) {
            System.out.println(i);
        }
    }
}

class OddThread implements Runnable {

    @Override
    public void run() {
        for (int i = 1; i < 10; i += 2) {
            System.out.println(i);
        }
    }
}

public class EvenOdd {

    public static void main(String args[]) {
        Thread tEven = new Thread(new EvenThread());
        Thread tOdd = new Thread(new OddThread());

        tEven.start();
        tOdd.start();
    }
}

Now we need to enforce a mechanism in such a way that, the numbers are printed in sequence (i.e. 0, 1, 2, 3, 4,.... and so on).

I have seen many similar questions in Stack Overflow, but they have just one class to print number and 2 synchronized methods are invoked in it.

Could any of the experts please suggest?

You need one thread to _notify_ the other thread that it has finished printing, so the other can print and _notify_ back. — Sotirios Delimanolis, Jun 16 '14 at 16:00
Notify, like Sotirios said. I'm curious if this could be accomplished by having an atomic variable as a part of each thread (lock/semephore), eliminating the need for a notify — Kyte, Jun 16 '14 at 16:03
@Kyte Wouldn't that still leave a race condition? What would prevent you from getting `1 3 2 4 ...`? — jpmc26, Jun 16 '14 at 16:05
@SotiriosDelimanolis: Thanks for your response! If I am getting it right, we need to implement wait-notify mechanism in such a way that once EvenThread is done printing Even number, it should notify OddThread to print the Odd number. Likewise, OddThread should wait and notify EvenThread. But, I am not getting a hint on how exactly could this be implemented. Could you please explain with sample code? — Curious Coder, Jun 16 '14 at 16:06
The threads would have to be hardcoded to know whether to start with a print to to check the other threads atomic variable — Kyte, Jun 16 '14 at 16:06
Look in the related section to the right. You'll find a bunch of examples. — Sotirios Delimanolis, Jun 16 '14 at 16:08
@Kyte: I believe what you meant is the same as what Mena's code below demonstrates. — Curious Coder, Jun 16 '14 at 16:31

score 4 · Accepted Answer · answered Jun 16 '14 at 16:20

Here's an ugly example with a low-level-ish wait/notify mechanism:

public class Main {
    static boolean turn = false; // false is even, true is odd

    public static void main(String[] args) {
        Object o = new Object();
        Thread tEven = new Thread(new EvenThread(o));
        Thread tOdd = new Thread(new OddThread(o));

        tEven.start();
        tOdd.start();
    }

    // TODO some inheritance with [Even/Odd]Thread

    static class EvenThread implements Runnable {
        Object o;

        EvenThread(Object o) {
            this.o = o;
        }

        @Override
        public void run() {
            for (int i = 0; i <= 10; i += 2) {
                synchronized (o) {
                    try {
                        while (turn) {
                            o.wait();
                        }
                    }
                    catch (InterruptedException ie) {
                        ie.printStackTrace();
                    }
                    finally {
                        System.out.println(i);
                        turn = !turn;
                        o.notifyAll();
                    }
                }
            }
        }
    }

    static class OddThread implements Runnable {
        Object o;

        OddThread(Object o) {
            this.o = o;
        }

        @Override
        public void run() {
            for (int i = 1; i < 10; i += 2) {
                synchronized (o) {
                    try {
                        while (!turn) {
                            o.wait();
                        }
                    }
                    catch (InterruptedException ie) {
                        ie.printStackTrace();
                    }
                    finally {
                        System.out.println(i);
                        turn = !turn;
                        o.notifyAll();
                    }
                }
            }
        }
    }
}

Output

Fantastic! The way 'Object o' is shared is the trick that I was trying to implement. Many thanks! :) — Curious Coder, Jun 16 '14 at 16:28

score 1 · Answer 2 · edited May 23 '17 at 11:44

Not a direct answer to your question but just to show you do not always need locks or synchronization - a memory barrier could suffice.

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

public class EvenAndOdd implements Runnable {

public static final int MAX_RUNTIME_SECONDS = 3;

public static void main(String[] args) {

    ExecutorService tp = Executors.newCachedThreadPool();
    AtomicInteger counter = new AtomicInteger();
    tp.execute(new EvenAndOdd(counter, true));
    //try { Thread.sleep(500); } catch (Exception ignored) {}
    tp.execute(new EvenAndOdd(counter, false));
    tp.shutdown();
    boolean tpTerminated = false;
    try {
        if (tp.awaitTermination(MAX_RUNTIME_SECONDS, TimeUnit.SECONDS)) {
            tpTerminated = true;
            System.out.println("Finished.");
        }
    } catch (Exception e) {
        e.printStackTrace();
    } finally {
        if (!tpTerminated) {
            System.out.println("Forcing shutdown.");
            tp.shutdownNow();
        }
    }
}

public static final int MAX_COUNTER = 10;

private final boolean odd;
private final AtomicInteger counter;

public EvenAndOdd(AtomicInteger counter, boolean odd) {
    this.odd = odd;
    this.counter = counter;
}

@Override
public void run() {

    int emptyCycleCounter = 0;
    while (true) {
        int i = counter.get();
        if (i > MAX_COUNTER) {
            break;
        }
        if (i % 2 == (odd ? 1 : 0)) {
            System.out.println(i + (odd ? " odd" : " even"));
            counter.incrementAndGet();
        } else {
            emptyCycleCounter++;
            Thread.yield();
        }
    }
    System.out.println("Finished"  + (odd ? " odd" : " even") + " with " + emptyCycleCounter + " empty cycles.");
}
}

Shobha Jha · Answer 3 · 2016-07-07T12:52:29.503

public class MyLock {

public MyLock(Boolean even) {
    super();
    this.even = even;
}

static Boolean even = null;

public synchronized void lock(boolean value) {

    while (even != value) {
        try {
                    wait();
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

}

public synchronized void unlock() {
    even = !even;
    notify();
}

}

public class OddEven {

private static final int Max_CCOUNTER = 100;
static final MyLock lock = new MyLock(true);

public static void main(String[] args) {
    // TODO Auto-generated method stub
    new Thread(() -> printEven(), "EVEN").start();
    ;
    new Thread(() -> printOdd(), "ODD").start();
    ;

}

static void printEven() {

    for (int i = 0; i < Max_CCOUNTER; i = i + 2) {
        lock.lock(true);
        System.out.println(i + ":" + Thread.currentThread().getName());
        lock.unlock();
    }
}

static void printOdd() {

    for (int i = 1; i < Max_CCOUNTER; i = i + 2) {
        lock.lock(false);
        System.out.println(i + ":" + Thread.currentThread().getName());
        lock.unlock();

    }
}

}

Printing Even and Odd numbers using 2 different classes

3 Answers3