Thursday, 15 October 2020

Building Binary Heap In O(n) Worst Time Complexity Explained

There are two ways we can build a binary heap, top-down & bottom-up. We will take top-down approach first. Let's consider the max heap below.

For top-down approach we will start from the root & then move the node towards the bottom till max heap property is satisfied. As you can see from screenshot, heap is a complete binary tree.
We will denote number of nodes at level h as n(h).
When h = 0, n(h) = 2^0 = 1
h = 1, n(h) = 2^1 = 2
h = 2, n(h) = 2^2 = 4
As you can see, a particular level always contains one more node than the total nodes of all previous levels. Let's consider when height is 2. n(h) is 4 which is greater than (1 + 2) = 3 which is total number of nodes in height 0 & 1.
But because heap is a complete binary tree, last level might not have all the nodes as you can see in the screenshot.
When h = 3, n(h) = 5
But what about total number of leaf nodes? At h=3, we have 5 leaf nodes & h=2 we have 1 leaf node.
So total leaf node is 6. And total non-leaf nodes is also 6. If last level contains all possible nodes, then more than half of total nodes are leaf nodes. Otherwise, we will have at least half nodes as leaf nodes in a complete binary tree. This is an important thing to understand.

Now let's go back to our top down approach. We start from the root each time. And then move nodes towards leaf level till it satisfies heap property. So we will have to move at least half of the nodes to leaf level from root level which is basically height of the tree h & that is log(n). So this scenario will take (n / 2) * log(n) time. So time complexity will become O(n log(n)).

We will take a look at bottom-up approach now. For bottom-up, we will start at the leaf level. At leaf level, we don't need to do any shift as any leaf node would satisfy heap property. We move one level up (h-1) & at that level we need to shift at most one level down. At (h-2) level we need to shift at most 2 level.
So we can write something similar as below:
(0 * n/2) + (1 * n/4) + (2 * n/8) + (3 * n/16) + ... + (h * 1)
= (1 * n/4) + (2 * n/8) +  (3 * n/16) + ... + (h * 1)
h
= ∑ kn/(2^(k+1))
k=1
We can move n out
h
n * ∑ k/(2^(k+1))
k=1

k/(2^(k+1)) can be simplified as k/(2^k * 2). 2 can be omitted as we don't need to consider constant value for time complexity.

h
∑ k/(2^k)) we need to check what happens when k value approaches to infinity.
k=1

1/ 2^1 + 2/2^2 + 3/2^3 + 4/2^4 + 5/^2^5 + 6/2^6 + ....
=1/2 + 1/2 + 3/8 + 1/4 + 5/32 + 3/32 + ....

As you can see the value will converge towards 2.
So worst time complexity will become O(n * 2) which is basically O(n).

Wednesday, 7 October 2020

What Is The Actual Difference Between Closeable And AutoCloseable In Java

Well, practically there is not much difference. If you check Java doc, you will notice that Closeable interface extends AutoCloseable interface. But there is one difference & that explains the reason why AutoCloseable interface was introduced in Java 7. Closeable  close() method can throw IOException only. And that made  sense as you will be using Closeable mostly with IO resources. But to handle other generic exceptions too with close() method, AutoCloseable was introduced.

public interface Closeable extends AutoCloseable {

public void close() throws IOException;

}

public interface AutoCloseable {

void close() throws Exception;

}

There is a misconception that Closeable can't be used with try-with-resources code block. But that is not true from Java 7 & hopefully everybody has a more upgraded version than that ðŸ˜€. Both interfaces work with try-with-resources statement so that you don't have to call close() method explicitly.

Sunday, 20 September 2020

How To Solve XML Parsing Issue "Content is not allowed in prolog" In Java

If you have come to this post, then you are facing xml parsing issue in Java.

Caused by: org.xml.sax.SAXParseException; lineNumber: 1; columnNumber: 1; Content is not allowed in prolog.
at com.sun.org.apache.xerces.internal.util.ErrorHandlerWrapper.createSAXParseException(ErrorHandlerWrapper.java:203)

