Synchronization is easy ?

Sometimes its hard to find bugs when it comes to multi-threading environment as few programers forget fundamental concepts of writing a synchronized block. If we talk about synchronized block I can create it in three different ways.

1. Using Object synchronization [acquire lock on "this"]
2. Using Class synchronization [acquire lock on "MyClass.class"]
3. Using "another" Object for synchronization [acquired lock on "different" object]

Lets see if you can find the bug in the below code. HINT: Read the above 3 points carefully.

/*
 * CountManager
 */
public class CountManager {
    static int count = 0;

    public static synchronized void incrementFew(int n) {
        for (int i = 0; i < n; i++) {
            count++;
            log("Static : " + count);
            try {
                Thread.sleep(200);
            } catch (Exception e) {
                // doesn't matter.
            }
        }
    }

    public synchronized void addFew(int n) {
        for (int i = 0; i < n; i++) {
            count++;
            log("Non-Static : " + count);
            try {
                Thread.sleep(200);
            } catch (Exception e) {
                // doesn't matter.
            }
        }
    }

    /*
     * CountMangagerClient, needs run()
     */
    static abstract class CountManagerClient implements Runnable {
        CountManager s;

        public CountManagerClient(CountManager s) {
            this.s = s;
        }
    }

    private static void log(String str) {
        System.out.println(str);
    }

    /* main */
    public static void main(String[] args) {
        CountManager s = new CountManager();
        Thread t1 = new Thread(new CountManagerClient(s) {
            public void run() {
                s.addFew(5); // no change in client code
                System.out.println("Result = " + CountManager.count);
            }
        });
        Thread t2 = new Thread(new CountManagerClient(s) {
            public void run() {
                CountManager.incrementFew(5); // no change in client code
                System.out.println("Result 2 = " + CountManager.count);
            }
        });
        t1.start();
        t2.start();
    }
}

OUTPUT
Non-Static : 1
Static : 2
Non-Static : 4
Static : 4
Static : 6
Non-Static : 6
Static : 7
Non-Static : 8
Non-Static : 10
Static : 10
Result = 10
Result 2 = 10

If you were able to find the bug, you really know synchronization. Anyways , the problem here is we are trying to synchronize the code block by acquiring the locks from two differet objects AKA "this" and "MyClass.class"

So, what is the solution? its simple; either use Object synchronization or Class synchronization. But what if the code is already being used by other clients which uses both? humm !! then introduce another object wihch is common to both of these code blocks and acquire lock on that object. This way you will not have to change the client code. Here is how you will do that:

/*
 * CountManager
 * @Threadsafe
 */
public class CountManager {
    static int count = 0;
    /* Object to get lock from */
    private static final Object obj = new Object();

    public static void incrementFew(int n) {
        synchronized (obj) { /* get lock from Object 'obj' instead of 'MyClass.class'*/
            for (int i = 0; i < n; i++) {
                count++;
                log("Static : " + count);
                try {
                    Thread.sleep(200);
                } catch (Exception e) {
                    // doesn't matter.
                }
            }
        }
    }

    public void addFew(int n) {
        synchronized (obj) { /* get lock from Object 'obj' instead of 'this'*/
            for (int i = 0; i < n; i++) {
                count++;
                log("Non-Static : " + count);
                try {
                    Thread.sleep(200);
                } catch (Exception e) {
                    // doesn't matter.
                }
            }
        }
    }

    /*
     * CountMangagerClient, needs run()
     */
    static abstract class CountManagerClient implements Runnable {
        CountManager s;

        public CountManagerClient(CountManager s) {
            this.s = s;
        }
    }

    private static void log(String str) {
        System.out.println(str);
    }

    public static void main(String[] args) {
        CountManager s = new CountManager();
        Thread t1 = new Thread(new CountManagerClient(s) {
            public void run() {
                s.addFew(5); // no change in client code
                System.out.println("Result = " + CountManager.count);
            }
        });
        Thread t2 = new Thread(new CountManagerClient(s) {
            public void run() {
                CountManager.incrementFew(5); // no change in client code
                System.out.println("Result 2 = " + CountManager.count);
            }
        });
        t1.start();
        t2.start();
    }
}

OUTPUT:
Static : 1
Static : 2
Static : 3
Static : 4
Static : 5
Non-Static : 6
Result 2 = 6
Non-Static : 7
Non-Static : 8
Non-Static : 9
Non-Static : 10
Result = 10

Odd one out !!

Problem: In an array of integers, all but one occur even number of times. Find the one which occur odd number of times.

First solution:
Use Hashmap like data structure Map to hold the Integer in the given array & the corresponding count.
performance : O(n) + O(n) = O(n)
Problem : extra space & data structure

Second solution:
Sort the array & start skipping the pair e.g. [2,2,3,3,9,9,11,11,11,12,12,34,34] : 11 cannot be skipped as it’s not a pair.
performance: O (nlog(n)) + O(n)
problem: bad performance

Trick solution:
We know X XOR X = 0, therefore start with 0 as result and XOR all the elements with result.
performace : O(n)
problem: none, let me know if you see any

public static void main(String[] args){
      int[] arr = {2,3,6,9,20,2,4,6,9,20,3};
      int result = 0;
      for(int i: arr){
          result ^= i;
      }
      System.out.println(result); //prints 4
  }