Friday 29 April 2016

Box Ball Logic Problem

Question

There are three bags.

  1. The first bag has two blue rocks. 
  2. The second bag has two red rocks. 
  3. The third bag has a blue and a red rock.
All bags are labeled but all labels are wrong.You are allowed to open one bag, pick one rock at random, see its color and put it back into the bag, without seeing the color of the other rock.

How many such operations are necessary to correctly label the bags ?




Solution

Just one!

You pick a ball from the bag labelled "blue and red" ... if its blue then that's the 2 blue rocks bag and likewise for the red. ( since all bags are labelled wrong the one reading blue and red would not actually contain a blue and red ball. So it label will be whatever color of ball comes from it) Next if we get a blue ball from the blue and red labelled bag we know that the bag labelled red has got to be blue and red since we have already used up the blue label and since all bags are labelled wrongly it cannot be red.

Thursday 28 April 2016

Lowest Common Ancestor in a Binary Tree.

Background

In one of the previous posts we saw how to find LCA of two nodes in a Binary search tree. In this post we will repeat the same question but now it's just a binary tree not a BST.



 Solution

    public static BTreeNode findLCA(BTreeNode root, int n1, int n2) {

        if (root == null) {
            return null;
        }

        if (root.getData() == n1 || root.getData() == n2) {
            return root;
        }

        BTreeNode leftNode = findLCA(root.getLeft(), n1, n2);
        BTreeNode rightNode = findLCA(root.getRight(), n1, n2);

        if (leftNode != null && rightNode != null) {
            return root;
        }

        return leftNode != null ? leftNode : rightNode;

    } 


I have posted complete solution with test cases on my GIT repo of interview question. You can find the code -

Logic is as follows -

  • If one of the two nodes is the root, then the root itself is the common ancestor.
  • If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
  • If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
  • Otherwise, root is the Lowest common ancestor.

Related Links


Remove repetitive words from a String and return it

Question

Assume you are given a string, write a function that can remove consecutive repeated words in the string and return it. For example,

"Beginning with the first first first first manned Gemini mission in March 1965, commemorative commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only only, only that each individual box containing a medallion bore the word Fliteline."

to

"Beginning with the first manned Gemini mission in March 1965, commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only, only that each individual box containing a medallion bore the word Fliteline."

Make sure you preserving punctuations in the right positions.


Solution

I have written following Java code with various methods that solve variations of above question -


import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * 
 * @author athakur
 *
 */
public class RemoveDuplicates {

    public static void main(String args[]) {

        String input = "Beginning with the first first first first manned Gemini mission in March 1965, commemorative commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only only, only that each individual box containing a medallion bore the word Fliteline.";

        System.out.println(removeConsecutiveDuplicates(input));
        System.out.println(removeConsecutiveDuplicatesBetter(input));
        System.out.println(removeAllDuplicates(input));

    }

    public static String removeAllDuplicates(String input) {
        StringBuilder outputBuilder = new StringBuilder();
        Set<String> wordsSet = new HashSet<>();
        StringTokenizer tokenizer = new StringTokenizer(input, " ");
        while (tokenizer.hasMoreTokens()) {
            String word = tokenizer.nextToken();
            if (wordsSet.add(word)) {
                outputBuilder.append(word);
                outputBuilder.append(" ");
            }
        }
        return outputBuilder.toString();
    }

    public static String removeConsecutiveDuplicatesBetter(String input) {

        StringBuilder outputBuilder = new StringBuilder();
        String lastWord = "";
        StringTokenizer tokenizer = new StringTokenizer(input, " ");
        while (tokenizer.hasMoreTokens()) {
            String word = tokenizer.nextToken();
            if (!word.equalsIgnoreCase(lastWord)) {
                outputBuilder.append(word);
                outputBuilder.append(" ");
            }
            lastWord = word;
        }
        return outputBuilder.toString();

    }

    public static String removeConsecutiveDuplicates(String input) {

        if (input == null)
            return null;

        Stack<String> wordsStack = new Stack<>();
        String[] words = input.split(" ");
        for (int i = 0; i < words.length; i++) {
            wordsStack.push(words[i]);
        }

        String lastWord = "";
        String stringWithNoConsecutiveDuplicates = "";

        while (!wordsStack.isEmpty()) {
            String tempPop = wordsStack.pop();
            if (!lastWord.equalsIgnoreCase(tempPop)) {
                stringWithNoConsecutiveDuplicates = tempPop + " "
                        + stringWithNoConsecutiveDuplicates;
            }

            lastWord = tempPop;
        }

        return stringWithNoConsecutiveDuplicates;

    }

}


