Wednesday, January 30, 2019

Advanced Data Structure — UnionFind. - Find the big brother.


So you decided to take it one step further, huh? Instead of settling with Array and maybe LinkedList.
Although there’s nothing wrong just knowing the basic ones, you still can be a solid developer.
But if you ever want to be a engineer, let’s dive in:

Step 0. Why? (Skip to Step 1 if you are a professional)
What exactly is UnionFind and why do we need it?
Remember Audible and Amazon, eh?
Now who’s the boss?
Yes! Audible belongs to Amazon.
Ok this sounds far too simple, we can just get a HashMap, and just point the Audible to its parent.
Well well well, imagine you are in a system design and need to point thousands of employees to their parent, hmm?
Oh and make it more challenging let’s say the companies are merging and selling all the time.
Great! You agreed we need something efficient and professional.

Step 1. How?
So for professionals I am telling you outright that UnionFind actually is tree.
You were right, using a HashMap or Array would do the job but we need a little delicate path compression and trust me this data structure is full of traps that you can make it full of bugs easily if careless, or even just tired.
For the sake of brevity we are using a simple primitive Java array. (You can swap it with a HashMap easily).
  • 1.1. Constructor
We are simply pointing everybody to himself. Meaning everyone is a disconnected dot. Audible belongs to Audible meaning it is not yet acquired by any other company.
public ConnectingGraph_589(int n) {
    // do intialization if necessary
    father = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}
  • 1.2. Connect
Connect two companies together. e.g. pointing Audible as the son of Amazon. Meaning Amazon acquires Audible.
public void connect(int a, int b) {
    // write your code here
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        father[rootA] = rootB;
    }
}
  • 1.3. Query
Check if the two companies belong to the same corporation.
This means returning true if Audible and Amazon has the same BIG brother — Amazon.
Or let’s say returning true if Nokia and Microsoft has the same BIG brother — the MS.
public boolean query(int a, int b) {
    // write your code here
    return find(a) == find(b);
}
  • 1.4 Find
This is the best part of the data structure in that you recursively find the BIG brother and update every children in the meanwhile.
private int find(int x) {
    if (father[x] == x) {
        return x;
    } else {
        return father[x] = find(father[x]);
    }
}

Last Step, show me the code:
public class ConnectingGraph_589 {
    private int[] father;

    /*
     * @param n: An integer
     */
    public ConnectingGraph_589(int n) {
        // do intialization if necessary
        father = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    public void connect(int a, int b) {
        // write your code here
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
        }
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: A boolean
     */
    public boolean query(int a, int b) {
        // write your code here
        return find(a) == find(b);
    }

    private int find(int x) {
        if (father[x] == x) {
            return x;
        } else {
            return father[x] = find(father[x]);
        }
    }
}
For more algorithms feel free to check out my Github https://github.com/oliverwreath/JiuZhang.git

Saturday, January 26, 2019

Ch4 BFS - Bootstrap your algorithms.

Now as it is known to all, the BFS can be easily implemented with the help of a Queue, or more so a FIFO data structure.

But much less known to all, the BFS has quite a few variations of implementation.
For starters, there's two Queue implementation and there's one Queue.
You can use a level counter, or you can simply use a dummyNode.

Alright so here's just one way of going about doing it.

PS: If you are using Java 8 and love succinct code, just use offer and poll methods as they don't invoke type conversion like the addFirst, addLast do. Which can look quite unappreciated.



Ch5 DFS - Bootstrap your algorithms.

As we all know BFS and DFS are the famous two pillars of the Searching algorithms.

Now as we all know BFS can be easily accomplished with a simple Queue. Or let's say a FIFO data structure.

But the DFS remains a tricky one, for we actually usually keep the main function concise and just call a beefy helper function to get it done.

Of course somebody will raise their hand and say "Why not just use recursion?"
Baby, recursion and iterations are not algorithms themselves, however they remains two different styles of implementing the same algorithms.

Now talk is cheap, show me the code:


Tuesday, January 22, 2019

Spring Boot Environment Switch Made Easy

Spring Boot Environment Switch Made Easy

Tired of changing the *.properties file spring.profiles.active=dev to prod every single time before deployment? 
You are NOT alone! 
It is OK to stand up and say, enough! 
application-dev.properties

Step 3 — Setup the Production environment to automatically call PROD profile.

spring.profiles.active=prod
That’s right baby! I go through a bunch of documents and StackOverFlow posts just to find out we only need one simply setting. 
PS: Depending on your AWS Beanstalk environment version, the old posts suggesting SPRING_PROFILES_ACTIVE(Linux environment style) didn’t work. The reason being Amazon aws apparently prefer this style and change them overnight. Yay thanks to me now you probably just dodge a bullet of half and hour. 

Step 2 — Setup the Development environment to automatically call DEV profile. 

The key is to set the JVM options: -Dspring.profiles.active=dev
-Dspring.profiles.active=dev
PS: there could be a pitfall depending on your IDE, as I was caught off-guard seeing all the tests failed! But it turns out that I need to set the JVM options for every single one of the tests too! 
-Dspring.profiles.active=dev

Step 1 — Setup a couple of properties file for each and every environment.

  • Keep your common settings, just leave them right where they are. 
  • Migrate dev settings (e.g.Turn on hibernate sql print; Turn off the view engine cache to see instant change as you write your code) to the application-dev.properties. 
  • Migrate prod settings (e.g. Turn on all sort of caches. Jack up the number of connections in pool.) to the application-prod.properties.

Alright, now you are all set. 
Feel free to comment below share your thoughts experience.
For more technical articles feel free to follow.