One common issue for this is BOM character. So what is a BOM (BYTE ORDER MARK) character? When you have multi byte format like UTF-16 or UTF-32, sever needs to indicate if the most significant byte starts from left or right (Big Endian & Little Endian). That's the purpose of BOM. It is a zero-width invisible character. Based on its value (FEFF or FFFE), a byte sequence can be treated as BIG Endian or Little Endian.
If your XML is in UTF-8 format, then BOM character is not required because UTF-8 is 8 bits (single byte). But the remote server might still send BOM character in the xml response due to legacy reasons. And while you are unmarshalling using JAXB, you will get above error.

To solve this, you can wrap around response input stream with BOMInputStream. It is from Apache Commons library.

BOMInputStream bomIn = new BOMInputStream(inputStream);
bomIn.hasBOM();
That should resolve the issue. Method hasBOM() actually checks & removes any BOM character in the input stream. Name of the method is a bit confusing.
Now you can parse the xml response without any error.

Thursday, 17 September 2020

A Free Online Tool To Draw Sequence Diagram Writing Text

Some of us need to create sequence diagrams while doing architecture design of product or a new feature. There are several online websites out there which can be used to draw sequence diagrams. Some of them are free & some of them are paid services. They support different features. Somewhere you can actually draw, somewhere you can type in text & some might support both. Personally I prefer to write text. That is quick & easy. We just need to type in the interactions between objects & tool will draw the sequence diagram for us. WebSequenceDiagrams is such a online tool. Its free version supports almost all the things that you would need to create a sequence diagram.

Wednesday, 16 September 2020

How To Fix "unable to find valid certification path to requested target" Error

If you are here, that means probably you have encountered below error:

Caused by: sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target
at sun.security.validator.PKIXValidator.doBuild(PKIXValidator.java:387)
at sun.security.validator.PKIXValidator.engineValidate(PKIXValidator.java:292)
at sun.security.validator.Validator.validate(Validator.java:260)
at sun.security.ssl.X509TrustManagerImpl.validate(X509TrustManagerImpl.java:324)
at sun.security.ssl.X509TrustManagerImpl.checkTrusted(X509TrustManagerImpl.java:229)
at sun.security.ssl.X509TrustManagerImpl.checkServerTrusted(X509TrustManagerImpl.java:124)
at sun.security.ssl.ClientHandshaker.serverCertificate(ClientHandshaker.java:1460)
... 101 more
Caused by: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target
at sun.security.provider.certpath.SunCertPathBuilder.build(SunCertPathBuilder.java:145)
at sun.security.provider.certpath.SunCertPathBuilder.engineBuild(SunCertPathBuilder.java:131)
at java.security.cert.CertPathBuilder.build(CertPathBuilder.java:280)
at sun.security.validator.PKIXValidator.doBuild(PKIXValidator.java:382)

That happens when you try to connect to a https url from Java application & that remote server SSL certificate is not trusted by your JVM. Basically Java has a Truststore where it stores root certificates & intermediate certificates from Certified Authorities (CA). So in case the remote server is using a self-signed certificate or a certificate from not a well-known CA, there is a chance that the root & intermediate certificates of the CA are not present in your Java Truststore. You need to add it manually.

I found out a small Java program online that can easily help you with that. You can just check this link & follow the steps to add certificates to your Java Truststore. This program also validates if the certificates are already added & working properly.

But just make sure you do really know the remote server before adding their certificates to your Java Truststore.

Saturday, 5 September 2020

Draw Tree Or Graph Online Using Plain Text

Sometimes we need to draw a binary tree or graph online to explain related stuffs. I wanted to share a website where you can write your tree or graph definition in plain english & you will get a graphical representation of it. You will just have to define relations between the nodes in text, that's all. It supports both directed & undirected graphs. Basically this tool follows DOT language which is nothing but a standard set of instructions to define the relations between nodes. It even supports attributes for edges & nodes.
For an example, just look at the screenshot below. Is it not simple? And then you can download it as an image.

How To Solve "Caused by: org.hibernate.HibernateException: Missing table" When Table Is Present In Database

If you are using JPA or Hibernate directly and got that exception while starting your application, there is one obvious reason for that. You...