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

Wednesday, 23 March 2016

Features in Using OWASP Zed Attack Proxy (ZAP)

Background

In last post we saw how to setup ZAP proxy - 
 In this post I will show you some of the features of ZAP proxy that I have explored so far.


Spider And Active Scan

Whenever you decide to attack an URL that you see in ZAP's home page ZAP will crawl the page, find out other relevant links that the base URL may refer to in response. It also figures out GET/POST requests applicable. This is basically spider attack.

For demo purposes I am going to attack following URL - 
  • http://ch01.mybluemix.net/ch01/

It' a simple problem where you have to exploit few vulnerabilities to guess the password :)



Next ZAP will scan all the relevant applicable URL with test request params. It shows various attributes like response code, response bytes etc. You can also see the raw request/response with right click the request entry in Active scan. You can also see list of applicable URLs in the left panel.



 NOTE : One good trick to inspect irregular behavior is to inspect the size of response and inspect further the ones you see fishy.

Resend Request

Another useful feature is "Resend" . Just right click the request on left panel and select resend. You can then edit the request as per your wish (edit request params, headers add cookies etc) and send.




 Encode/Decode/Hash

This is a very handy feature that I loved in ZAP. Input a String and it will give you it's Encoding/Decoding/Hash whatever you need -

You can access this from Tools -> Encode/Decode/Hash




 Fuzzer

If you don't know what fuzzing is -

"Fuzz testing or Fuzzing is a Black Box software testing technique, which basically consists in finding implementation bugs using malformed/semi-malformed data injection in an automated fashion. "

More details -
 ZAP has an in build fuzzer that you can use. Simply
select the URL you want to fuzz -> Right click -> Attack -> Fuzz

You will need to highlight the area you want to fuzz and select add payload. The highlighted area can be anything - request parameter, cookie value, header etc. Also payload can be anything list of strings, scripts to be injected random values , alphabets etc.


Sample example is screenshot below -




 In above example I have highlighted "ZAP" which is the password. So I am going to fuzz various values of passwords. Next click Add to add payloads. You can define your own sets of string as well. I am using inbuilt file fuzzer that provided pre defined sets of strings. Finally click "Start Fuzzer" to start fuzzing.

NOTE : Again as I mentioned before it is always advantageous to sort response size to check unusual response to exploit :)


So far I have explored these. Will keep you updated :)
Stay tuned!



Related Links

Monday, 21 March 2016

Using OWASP Zed Attack Proxy (ZAP) and Plug-n-Hack as a proxy for your browser

Background

Some time back we saw how to use Fiddler proxy to intercept traffic from local browser or you Android devices. 
Recently I came across a more powerful proxy tool called OWASP Zed Attack Proxy or ZAP . It's not just a proxy tool. It is a tool used for ethical hacking. You can use it to attack sites and find vulnerabilities. Using ZAP you can do various things like -
etc.

You can read more about ZAP on their home page -

NOTE : You should use these ethical hacking tools only on sites that you have permission for. Using these on other sites may be treated as an offense.

In this post I am going to show you how to set up a simple proxy to redirect your browser traffic through ZAP.

 You can download the software from here. You can choose the download based on your operating system.

Once you download, install and open ZAP it would look something like below -



Using ZAP as proxy

Before we move on to browser to see how we can use ZAP as a proxy there lets see proxy settings in ZAP itself.
  • Go to Tools -> Options ->Local proxy
Here you can see the Address and port the proxy is listening on. You can manually configure your browser proxy settings to use this.



 Now click on Plug-n-Hack on the ZAP home page or copy the URL pasted in browser.

Click on "Click to setup!"

And install the addon.





 Finally enable the browser to send traffic via our ZAP proxy -



NOTE :  If you are getting - "A provider with this name has already been configured.".




You can manually check the proxy settings.




Also if you want the automatic configuration you can clear it. Also from now on you can use
  • zap
  • pnh
command in firefox console  (Shift + F2)
 



You can use pnh command to clear and remove proxy settings from firefox





You should finally see something like below -



Related Links

t> UA-39527780-1 back to top