Note

Couple of points to note. Prefer removeConsecutiveDuplicatesBetter approach as it does not keep all data in memory. So lets say you have a huge file you need to do this operation on you read it line by line and then tokenize it to further process it.

Also note HashSet has add method which returns false if data is already present in the set.

Stack method is more if you want to retain the duplicate consecutive words which are farthest in a line. Irrespective of your approach you need to take care of following -

  • Don't keep all the data in the memory (data can be very huge). Using Stack may led to overflow.
  • Use minimum space and more efficient lookup. Hashset internally used HashMap to keep the data hence put/get is ~O(1).
  • Avoid String concatenation. Use StringBuilder instead.

As you must have already noticed above approaches do not take care of punctuations. You will need separate processing for that.

Related Links







Sunday 10 April 2016

ThreadLocal class in Java

Background

Java concurrency and multi-threading is a wide topic. If you are coding for a multi threaded application you need to take care of thread safety. Not all objects are thread safe. Any by thread safety I mean that if a thread is working on some variable and context switch happens and some other thread alters the value of the variable, when 1st thread comes back it will see different value which ultimately will led to inconsistent state (race condition).

One way to ensure thread safety is by Synchronization. In this basically you need to acquire lock before entering a critical region. Other threads have to wait until current that that holds the lock releases it. 

Another way to ensure thread safety is by using ThreadLocal variable. This basically ensures each thread has it's own local copy of this variable and cannot access copy held by other threads. Hence the case of race or inconsistency will never arise. Lets see this in more details.

Example

Consider following example -



public class ThreadLocalDemo {
    
    public static void main(String args[]) throws InterruptedException {    
        MYRunnable myRunnable  = new MYRunnable();
        Thread t1 = new Thread(myRunnable);
        Thread t2 = new Thread(myRunnable);
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        
    }
}


class MYRunnable implements Runnable {


    ThreadLocal<String> myThreadLocal = new ThreadLocal<String>(){
        protected String initialValue() {
            return "InitialValue";
        };
    };
    
    @Override
    public void run() {
        System.out.println(Thread.currentThread().getName() + " : Before : " + myThreadLocal.get());
        myThreadLocal.set("NewValue1");
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        System.out.println(Thread.currentThread().getName() + " : After 1 : " + myThreadLocal.get());
        myThreadLocal.set("NewValue2");
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        System.out.println(Thread.currentThread().getName() + " : After 2 : " + myThreadLocal.get());
        myThreadLocal.set("NewValue3");
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        System.out.println(Thread.currentThread().getName() + " : After 3 : " + myThreadLocal.get());
    }
    
}

Output is - 

Thread-1 : Before : InitialValue
Thread-0 : Before : InitialValue
Thread-0 : After 1 : NewValue1
Thread-1 : After 1 : NewValue1
Thread-0 : After 2 : NewValue2
Thread-1 : After 2 : NewValue2
Thread-0 : After 3 : NewValue3
Thread-1 : After 3 : NewValue3

As you can see values are consistent across threads. There are no race conditions.


More Info


  • Good example of ThreadLocal is SimpleDateFormat. Since SimpleDateFormat is not thread safe, having a global formatter may not work (different threads may alter it's value and may led to inconsistent state) but having per Thread formatter will certainly work.
  • What I have generally seen is ThreadLocal variable being declared static and its value being set and retrieved per thread.
  • ThreadLocal variable are more like local variable (which are only accessible in the block they are declared). ThreadLocal can only be accessed in same thread.

NOTE 

  • You need to be very careful about cleaning up any ThreadLocals you get() or set() by using the ThreadLocal's remove() method.
  • If you do not clean up when you're done, any references it holds to classes loaded as part of a deployed webapp will remain in the permanent heap and will never get garbage collected. Redeploying/undeploying the webapp will not clean up each Thread's reference to your webapp's class(es) since the Thread is not something owned by your webapp. Each successive deployment will create a new instance of the class which will never be garbage collected.
  • So if you use ThreadLocal to store some object instance there is a high risk to have the object stored in the thread local never garbaged when your app runs inside an app server like WebLogic Server, which manage a pool of working thread - even when the class that created this ThreadLocal instance is garbage collected.


Related Links

t> UA-39527780-1 back to top